Question

Use Quick sort to sort the following list. Show the actions step by step

123, 34, 189, 56, 150, 12, 9, 240

Answer 1

Quicksort (sometimes called partition-exchange sort) is an efficient sortingalgorithm, serving as a systematic method for placing the elements of an array in order.It is still a commonly used algorithm for sorting.

Assume pivot is the leftmost one in the range and the partition is:
Function Partition (left, right)
P = A [left]; i = left; j = right + 1
While (1)
Do i ++ until A [i]> = P;
Do j-- until A [j] <= P;
If i <j swap A [i] and A [j]
Else exit the while-loop
Swap A [left] and A [j]; return j;
Step-by step:
(123 34 189 56 150 12 9 240) (pivot 123)
(34 9 56 12) 123 (150 189 240) (pivot: 34, 150)
(912) 34 (56) 123 150 (189 240) (pivot: 9, 56, 189)
9 (12) 34 56 123 150 189 (240) (pivot: 12, 240)