H Lecture Notes - Lecture 3: Sorting Algorithm, Quicksort, Merge Sort
12 Sep 2021
Department
Course
Professor
The algorithm was developed by a British computer scientist Tony Hoare in 1959. The name "Quick
Sort" comes from the fact that, quick sort is capable of sorting a list of data elements significantly
faster (twice or thrice faster) than any of the common sorting algorithms. It is one of the most
efficient sorting algorithms and is based on the splitting of an array (partition) into smaller ones and
swapping (exchange) based on the comparison with 'pivot' element selected. Due to this, quick sort is
also called as "Partition Exchange" sort. Like Merge sort, Quick sort also falls into the category of
divide and conquer approach of problem-solving methodology.
Explanation
Taking the analogical view in perspective, consider a situation where one had to sort the papers
bearing the names of the students, by name from A-Z. One might use the approach as follows:
Select any splitting value, say L. The splitting value is also known as Pivot.
1.
Divide the stack of papers into two. A-L and M-Z. It is not necessary that the piles should be
equal.
2.
Repeat the above two steps with the A-L pile, splitting it into its significant two halves. And M-Z
pile, split into its halves. The process is repeated until the piles are small enough to be sorted
easily.
3.
Ultimately, the smaller piles can be placed one on top of the other to produce a fully sorted and
ordered set of papers.
4.
The approach used here is reduction at each split to get to the single-element array.
5.
At every split, the pile was divided and then the same approach was used for the smaller piles
by using the method of recursion.
6.
Technically, quick sort follows the below steps:
Step 1 − Make any element as pivot
Step 2 − Partition the array on the basis of pivot
Step 3 − Apply quick sort on left partition recursively
Step 4 − Apply quick sort on right partition recursively
Quick Sort Example:
Problem Statement
Consider the following array: 50, 23, 9, 18, 61, 32. We need to sort this array in the most efficient
manner without using extra place (in place sorting).
Solution
Step 1:
Make any element as pivot: Decide any value to be the pivot from the list. For convenience of
•
Quick sort
Friday, July 16, 2021
10:00 AM
code, we often select the rightmost index as pivot or select any at random and swap with
rightmost. Suppose for two values “Low” and “High” corresponding to the first index and last
index respectively.
In our case low is 0 and high is 5.
○
Values at low and high are 50 and 32 and value at pivot is 32.
○
Partition the array on the basis of pivot: Call for partitioning which rearranges the array in such
a way that pivot (32) comes to its actual position (of the sorted array). And to the left of the
pivot, the array has all the elements less than it, and to the right greater than it.
In the partition function, we start from the first element and compare it with the pivot.
Since 50 is greater than 32, we don’t make any change and move on to the next element
23.
○
Compare again with the pivot. Since 23 is less than 32, we swap 50 and 23. The array
becomes 23, 50, 9, 18, 61, 32
○
We move on to the next element 9 which is again less than pivot (32) thus swapping it
with 50 makes our array as 23, 9, 50, 18, 61, 32.
○
Similarly, for next element 18 which is less than 32, the array becomes 23, 9, 18, 50, 61, 32.
Now 61 is greater than pivot (32), hence no changes.
○
Lastly, we swap our pivot with 50 so that it comes to the correct position.
○
•
Thus the pivot (32) comes at its actual position and all elements to its left are lesser, and all elements
to the right are greater than itself.
Step 2: The main array after the first step becomes
23, 9, 18, 32, 61, 50
Step 3: Now the list is divided into two parts:
Sublist before pivot element
1.
Sublist after pivot element
2.
Step 4: Repeat the steps for the left and right sublists recursively. The final array thus becomes
9, 18, 23, 32, 50, 61.
The following diagram depicts the workflow of the Quick Sort algorithm which was described above.
Document Summary
The algorithm was developed by a british computer scientist tony hoare in 1959. Sort" comes from the fact that, quick sort is capable of sorting a list of data elements significantly faster (twice or thrice faster) than any of the common sorting algorithms. It is one of the most efficient sorting algorithms and is based on the splitting of an array (partition) into smaller ones and swapping (exchange) based on the comparison with "pivot" element selected. Due to this, quick sort is also called as "partition exchange" sort. Like merge sort, quick sort also falls into the category of divide and conquer approach of problem-solving methodology. Taking the analogical view in perspective, consider a situation where one had to sort the papers bearing the names of the students, by name from a-z. Select any splitting value, say l. the splitting value is also known as pivot. It is not necessary that the piles should be equal.
