Quick Sort

 

Quicksort is another divide and conquer algorithm. Quicksort is based on the idea of partitioning (splitting) the list around a pivot or split value. Quicksort is also a divide and conquer algorithm. We see pictorially, how the quick sort algorithm works. Suppose we have an array as shown in the figure Fig 45.33.

We select an element from the array and call it the pivot. In this array, the pivot is the middle element 5 of the array. Now, we swap this with the last element 3 of the array. The updated figure of the array is shown in Fig 45.34.

As shown in Fig 45.34, we used two indexes low and high. The index low is started from 0^th position of the array and goes towards right until n-1^th position. Inside this loop, an element that is bigger than the pivot is searched. The low index is incremented further as 4 is less than 5.

low is pointing to element 12 and it is stopped here as 12 is greater than 5. Now, we start from the other end, the high index is moved towards left from n-1^th position to 0. While coming from right to left, we search such an element that is smaller than 5. Elements 7 and 11 towards left are greater than 5, therefore, the high pointer is advanced further towards left. high index is stopped at the next position as next element 2 is smaller than 5. Following figure Fig 45.36 depicts the latest situation.

Both of the indexes have been stopped, low is stopped at a number 12 that is greater than the pivot and high is stopped at number 2 that is smaller than the pivot. In the next step, we swap both of these elements as shown in Fig 45.37.

Note that our pivot element 5 is still there at its original position. We again go to index low and start moving towards right, trying to find a number that is greater than the pivot element 5. It immediately finds the next number 10 greater than 5. Similarly, the high is moved towards left in search to find an element smaller than the pivot element 5. The very next element 3 is smaller than 5, therefore, the high index stops here. These elements 10 and 3 are swapped, the latest situation is shown in Fig 45.38.

Now, in the next iteration both low and high indexes cross each other. When the high pointer crosses the low pointer, we stop it moving further as shown in Fig 45.39 and swap the element at the crossing position (which is 8) with the pivot number as shown in Fig 45.40.

This array is not sorted yet but element 5 has found its destination. The numbers on the left of 5 should be smaller than 5 and on right should be greater than it and we can see in Fig 45.40 that this actually is the case here. Notice that smaller numbers are on left and greater numbers are on right of 5 but they are not sorted internally.

Next, we recursively quick sort the left and right parts to get the whole array sorted.

 

Now, we see the C++ code of quick sort.

void quickSort(int array[], int size) { int index; if (size > 1) { index = partition(array, size); quickSort(array, index); quickSort(array+index+1, size - index-1); } } int partition(int array[], int size) { int k; int mid = size/2; int index = 0; swap(array, array+mid); for (k = 1; k < size; k++){ if (array[k] < array[0]){ index++; swap(array+k, array+index); } } swap(array, array+index); return index; }

An array and its size are passed as arguments to the quickSort function. The function declared a local variable index and the size of the array is checked in the next statement. If the size of the array is more than 1 then the function does the recursive calling mechanism to sort the array. It divides the array into two parts by choosing the pivot element. In the subsequent calls, firstly the left side is sorted and then the right side using the recursive mechanism. Quicksort algorithm is very elegant and it can sort an array of any size efficiently. It is considered one of the best general purpose algorithms for sorting. This normally is preferred sorting method being nlog₂n and inplace algorithm.

Technorati Tags: quick sort algorithm,quick sort algo,quick sort data structure