GATE CSE 1989 | Question: 9

Question

An input files has $10$ records with keys as given below:

$25\quad 7\quad 34\quad  2\quad  70\quad  9\quad  61\quad  16\quad  49\quad  19$

This is to be sorted in non-decreasing order.

1. Sort the input file using QUICKSORT by correctly positioning the first element of the file/subfile. Show the subfiles obtained at all intermediate steps. Use square brackets to demarcate subfiles.
2. Sort the input file using $2$-way- MERGESORT showing all major intermediate steps. Use square brackets to demarcate subfiles.

Comments

$25,7,34,2,70,9,61,16,49,19$

After $1^{st}$ pass: $(19,7,2,9,16)$ $25$ $(61,70,49,34)$

After $2^{nd}$ pass: $(16,7,2,9)$ $19,25$  $(61,70,49,34)$

After $3^{rd}$ pass: $(9,7,2)$ $16,19,25$ $(61,70,49,34)$

After $4^{th}$ pass: $(2,7)$ $9,16,19,25$ $(61,70,49,34)$

After $5^{th}$ pass:  $2,7,9,16,19,25$ $(61,70,49,34)$

After $6^{th}$ pass:  $2,7,9,16,19,25$ $(34,49)$ $61$ $(70)$

After $7^{th}$ pass:  $2,7,9,16,19,25$  $34,49,61$ $(70)$

After $8^{th}$ pass:  $2,7,9,16,19,25$  $34,49,61,70$

---

@KUSHAGRA गुप्ता , @Arjun sir

Please explain the first pass.

I am getting some different pattern in the first pass.

(9,7,19,2,16),25,(61,70,49,34).

Just explain the first pass, I will get the remaining point.

---

@GateOverflow04 you answer is also correct because their is no fixed method in which paritition algorithm will swap the values. 

---

@abir_banerjee  thank you for clearing my doubt.

Answer 1

Quick Sort

$\textbf{Pseudocode for quicksort}$

$\text{QUICKSORT(A,p,r)}$
$\quad \textbf{if } p < r$
$\quad\quad \textbf{then} q \leftarrow \text{PARTITION}(A,p,r)$
$\quad\quad\quad \text{QUICKSORT}(A,p,q-1)$
$\quad\quad\quad\text{QUICKSORT}(A,q+1,r)$

${\color{Red}{\text{Initial call: }} }\text{QUICKSORT}(A,1,n)$

1. ${\color{Red} {25}}\ 7\ 34\ 2\ 70\ 9\ 61\ 16\ 49\ 19$
2. ${\color{Red} {25}}\ 7\  \color{blue}{2\ 34}\ 70\ 9\ 61\ 16\ 49\ 19$
3. ${\color{Red} {25}}\ 7\ 2\  \color{blue}{9}\   70\;  \color{blue}{34}\;  61\ 16\ 49\ 19$
4. ${\color{Red} {25}}\ 7\ 2\ 9 \ \color{blue}{16}\   34\ 61\ \color{blue}{70}\  49\ 19$
5. ${\color{Red} {25}}\ 7\ 2\ 9\ 16\ \color{blue}{19} \; 61\ 70\ 49 \ \color{blue}{34}$
6. $[7\ 2\ 9\ 16$ $19]$ ${\color{Red} {25}}\ [61\ 70\ 49$ $34]$
7. $[{\color{Red} {7}}\ 2\ 9\ 16\ 19]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
8. $[[2]\ {\color{Red} {7}}\ [9\ 16\ 19]]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
9. $[{\color{Red} {2\ 7}}\ [{\color{Red} {9}}\ [16\ 19]]]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
10. $[{\color{Red} {2\ 7}}\ [{\color{Red} {9}}\ [{\color{Red} {16}} \ 19]]]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
11. $[{\color{Red} {2}}\ {\color{Red} {7}}\ [{\color{Red} {9}}\ [{\color{Red} {16}} \ {\color{Red} {19}}]]]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
12. ${\color{Red} {[2}}\ {\color{Red} {7[}}\ {\color{Red} {9}}\ {\color{Red} {16}} \ {\color{Red} {19]]}}\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
13. ${\color{Red} {[2}}\ {\color{Red} {7}}\ {\color{Red} {9}}\ {\color{Red} {16}} \ {\color{Red} {19]}}\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
14. ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[{\color{Red} {61}}\ \color{blue}{49\ 70}\  34]$
15. ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[{\color{Red} {61}}\ 49\; \color{blue}{34\ 70}]$
16. ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }} [[49\ 34]\ {\color{Red} {61}}\  [70] ]$
17. ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[[ {\color{Red} {49}}\ 34]\ {\color{Red} {61}}\  [70] ]$
18. ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[[ [34]\ {\color{Red} {49}}]\ {\color{Red} {61}}\  [70] ]$
19. ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[ {\color{Red} {[ [34]\ 49]}}\ {\color{Red} {61}}\  [70] ]$
20. ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[ {\color{Red} {[34\ 49]}}\ {\color{Red} {61}}\  [70] ]$
21. ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}  [{\color{Red} {34\ 49}}\ {\color{Red} {61\ [70 ]}}]  $
22. ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}  {\color{Red} {[34\ 49}}\ {\color{Red} {61\ 70 ]}}\  $
23. ${\color{Red} {[2\ 7\ 9\ 16\ 19\ 25\ }}  {\color{Red} {34\ 49}}\ {\color{Red} {61\ 70] }}\  $

