Question

I am trying to implement this version of quicksort in C/c++ but I am getting stuck. Below is how the algorithm is supposed to work. This is the partitioning scheme I am trying to implement.

17, -10, 7, 19, 21, 23, -13, 31, 59
# ^ ^
start

17, -10, 7, 19, 21, 23, -13, 31, 59
# ^ ^
move left pointer to first element larger than pivot. 3 compares

17, -10, 7, 19, 21, 23, -13, 31, 59
# ^ ^
move right pointer to first element smaller than pivot. 3 compares
  
17, -10, 7, -13, 21, 23, 19, 31, 59
# ^ ^
swap elements at pointer
  
17, -10, 7, -13, 21, 23, 19, 31, 59
# ^ ^
move left pointer to first element larger than pivot. 1 compare
  
17, -10, 7, -13, 21, 23, 19, 31, 59
# ^^
move right pointer to first element smaller than pivot (but not past left   
pointer. 1 compare

-13, -10, 17, 17, 21, 23, 19, 31, 59
#

I am trying to implement this version of Quicksort in code but I am having trouble implementing it. Can i get some help? This is what I have so far:

int partition(int arr[], int low, int high)
{  
int pivot = arr[low];
int k = low;
   int j = high;

   for (int i = low + 1; i < high; i++)
   {
       if (pivot < arr[i]) // if the pivot is less than number go to left
       {
           for (j; j > i + 1; j--)
           {
if (i >= j)
return j;

               if (pivot > arr[j])
               {
                   swap(arr[i], arr[j]); // swap the two values
               }
           }
       }  
   }

   return 1;
}

void quickSort(int arr[], int low, int high)
{
if (low < high)
{   
int pi = partition(arr, low, high);

  
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}

Answer 1

C CODE

/* 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[] = {17, -10, 7, 19, 21, 23, -13, 31, 59};
   int n = sizeof(arr)/sizeof(arr[0]);
   quickSort(arr, 0, n-1);
   printf("Sorted array: n");
   printArray(arr, n);
   return 0;
}