Need help with In-Place Quick Sort Implementation

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!

You’re asking this in a Codeigniter forum?

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

---

CodeIgniter Wizard (CRUD code generator for Mac) instantly scaffolds Bootstrap-based web applications with an administrative interface (admin templates include Bootstrap5)

---