0

Why doesn't a different pivot, besides high, work for this code? Is there a code for quicksort that can handle high/low/random pivots or does it have to be a separate algorithm ? I think that this is using Lomuto's partitioning scheme.

/* C implementation QuickSort */
#include <stdio.h>

// A utility function to swap two elements
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

/* The main function that implements QuickSort
 arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);

        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main()
{
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
begginer3
  • 13
  • 5
  • 2
    From what I've seen, you can write a quick sort that uses either the first or the last index as the pivot. To get a random pivot, the code usually seems to choose an entry at random and swap it with either the first or last index, and that becomes the pivot. You might look at [Quicksort: Choosing the pivot](http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot) for more information on pivot selection algorithms. – Jonathan Leffler Apr 20 '17 at 04:44
  • @JonathanLeffler That's certainly the way I've coded them in the past (i usually use the high end). Its just easier because there is zero chance of your pivot being walked on if you use a storage slot *during* the sweep. The OP's code, however, looks odd as it never actually uses the final slot for storage while sweeping, relying instead on a local temp. That last swap looks odd (not that I've tested it). – WhozCraig Apr 20 '17 at 04:49
  • @WhozCraig If it was up to me, I would just take this algorithm and be done with it. But I have to do it using low/high/rand pivot. And I cant seem to get this to work with anything else than a high pivot. Even in my own program based on the wikipedia pseudocode. There must be some key differences between the one that uses low and the one that uses high. – begginer3 Apr 20 '17 at 04:54
  • Yeah, the indexing becomes a pain when you use the same base array but multiple indexes to refer to the partition windows. With C and C++ using pointer arithmetic on the base address for the recursion throws all that out, making the algorithm *far* easier to implement and understand imho, at least for C programmers. – WhozCraig Apr 20 '17 at 05:35

0 Answers0