1 of 8

Working of Quick Sort

CS212 : Design & Analysis of Algorithms

Prof. Prateek Vishnoi

Indian Institute of Technology, Mandi

2 of 8

Steps of Quick Sort

  • Select the last element of an array as a π‘π‘–π‘£π‘œπ‘‘ element.

​

  • Initialise pointer 𝑗 as 1st(base address) index of an array.

​

  • Initialise pointer 𝑖 which points to the address just before the base address of an array.

​

  • Iterate the pointer 𝑗 over an array with the following conditions:
  • If the value at pointer 𝑗 is β‰₯ π‘π‘–π‘£π‘œπ‘‘, IGNORE.
  • If value at pointer 𝑗 < π‘π‘–π‘£π‘œπ‘‘, then 𝑖++ and swap(value at 𝑖 , value at 𝑗)
  • Recursively call the Quick Sort Function on a left subarray of the π‘π‘–π‘£π‘œπ‘‘ element.
  • Recursively call the Quick Sort Function on a right subarray of the π‘π‘–π‘£π‘œπ‘‘ element.

​

​

Indian Institute of Technology, Mandi

3 of 8

Indian Institute of Technology, Mandi

8 2 4 7 1 3 9 6 5

𝑖

𝑗

π‘£π‘Žπ‘™(𝑗) > π‘π‘–π‘£π‘œπ‘‘, 𝐼𝐺𝑁𝑂𝑅𝐸, 𝑗++

π‘π‘–π‘£π‘œπ‘‘ =5

​

​

8 2 4 7 1 3 9 6 5

𝑖

𝑗

π‘£π‘Žπ‘™(𝑗) < π‘π‘–π‘£π‘œπ‘‘, 𝑖++ , π‘ π‘€π‘Žπ‘(π‘£π‘Žπ‘™(𝑖), π‘£π‘Žπ‘™(𝑗))

2 8 4 7 1 3 9 6 5

𝑖

𝑗

𝑗++

2 8 4 7 1 3 9 6 5

𝑖

𝑗

4 of 8

Indian Institute of Technology, Mandi

2 8 4 7 1 3 9 6 5

𝑖

𝑗

2 4 8 7 1 3 9 6 5

π‘£π‘Žπ‘™(𝑗) < π‘π‘–π‘£π‘œπ‘‘, 𝑖++ , π‘ π‘€π‘Žπ‘(π‘£π‘Žπ‘™(𝑖), π‘£π‘Žπ‘™(𝑗))

𝑗

𝑖

2 4 8 7 1 3 9 6 5

𝑗++

2 4 8 7 1 3 9 6 5

𝑖

𝑗

π‘£π‘Žπ‘™(𝑗) > π‘π‘–π‘£π‘œπ‘‘, 𝐼𝐺𝑁𝑂𝑅𝐸, 𝑗++

𝑖

𝑗

5 of 8

Indian Institute of Technology, Mandi

2 4 8 7 1 3 9 6 5

𝑖

𝑗

π‘£π‘Žπ‘™(𝑗) < π‘π‘–π‘£π‘œπ‘‘, 𝑖++ , π‘ π‘€π‘Žπ‘(π‘£π‘Žπ‘™(𝑖), π‘£π‘Žπ‘™(𝑗))

2 4 1 7 8 3 9 6 5

𝑖

𝑗

2 4 1 7 8 3 9 6 5

𝑗++

𝑖

𝑗

π‘£π‘Žπ‘™(𝑗) < π‘π‘–π‘£π‘œπ‘‘, 𝑖++ , π‘ π‘€π‘Žπ‘(π‘£π‘Žπ‘™(𝑖), π‘£π‘Žπ‘™(𝑗))

2 4 1 3 8 7 9 6 5

𝑖

𝑗

6 of 8

Indian Institute of Technology, Mandi

2 4 1 3 8 7 9 6 5

π‘£π‘Žπ‘™(𝑗) > π‘π‘–π‘£π‘œπ‘‘, 𝐼𝐺𝑁𝑂𝑅𝐸, 𝑗++

𝑖

𝑗

2 4 1 3 8 7 9 6 5

𝑖

𝑗

2 4 1 3 8 7 9 6 5

π‘£π‘Žπ‘™(𝑗) > π‘π‘–π‘£π‘œπ‘‘, 𝐼𝐺𝑁𝑂𝑅𝐸, 𝑗++

𝑖

𝑗

2 4 1 3 8 7 9 6 5

π‘£π‘Žπ‘™(𝑗) > π‘π‘–π‘£π‘œπ‘‘, 𝐼𝐺𝑁𝑂𝑅𝐸, 𝑗++

𝑖

𝑗

7 of 8

Indian Institute of Technology, Mandi

2 4 1 3 8 7 9 6 5

𝑖

𝑗

𝑗 pointing to pivot, 𝑖++, swap(value(𝑖), pivot)

2 4 1 3 5 7 9 6 8

2 4 1 3

7 9 6 8

𝑖

𝑗

π‘π‘–π‘£π‘œπ‘‘ =3

π‘£π‘Žπ‘™(𝑗) < π‘π‘–π‘£π‘œπ‘‘, 𝑖++ , π‘ π‘€π‘Žπ‘(π‘£π‘Žπ‘™(𝑖), π‘£π‘Žπ‘™(𝑗))

2 4 1 3

𝑗

𝑖

8 of 8

Indian Institute of Technology, Mandi

2 4 1 3 5 7 9 6 8

7 9 6 8

𝑖

𝑗

π‘π‘–π‘£π‘œπ‘‘ =3

π‘£π‘Žπ‘™(𝑗) < π‘π‘–π‘£π‘œπ‘‘, 𝑖++ , π‘ π‘€π‘Žπ‘(π‘£π‘Žπ‘™(𝑖), π‘£π‘Žπ‘™(𝑗))

2 4 1 3

𝑗

𝑖

2 4 1 3

2 4 1 3

𝑖

𝑗

𝑗++

π‘π‘–π‘£π‘œπ‘‘ =8

Follow the same steps

𝑖

𝑗

7 9 6 8

𝑖

𝑗

𝑗++

7 9 6 8

𝑖

𝑗

Follow the same steps

π‘£π‘Žπ‘™(𝑗) < π‘π‘–π‘£π‘œπ‘‘, 𝑖++ , π‘ π‘€π‘Žπ‘(π‘£π‘Žπ‘™(𝑖), π‘£π‘Žπ‘™(𝑗))