---

2-way MergeSort [Iterative version]

1. $[25\ 7]\ [34\ 2]\ [70\ 9]\ [61\ 16]\ [49\ 19]$
2. $[{\color{Red} {[7\ 25]}}\ {\color{Red} {[2\ 34]}}]\ [{\color{Red} {[9\ 70]}}\ {\color{Red} {[16\ 61]}}]\ [{\color{Red} {[19\ 49]}}]$
3. $[{\color{Green} {[2\ 7\ 25\ 34 ]}}\  {\color{Green} {[9\ 16\ 61\ 70]}}]\ {\color{Green} {[19\ 49]}}$
4. $[{\color{Blue} {[2\ 7\ 9\ 16\  25\ 34\  61\ 70]}}\ {\color{Green} {[19\ 49]}}]$
5. $[{\color{Blue} {[2\ 7\ 9\ 16\ 19\ 25\ 34\ 49\ 61\ 70]}}$

$\textbf{MergeSort [Recursive version]}$

$\textbf{MERGE - SORT A[1...n]}$

1. $\text{If } n = 1,$ done.
2. Recursively sort $A[1...\left \lceil n/2 \right \rceil]$ and $A[\left \lceil n/2 \right \rceil + 1 ... n]. $
3. ${\color{Red}{\text{“Merge"}}}$ the $2$ sorted lists.

$\qquad{\color{Red}{\text{Key subroutine: }}}  \textbf{MERGE}$

1. $[25\ 7\ 34\ 2\ 70]\ [9\ 61\ 16\ 49\ 19]$
2. $[[25\ 7\ 34]\ 2\ 70]\ [9\ 61\ 16\ 49\ 19]$
3. $[[{\color{Red} {[7\ 25]}}\ [34]]\ [2\ 70]]\ [9\ 61\ 16\ 49\ 19]$
4. $[[{\color{Red} {[7\ 25]}}\ {\color{Red} {[34]}}]\ [2\ 70]]\ [9\ 61\ 16\ 49\ 19]$
5. $[[{\color{Red} {[7\ 25\ 34]}}]\ [2\ 70]]\ [9\ 61\ 16\ 49\ 19]$
6. $[{\color{Red} {[7\ 25\ 34]}}\ {\color{Red} {[2\ 70]}}]\ [9\ 61\ 16\ 49\ 19]$
7. ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [9\ 61\ 16\ 49\ 19]$
8. ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [[9\ 61\ 16]\ [49\ 19]]$
9. ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [[[9\ 61]\ [16]]\ [49\ 19]]$
10. ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [[{\color{Red} {[9\ 61]}}\ [16]]\ [49\ 19]]$
11. ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [[{\color{Red} {[9\ 61]\ [16]}}\ ]\ [49\ 19]]$
12. ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [{\color{Red} {[9\ 16\ 61]}}\ [49\ 19]]$
13. ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [{\color{Red} {[9\ 16\ 61]}}\ {\color{Red} {[19\ 49]}}]$
14. ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ {\color{Red} {[9\ 16\ 19\ 49\ 61]}}$
15. ${\color{Red} {[2\ 7\ 9\ 16\ 19\ 25\ 34\ 49\ 61\ 70]}}$

Comments

In quick sort, once the partition is found, the pivot element is swapped with the last index of the first partition. There’s no shifting takes place. So, after Step 5 in QuickSort, 25 will get swapped with 19 and as a result 19 will get selected as pivot in the next round for the first partition.

Shifting has asymptotically higher complexity than swapping.

---

I was so confused for Part - A. I didnt understand, how quick sort was working. Then after a bit of research, here are the findings.

We can perform Quick sort using 3 partition Methods:

1) Naive

2) Lomuto (Used in the answer)

3) Hoare (More Popular)

Reference links :

https://www.youtube.com/watch?v=y0YC4R4V9L8# (Talks briefly about all 3)

https://m.youtube.com/watch?v=86WSheyr8cM (Visualization of Lomuto)

https://m.youtube.com/watch?v=NuQYFXmLUrM (Visualization of Hoare)

Lomuto Explanation : https://www.geeksforgeeks.org/dsa/lomuto-partition-algorithm/

Hoare Explanation : https://www.geeksforgeeks.org/dsa/hoare-s-partition-algorithm/

---

Also what @DebRC said is correct.

After step 5, 19 should be swapped with 25. Step 6 should look like this :

[19, 7, 2, 9, 16] 25 [61, 70, 49, 34]