Quick Sort
Quick Sort
Is an algorithm based on the divide and conquer
approach in which the array is split into
subarrays and these sub-arrays are recursively
called to sort the elements.
Divide and Conquer approach:
DIVIDE
- The array is divide into subparts taking pivot as the partitioning point. The element smaller
than the pivot are placed to the left of the pivot and the elements greater than the pivot are placed
to the right.
CONQUER
- The left and the right subparts are again partitioned using the by electing pivot elements for
them. This can be achieved by recursively passing the subparts into the algorithm,
COMBINE
- This step does not play a significant role in quicksort. The array is already sorted at the end of
the conquer step.
How QuickSort Works?
1. A pivot element is chosen from the array. You can choose any element from the array as
the pivot element. (rightmost)
2. The elements smaller than the pivot element are put on the left and the elements greater
than the pivot element are put on the right.
3. Pivot elements are again chosen form for the left and the right sub-parts separately. With
these sub-parts, the pivot elements are placed at their right position. Then, step 2 is
repeated.
4. The sub-parts are again divided into smaller sub-parts until each subpart is formed of a
single element.
5. At this point, the array is already sorted.
15 20 11 17 10 19 12
EXAMPL
E:
15 20 11 17 10 19 12
Pivot @ rightmost
15 20 11 17 10 19 12
Step 1:
1st pair (15, 12) 15, 20, 11, 17, 10, 19, 12
2nd pair (20, 12) 15, 20, 11, 17, 10, 19, 12
3rd pair (11, 12) 11, 20, 15, 17, 10, 19, 12
4th pair (17, 12) 11, 20, 15, 17, 10, 19, 12
5th pair (10, 12) 11, 10, 15, 17, 20, 19, 12
6th pair (19, 12) 11, 10, 15, 17, 20, 19, 12
Place Pivot (12) 11, 10, 12, 17, 20, 19, 15
STEP 1 Result 11, 10, 12, 17, 20, 19, 15
How QuickSort Works?
1. A pivot element is chosen from the array. You can choose any element from the array as
the pivot element. (rightmost)
2. The elements smaller than the pivot element are put on the left and the elements greater
than the pivot element are put on the right.
3. Pivot elements are again chosen form for the left and the right sub-parts separately. With
these sub-parts, the pivot elements are placed at their right position. Then, step 2 is
repeated.
4. The sub-parts are again divided into smaller sub-parts until each subpart is formed of a
single element.
5. At this point, the array is already sorted.
11 10 12 17 20 19 15
11 10 12 17 20 19 15
2nd Pivot in right
2nd Pivot in left side side
11 10 12 17 20 19 15
Step 2:
Paired Pivot in the left Paired Pivot in the right
1st pair (11, 10) 10, 11, 12 1st pair (17, 15) 10, 11, 12, 17, 20, 19, 15
2nd pair (20, 15) 10, 11, 12, 17, 20, 19, 15
3rd pair (19, 15) 10, 11, 12, 17, 20, 19, 15
Place Pivot (15) 10, 11, 12, 15, 20, 19, 17
STEP 2 Result 10, 11, 12, 15, 20, 19, 17
10 11 12 15 20 19 17
10 11 12 15 20 19 17
3rd Pivot in right
side
10 11 12 15 20 19 17
Step 3:
Paired Pivot in the right
1st pair (20, 17) 10, 11, 12, 15, 20, 19, 17
2nd pair (19, 17) 10, 11, 12, 15, 20, 19, 17
Place Pivot (17) 10, 11, 12, 15, 17, 19, 20
STEP 3 Result 10, 11, 12, 15, 17, 19, 20