Need help with In-Place Quick Sort Implementation - leusiam - 07-21-2023
Hello, I'm working in Python on constructing an in-place version of the Quick Sort method. After doing some research and reading this article on Quick Sort Algorithm, I realized that an in-place Quick Sort reduces the need for extra RAM for temporary arrays, which can be useful for huge datasets. However, I'm having problems understanding how to split and swap parts in-place properly.
So far, here's the code I've tried:
Code: def quick_sort_inplace(arr, low, high):
if low >= high:
return
pivot_index = (low + high) // 2
pivot_value = arr[pivot_index]
# Swapping pivot with the last element to simplify partitioning
arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
# Partitioning the array
i = low - 1
for j in range(low, high):
if arr[j] < pivot_value:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# Swapping pivot back to its correct position
arr[i + 1], arr[high] = arr[high], arr[i + 1]
# Recursive calls for left and right sub-arrays
quick_sort_inplace(arr, low, i)
quick_sort_inplace(arr, i + 2, high)
# Example usage
my_array = [38, 27, 43, 3, 9, 82, 10]
quick_sort_inplace(my_array, 0, len(my_array) - 1)
print(my_array)
When I run the code, however, it does not yield the desired sorted output. I suspect there is a problem with my in-place partitioning or swapping procedures.
Could someone kindly go through my code and tell me what's going wrong? Any ideas or adjustments to my Quick Sort implementation in-place would be greatly appreciated.
Thank you so much!
RE: Need help with In-Place Quick Sort Implementation - JustJohnQ - 07-21-2023
You’re asking this in a Codeigniter forum?
RE: Need help with In-Place Quick Sort Implementation - gosocial2 - 07-22-2023
Here is a Cı4 library that ports your code to PHP:
PHP Code: <?php namespace App\Libraries;
class QuickSortLib { public function sortInplace(&$arr, $low, $high) { if ($low >= $high) { return; }
$pivot_index = intdiv($low + $high, 2); $pivot_value = $arr[$pivot_index];
// Swapping pivot with the last element to simplify partitioning list($arr[$pivot_index], $arr[$high]) = array($arr[$high], $arr[$pivot_index]);
// Partitioning the array $i = $low - 1; for ($j = $low; $j < $high; $j++) { if ($arr[$j] < $pivot_value) { $i += 1; list($arr[$i], $arr[$j]) = array($arr[$j], $arr[$i]); } }
// Swapping pivot back to its correct position list($arr[$i + 1], $arr[$high]) = array($arr[$high], $arr[$i + 1]);
// Recursive calls for left and right sub-arrays $this->sortInplace($arr, $low, $i); $this->sortInplace($arr, $i + 2, $high); } } ?>
You can use this library in a controller like this:
PHP Code: <?php namespace App\Controllers;
use App\Libraries\QuickSortLib;
class SortController extends BaseController { public function index() { $my_array = array(38, 27, 43, 3, 9, 82, 10); // Instantiate the library $quickSortLib = new QuickSortLib(); $quickSortLib->sortInplace($my_array, 0, count($my_array) - 1); echo implode(", ", $my_array); } } ?>
|