Question

List 44 33 11 55 77 90 40 60 99 22 88 66 if we try to sort the list using quick sort

Answer 1

Answer:

• In Quick sort algorithm,  we can perform the partitioning of the list in the  following steps...

Step 1 - Set the first element of the list as pivot .

Step 2 - Take two variables left and right. Set left and right to first and last elements of the list respectively.

Step 3 - Increment left until list[left] > pivot then stop.

Step 4 - Decrement right until list[right] < pivot then stop.

Step 5 - If left < right then exchange list[left] and list[right].

Step 6 - Repeat steps 3,4 & 5 until left >right.

Step 7 - Exchange the pivot element with list[right] element.

Step-by-step explanation:

• The partition() process is the key process in quicksort  . The partition() function  receives an array and an element x of the array as a pivot and put x at its correct position in a sorted array . It then put all  elements smaller than x before x, and put all elements greater than x after x.

• Consider the given list :

          44 33 11 55 77 90 40 60 99 22 88 66

Size of the list a is 12 , index starts from 0 to 11.

pivot : 0           left : 1           right : 11

• Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -Now, a[left] = 44, a[right] = 88, and a[pivot] = 44

• again, a[pivot] < a[right], algorithm moves forward one position towards left, i.e. -Now, a[left] = 44, a[right] = 22, and a[pivot] = 44

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves to right, as -

• 22  33 11 55 77 90 40 60 99 44 88 66
  Now, a[left] = 22, a[right] = 44, and a[pivot] = 44. As the pivot is at right, so algorithm starts from left and moves to right.

      As a[pivot] > a[left], so algorithm moves one position to right

• Now, a[left] = 33, a[right] = 44, and a[pivot] = 44. As a[pivot] > a[left], so algorithm moves one position to right

• Now, a[left] = 11, a[right] = 44, and a[pivot] = 44. a[pivot] > a[left], so algorithm moves one position to right

• Now, a[left] = 55, a[right] = 44, and a[pivot] = 44.

    Because, a[pivot] <a[left], so, algorithm will swap a[pivot] with a[left],  and pivot moves to left -

22  33 11 44 77 90 40 60 99 55 88 66

• Now, a[left] = 44, a[right] = 55, and a[pivot] = 44. a[pivot] < a[right], so algorithm moves forward one position towards left,

• Now, a[left] = 44, a[right] = 99, and a[pivot] = 44.

• Next : a[left] = 44, a[right] = 60, and a[pivot] = 44.

• Next :  a[left] = 44, a[right] =40, and a[pivot] = 44.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves to right, as -

22  33 11 40 77 90 44 60 99 55 88 66

• Now 40 is in its proper position, all elements in its left is less than 40 and elements in its right are greater than 40.

If we repeat the procedure, we will get the sorted array.