This post is regarding quicksort…

In quicksort algo, we choose a pivot element and then brings all the smaller elements to the left of the list and biggers one on the right…
Then we go on processing the same with left and right sub list dividing the original list by the pivot element.

In each pass the pivot acquires its correct position.

This yields us the sorted list in the end.

Its best case and average case complexity is nlog(n) and worst case to be (n square), where the list is already sorted or pivot is unique maximum or minimum.

It is not in-place and is not a stable sort…

An implementation in C++ is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

/*
 * Quick sort algorithm implementation.
 * Best case: nlog(n)
 * Average case: nlog(n)
 * Worst case: n square.
 */
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
 
#include <stdarg.h>          /* For variable number of arguments */
 
#define MAXLISTSIZE 100      /* Can sort upto MAXLISTSIZE elements */
 
using namespace::std;
 
/*
 * Quicksort implemented as a class..
 */
class Quicksort {
   private:
      int quickList[MAXLISTSIZE];                              /* Our quick list of elements */
      int quickCounter;                                        /* Our counter for this list */
      int quickSort ( int sortingList[], int start, int end ); /* Performs quick sort algorithm */
   public:
      Quicksort ();                                            /* Our constructor function */
      int performQuickSort ();                                 /* Calls quick sort algo from outside */
      int addElement ( int numOfElements, ... );               /* Adds n elements to our quick list to sort */
};
 
/*
 * Consrtuctor definiton..
 */
Quicksort::Quicksort () {
   quickCounter = 0;
}
 
/*
 * Adds numOfElements in the quick list to be sorted.
 */
int Quicksort::addElement ( int numOfElements, ... ) {
   va_list numbers;
   va_start ( numbers, numOfElements );
   cout << "Adding: " << endl;
   for ( int i = 0 ; i < numOfElements ; i++ ) {
      quickList[quickCounter++] = va_arg ( numbers, int );
      cout << quickList[quickCounter-1] << "\t";
   }
   cout << endl;
   return EXIT_SUCCESS;
}
 
/*
 * Performs quick sort algo as recurcive function..
 * Learn more: http://en.wikipedia.org/wiki/Quicksort
 */
int Quicksort::quickSort ( int sortingList[], int start, int end ) {
   if ( (end - start) <= 1 ) {
      return 0;
   }
   int pivotIdx = (end+start) / 2;
   int lessCtr = 0; int moreCtr = MAXLISTSIZE+2;
   int tempList[(MAXLISTSIZE*2)+1];
   for ( int i = 0 ; i < MAXLISTSIZE*2 ; i++ ) {
      tempList[i] = 0;
   }
   tempList[MAXLISTSIZE+1] = sortingList[pivotIdx];
   for ( int i = start ; i < end ; i++ ) {
      if ( sortingList[i] < sortingList[pivotIdx] ) {
         tempList[lessCtr++] = sortingList[i];
      }
      else if ( sortingList[i] > sortingList[pivotIdx] ) {
         tempList[moreCtr++] = sortingList[i];
      }
   }
   int j = start;
   for ( int i = 0 ; i < MAXLISTSIZE*2 ; i++ ) {
      if ( tempList[i] != 0 ) {
         sortingList[j++] = tempList[i];
      }
   }
   quickSort ( quickList, 0, pivotIdx );
   quickSort ( quickList, pivotIdx+1, end );
   return EXIT_SUCCESS;
}
 
/*
 * Caller function for quicksort..
 */
int Quicksort::performQuickSort () {
   cout << "Quick sorting..." << endl;
   quickSort ( quickList, 0, quickCounter );
   for ( int i = 0 ; i < quickCounter ; i++ ) {
      cout << quickList[i] << "\t";
   }
   cout << endl;
}
 
/*
 * Test case..
 */
int main () {
   Quicksort qs;
   /* Sorting 11 elements as specified after argument 1.. */
   qs.addElement ( 11, 2, 4, 3, 7, 11, 9, 13, 8, 20, 15, 5 );
   qs.performQuickSort ();    /* Do quicksort.. */
   return 0;
}

Sample run:
[shamail@macintosh Quicksort/]$ ./a.out
Adding:
2 4 3 7 11 9 13 8 20 15 5
Quick sorting…
2 3 4 5 7 8 9 11 13 15 20

:-) Read more at: http://en.wikipedia.org/wiki/Quicksort

Post to Twitter Tweet This Post