Quicksort

The quicksort divides the array into two groups and sorts the either group (conquering). It divides the array based on a random element from the array.

1. Check if array has at least 2 elements
2. Select the first element in the array (the pivot)

3. Move all elements that are less than or equal to the selected element to the left of the pivot element and move all the elements greater to the right of it (do this with the partition function)

   1. Set a variable low as the first index and a variable high as the last index.
   2. Keep on incrementing low until its value is greater than the pivot value.
   3. Keep on decrementing high until its value is less than or equal to the pivot value.
   4. If low’s value is less than high’s value, swap the elements.
   5. Repeat steps ii-iv until high is less than or equal to low.
   6. When high is less than or equal to low, swap the pivot element with the high element.

4. Repeat 1-3 each sub-array.

Let’s try this with an array of numbers.

*2* 6 5 1 4 3
1. Select a Moses (``pivot``).
2. Partition the array based on Moses.
2 6 5 1 4 3
moses = 2
low = 0 (2)     index (value)
high = 5 (3)
low = 1 (6)     greater than moses
high = 4 (4)
high = 3 (1)     less than moses
Low (1) < high (3), so swap 6 and 1
2 1 5 6 4 3
low = 1 (1)
low = 2 (5)     greater than moses
high = 3 (6)
high = 2 (5)
high = 1 (1)    less than moses
Low (2) not < high (1), break out of loop
Swap moses with high
1 2 5 6 4 3

3. Repeat on left sub-array.
1
Since it has one element, return.

4. Repeat on right sub-array
5 6 4 3
moses = 5
low = 0 (5)
high = 3 (3)
low = 1 (6)     greater than moses
high = 3 (3)    less than moses
Low (1) < high (3), so swap 6 and 3
5 3 4 6
low = 1 (3)
low = 2 (4)
low = 3 (6)     greater than moses
high = 3 (6)
high = 2 (4)     less than moses
Low (3) not < high (2), break out of loop
Swap moses with high
4 3 5 6


5. Repeat on this sub-array's left sub-array
4 3
moses = 4
low = 0 (4)
high = 1 (3)
low = 1 (3)
low = 2 (?)     index greater than high
high = 1 (3)    less than moses
Low (2) not < high (1), break out of loop
Swap moses and high
3 4

5. Repeat on sub-array's right sub-array
6
Since it has one element, return.

foo = 3 4 5 6
Return

foo = 1 2 3 4 5 6
Return
Done!

Here is the code:

void quick(int foo[], int first, int last)     // Indexes of first and last elements you wish to sort
{
     if (last - first >= 1)     // If there are at least two elements
     {
          int moses;     // Index of partitioner
          moses = partition(foo, first, last);
          quick(foo, first, moses - 1);     // left sub-array
          quick(foo, moses + 1, last);     // right sub-array
     }
}

int partition(int sea[], int low, int high)
{
     int pivotIndex = low;
     int pivotValue = sea[low];     // Set pivotValue to first element
     do
     {
          while (low <= high && sea[low] <= pivotValue)     // Find first value greater than pivotValue
               low++;
          while (sea[high] > pivotValue)     // Find the first value less than or equal to the pivotValue
               high--;
          if (low < high)
               swap(sea[low], sea[high);
     }
     while (low < high);     // Continue looping until high has a lesser value than low
     swap(sea[pivotIndex], sea[high]);     // Swap the pivotValue with this one because we know that high points to the correct place for the pivot
     pivotIndex = high;     // Get the index of the high because that's the pivot's index now
     return pivotIndex;
}

What is the big-o? You exponentially split the array up (O(log(n))) and loop through all the elements for at most O(n) times. On average it is O(n * log(n)).

void quick(int foo[], int first, int last)
{
     if (last - first >= 1)
     {
          int moses;     // Index of partitioner
          moses = partition(foo, first, last);
          quick(foo, first, moses - 1);     // O(log(n) / 2)
          quick(foo, moses + 1, last);     // O(log(n) / 2)
     }
}     // O(n * log(n) / 2 + n * log(n) / 2) = O(n * log(n))

int partition(int sea[], int low, int high)
{
     int pivotIndex = low;
     int pivotValue = sea[low];
     do
     {
          while (low <= high && sea[low] <= pivotValue)
               low++;
          while (sea[high] > pivotValue)
               high--;
          if (low < high)
               swap(sea[low], sea[high);
     }
     while (low < high);     // O(n), at most n steps
     swap(sea[pivotIndex], sea[high]);
     pivotIndex = high;
     return pivotIndex;
}     // O(n)

In the worst case it is O(n^2). This is when you have an already ordered array, because you will split up the array n times instead of log(n).

   1 2 3 4 5 6
1     2 3 4 5 6
    2     3 4 5 6
        3     4 5 6
             4     5 6
                  5   6

The quicksort is unstable.

2(a) 2(b) 1 moses = 2(a) low = 0 (2(a)) high = 2 (1) low = 1 (2(b)) low = 2 (1) low = 3 (?) greater than high high = 2 (1) less than high Low (3) is not < high (2), break out of loop Swap moses and high 1 2(b) 2(a) [after evaluating left sub-array] Done!

Notice that the 2s have not retained their original order.