Quick Sort Algorithm

 

The algorithm of quick sort takes time that is proportional to nlog2n, and hence it is very quick to sort an array by using quick sort algorithm. Quick sort is a divide and conquer algorithm in which the array is divided into two parts and each part will be sorted separately and after that the array will be merged into a single array. In other words we can conclude this into simpler points as follows:

  1. Splitting the array into two parts
  2. Then sorting the two parts of the array separately
  3. After this merge the two arrays into one single array

When we are sorting using divide and conquer the following questions arise:

  1. Why the halved arrays are not divided into further halves?
  2. The quarters in half?
  3. When we should stop?

The array or the list is stopped dividing into halves when we reach to the single element of the array. Similarly quick sort is based on the idea of splitting the arrays around a pivot point. The algorithm of quick sorting requires a less time space and is very fast to sort the array. The array is divided and has three main parts or components that are the elements that are less than the pivot point and the pivot point and the element that are greater than the pivot point.

The elements that are less than pivot point are placed to the left side of pivot point and the elements that are greater than pivot point are placed to the right of the pivot point.

 

How quick sort works:

Consider the following figure to comprehend the idea of quick sorting to sort an array of element:

4 12 10 8 5 2 11 7 3

Now we set the fifth element that is 5 as the pivot point of this array. Now this pivot point is swapped with the lat element of the array as the last element of the array is smallest of all. The new array will look like the following:

The new array will look like the following

In the figure we have two indexes that are ‘low’ and ‘high’. The index ‘low’ is started from the 0th position of the array and it goes to the (n-1) position of the array. Then we use a loop and we search for the element that is greater than the pivot point. As 4 is smaller than 5 (pivot point) therefore, we increment the index ‘low’ to the next position. Now index low is pointing to the element ‘12’ of the array.

12

12 is greater than 5 (pivot point), it is stopped here and we start from the other end that is from the index ‘high’. The ‘high’ index is moved towards left from n-1 position to 0 position of the array. When the high index is coming towards 0 position, the elements that are smaller than 5 (pivot point) are searched. As 11 and 7 are greater than 5 therefore the high index is moved to the element 2 and it is stopped here. The array looks like the following:

The array looks like the following

Now low is at element 12 of array and high is at element 2 of array and both of these indexes are stopped. High is smaller than pivot point and low is greater than pivot point. In the next step both of them are swapped that is high and low are swapped. Now our array will look like the following:

Now our array will look like the following

Now high is at element 10 and low is at element 3. We again move to index low and we will start moving to right searching for the element which is greater than 5 (pivot point). In the same way high is moved to the left side and we are finding an element which is smaller than 5 (pivot point).

As low is at element 10 and the element 10 is greater than 5 and high is at element 3 which is smaller than 5 therefore both of these elements will be swapped. The new array will look like:

 

3 and 10

Now in the next iteration, the indexes low and high will cross each other.

8

The element that is at the crossing position is swapped with the pivot number which is 5 when the high pointer crosses the low pointer. The new array will look like the following:

5

The above array is not sorted but the pivot number that is 5 has got its correct position. In the above array the elements to the left side of the array should be smaller than 5 and the elements that are to the right side of the array should be greater than 5.

But it should be noted that the numbers or elements to the left side are smaller but they are not sorted and similar is the case with the elements to the right side of the pivot number 5. Now these parts will be sorted using recursively quick sort, in this way we will have the entire array sorted.

 

Sorting using Quick Sort Algorithm:

The following is the algorithm of sorting using quick sort:

ALGORITHM:

voidquicksorting (intarr [], int s, int e)

{

if (s < e)

{

int n;

n = division (arr, s, e);

quicksorting (arr, s, n);

quicksorting (arr, n + 1, e);

}

}

int division (intarr [], int s, int e)

{

int x, y, pivot, temp;

pivot = arr [s];

x = s;

y = e;

while (1)

{

while (arr [x] < pivot &&arr [x] != pivot)

x ++;

while (arr [y] > pivot &&arr [y] != pivot)

y –;

if (x < y)

{

temp = arr [x];

arr [x] = arr [y];

arr [y] = temp;

}

else

{

return y;

}

}

}

In the above algorithm, there is a method that is void quicksorting () which is used to sort the array using quick sort. In the method or function we have passed an array that is to be sorted and a variable s which is used as the starting index of the array that is its value will be 0. And the variable e is used for the last index of the array. The remaining algorithm works the same as described earlier.

 

Complexity Analysis of Quick Sort:

The following are the cases for time complexity of quick sorting:

Worst case Time complexity:

The worst case time complexity is o (n ^ 2)

Best case Time Complexity:

The best case time complexity is o (n log n)

Average Time Complexity:

The average case time complexity is o (n log n)

Space Complexity:

The space complexity is o (1)

The algorithm of the quick sorting takes a very less space and O (n log n) requires some extra space. When we use the algorithm of quick sorting, the occurrence of two similar elements in the list or array may get changed while sorting the array or the list. In other words we can say that quick sorting is not stable as it can change the occurrence of two similar elements in the list or in the array.