Quick sort explained with simple example

Quick sort is one of the fastest sorting algorithm, which works on Divide and Conquer algorithm. In this sorting algorithm, an element is picked as a pivot element and list is divided into sub-lists around the pivot element. These divided sub-lists finally sorted into which results into sorted initial list.

Pros:
1) Faster algorithm and best performance O(nlogn) is for worst distribution case scenario.
2) Simple implementation due to recursive nature.
3) No extra space is needed.

Cons:
1) Worst case scenario performance is O(n*n).
2) Not good for Linked list kind of sorting data where memory is not contiguous.

Algorithm explained via example:

Let us take an example array “76, 4, 65, 33, 23, 10, 44, 38, 97, 100, 1, 59”. Now we will run through this array with quick sort algorithm to understand how it works.

There are several ways to pick pivot element like the first element or last element or the center element etc. Here, we are picking the last element as pivot.

First traversal (divide the list into two halves across the pivot/last element “59” after placing it to its correct place)
1, 4, 38, 33, 23, 10, 44, 59, 97, 100, 76, 65 —> pivot “59” is placed at its correct position. Now divide it into two sublists (left and right)

Second traversal (divide the left list of “59” by choosing pivot/last element “44” after placing it to its correct place)
1, 4, 38, 33, 23, 10, 44, 59, 97, 100, 76, 65 —> pivot “44” is placed at its correct position. Now divide it into two sublists.

Third traversal (divide the left list of “44” by chossing pivot/last element “10” after placing it in correct place)
1, 4, 10, 33, 23, 38, 44, 59, 97, 100, 76, 65 —> pivot “10” is placed at its correct position. Now divide it into two sublists.

Fourth traversal (divide the left list of “10” by chossing pivot/last element “4” after placing it in correct place)
1, 4, 10, 33, 23, 38, 44, 59, 97, 100, 76, 65 —> pivot “4” is placed at its correct position. Now divide it into two sublists.

Fifth traversal (divide the left list of “4” by chossing pivot/last element “1” after placing it in correct place)
1, 4, 10, 33, 23, 38, 44, 59, 97, 100, 76, 65 —> pivot “1” is placed at its correct position. Now divide it into two sublists.

Sixth traversal (divide the right list of “10” by chossing pivot/last element “23” after placing it in correct place)
1, 4, 10, 23, 33, 38, 44, 59, 97, 100, 76, 65 —> pivot “23” is placed at its correct position. Now divide it into two sublists.

Seventh traversal (divide the right list of “59” by chossing pivot/last element “65” after placing it in correct place)
1, 4, 10, 23, 33, 38, 44, 59, 65, 100, 76, 97 —> pivot “65” is placed at its correct position. Now divide it into two sublists.

Eigth traversal (divide the right list of “65” by chossing pivot/last element “97” after placing it in correct place)
1, 4, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100 —> pivot “97” is placed at its correct position. Now divide it into two sublists.

At this point, left and right sublist of element “97” contains single element and is already sorted. So, no more traversal required.
Now the list is sorted.

Let’s have a look at the sample program for quick sort.

void printArray(int a[] )
{
	for (int i = 0; i < 12; i++)
	{
		cout << a[i] << ", ";
	}
	cout << endl; } void quickSort(int array[], int startIndex, int endIndex) { if (startIndex ><span data-mce-type="bookmark" style="display: inline-block; width: 0px; overflow: hidden; line-height: 0;" class="mce_SELRES_start"></span>= endIndex)
		return;

	int pivot = array[endIndex];
	int lowIndex = startIndex;
	int highIndex = endIndex - 1;
	bool flag = true;

	while (true)
	{
		while (lowIndex < endIndex) { if (array[lowIndex] > pivot)
				break;
			lowIndex++;
		}

		while (highIndex > 0 && highIndex >= startIndex)
		{
			if (array[highIndex] < pivot)
				break;
			highIndex--;
		}

		if (lowIndex < highIndex)
		{
			int temp = array[lowIndex];
			array[lowIndex] = array[highIndex];
			array[highIndex] = temp;
		}
		else
			break;
	}


	int temp = array[lowIndex];
	array[lowIndex] = pivot;
	array[endIndex] = temp;

	printArray(array);

        // Enable below code to see how index is being chosen while quick sort is progressed.
        //std::cout << "Start: " << startIndex << "End: " << endIndex << std::endl;

	// Call quickSort again
	quickSort(array, startIndex, lowIndex - 1);
	quickSort(array, lowIndex + 1, endIndex);
}

void quickSortCaller()
{
	int a[] = { 76,4,65,33,23,10,44,38,97,100,1,59 };
	cout << "QuickSort Sort" << endl;
	cout << "Initial array" << endl;
	printArray(a);

	quickSort(a,0,11);
	printArray(a);
}

int main()
{
    quickSortCaller();
}

Output of the above program is as follows:

QuickSort Sort
Initial array
76, 4, 65, 33, 23, 10, 44, 38, 97, 100, 1, 59,
1, 4, 38, 33, 23, 10, 44, 59, 97, 100, 76, 65,
1, 4, 38, 33, 23, 10, 44, 59, 97, 100, 76, 65,
1, 4, 10, 33, 23, 38, 44, 59, 97, 100, 76, 65,
1, 4, 10, 33, 23, 38, 44, 59, 97, 100, 76, 65,
1, 4, 10, 33, 23, 38, 44, 59, 97, 100, 76, 65,
1, 4, 10, 23, 33, 38, 44, 59, 97, 100, 76, 65,
1, 4, 10, 23, 33, 38, 44, 59, 65, 100, 76, 97,
1, 4, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100,
1, 4, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100,

Algorithm performance:

Time complexity:
Quick sort is affected by data distribution.

Time complexity for best case(random data distribution) is O(nlogn).
Worst case(data is already sorted) scenario is O(n*n).

Space complexity:
Since, no extra space is needed for this sorting algorithm. Hence, Space complexity is O(1).