Quicksort

Quicksort

Donny
April 21, 2018
2023
-

Tags in blue are handcrafted tags; Tags in green are generated using AutoTag.

Time Complexity

With partition, the elements compared each time are as follow:

n, n/2, n/2, n/4, n/4, n/4, n/4, ..., 1, 1, ..., 1 (n ones)

And their sum is:

n, n, n, ..., n

But how much n?

Since n is divided to 1 by 2, there sure is log2(n) number of n.

So the time complexity is: n*log2(n)

Unique-elements sorting implement

``````algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot

do
j := j - 1
while A[j] > pivot

if i >= j then
return j

swap A[i] with A[j]
``````

My C++ implement:

``````#include <cstdio>
#include <algorithm>

int partition(int *arr, int lo, int hi)
{
int pivot = arr[lo];
while (true)
{
while (arr[lo] < pivot) ++lo;
while (arr[hi] > pivot) --hi;
if (lo >= hi) return lo;
std::swap(arr[lo], arr[hi]);
}
}

void quicksort(int *arr, int lo, int hi)
{
if (lo >= hi) return;
int p = partition(arr, lo, hi);
quicksort(arr, lo, p-1);
quicksort(arr, p+1, hi);
}

int main()
{
int A[] = {
15, 16, 10, 9, 4, 3, 6, 1, 7, 2, 8, 14
};
const int len = sizeof(A)/sizeof(A[0]);
quicksort(A, 0, len-1);
for (int a = 0; a < len; ++a)
printf("%d ", A[a]);
return 0;
}
``````

Duplicate-elements sorting implement

At first, I coded something like this:

``````#include <cstdio>

int partition(int *arr, int f, int l)
{
int lo = f, hi = l;
int pivot = lo;
int pivot_val = arr[lo];
while (lo < hi)
{
while (hi > lo && arr[hi] >= pivot_val) --hi;
arr[pivot] = arr[hi]; pivot = hi;
while (lo < hi && arr[lo] <= pivot_val) ++lo;
arr[pivot] = arr[lo]; pivot = lo;
}
arr[pivot] = pivot_val;
return pivot;
}

void quick_sort(int *arr, int f, int l)
{
if (f >= l) return;
int p = partition(arr, f, l);
quick_sort(arr, f, p-1);
quick_sort(arr, p+1, l);
}

int main()
{
int arr[] = {
1, 18, 10, 6, 16, 8, 6, 2, 7, 3, 16, 21
};
const int len = sizeof(arr)/sizeof(arr[0]);
quick_sort(arr, 0, len-1);
for (int a : arr) printf("%d ", a);
printf("\n");
return 0;
}
``````

It works, but might swap the pivot elements unnecessarily. So I add same if-statements:

``````--- a/src/duplicate-1.cpp
+++ b/src/duplicate-2.cpp
@@ -9,8 +9,10 @@ int partition(int *arr, int f, int l)
while (lo < hi)
{
while (hi > lo && arr[hi] >= pivot_val) --hi;
+        if (lo == hi) break;
arr[pivot] = arr[hi]; pivot = hi;
while (lo < hi && arr[lo] <= pivot_val) ++lo;
+        if (lo == hi) break;
arr[pivot] = arr[lo]; pivot = lo;
}
arr[pivot] = pivot_val;
``````

It also passed the test.

Then I wonder if I can make it more concise. And I found out the pivot variable is unnecessary.

``````--- a/src/duplicate-2.cpp
+++ b/src/duplicate.cpp
@@ -4,19 +4,16 @@
int partition(int *arr, int f, int l)
{
int lo = f, hi = l;
-    int pivot = lo;
int pivot_val = arr[lo];
while (lo < hi)
{
while (hi > lo && arr[hi] >= pivot_val) --hi;
-        if (lo == hi) break;
-        arr[pivot] = arr[hi]; pivot = hi;
+        if (lo != hi) arr[lo] = arr[hi];
while (lo < hi && arr[lo] <= pivot_val) ++lo;
-        if (lo == hi) break;
-        arr[pivot] = arr[lo]; pivot = lo;
+        if (lo != hi) arr[hi] = arr[lo];
}
-    arr[pivot] = pivot_val;
-    return pivot;
+    arr[lo] = pivot_val;
+    return lo;
}
``````

Finally, with unit test, the final code looks like this:

``````#include <cstdio>

int partition(int *arr, int f, int l)
{
int lo = f, hi = l;
int pivot_val = arr[lo];
while (lo < hi)
{
while (hi > lo && arr[hi] >= pivot_val) --hi;
if (lo != hi) arr[lo] = arr[hi];
while (lo < hi && arr[lo] <= pivot_val) ++lo;
if (lo != hi) arr[hi] = arr[lo];
}
arr[lo] = pivot_val;
return lo;
}

void quicksort(int *arr, int f, int l)
{
if (f >= l) return;
int p = partition(arr, f, l);
quicksort(arr, f, p-1);
quicksort(arr, p+1, l);
}

#include <cstdlib>
#include <ctime>
#include <memory>
#define BOOST_TEST_MODULE quicksort
#include <boost/test/included/unit_test.hpp>

void print_array(int *arr, int len)
{
for (int a=0; a<len; ++a) printf("%d ", arr[a]);
printf("\n");
}

void test_once()
{
const int maxlen = 100000;
const int maxval = 1000;

const int len = rand()%(maxlen/10*9) + maxlen/10 + 1;
std::unique_ptr<int[]> arr_ptr(new int[len]);
int *arr = arr_ptr.get();

for (int a=0; a<len; ++a) arr[a] = rand()%maxval;
quicksort(arr, 0, len-1);

for (int a=1; a<len; ++a)
{
if (arr[a]<arr[a-1])
{
printf("Error!\n");
print_array(arr, len);
}
BOOST_REQUIRE(arr[a] >= arr[a-1]);
}
}

BOOST_AUTO_TEST_CASE( test_quicksort )
{
const int max_test_times = 200;

for (int a=1; a<=max_test_times; ++a) {
printf("Performing %d sub-test...\n", a);
test_once();
}
}

BOOST_AUTO_TEST_CASE( single_test )
{
int arr[] = {
1, 18, 10, 6, 16, 8, 6, 2, 7, 3, 16, 21
};
int sorted_arr[] = {
1, 2, 3, 6, 6, 7, 8, 10, 16, 16, 18, 21
};
const int len = sizeof(arr)/sizeof(arr[0]);

quicksort(arr, 0, len-1);

for (int a=0; a<len; ++a)
BOOST_REQUIRE(arr[a] == sorted_arr[a]);

printf("Result of a small sort case:\n");
for (int a : arr) printf("%d ", a);
printf("\n");
}
``````

Output:

``````\$ make test-duplicate
g++ src/duplicate.cpp -o bin/duplicate -std=c++11
cd bin && ./duplicate
Running 2 test cases...
Performing 1 sub-test...
Performing 2 sub-test...
Performing 3 sub-test...
Performing 4 sub-test...
Performing 5 sub-test...
...
Performing 196 sub-test...
Performing 197 sub-test...
Performing 198 sub-test...
Performing 199 sub-test...
Performing 200 sub-test...
Result of a small sort case:
1 2 3 6 6 7 8 10 16 16 18 21

*** No errors detected
``````