Need help with In-Place Quick Sort Implementation

Need help with In-Place Quick Sort Implementation - Printable Version

+- CodeIgniter Forums (https://forum.codeigniter.com)
+-- Forum: General (https://forum.codeigniter.com/forumdisplay.php?fid=1)
+--- Forum: Lounge (https://forum.codeigniter.com/forumdisplay.php?fid=3)
+--- Thread: Need help with In-Place Quick Sort Implementation (/showthread.php?tid=88098)

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);
    }
}
?>