edited by
4,832 views
15 votes
15 votes

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.
edited by

1 Answer

Best answer
19 votes
19 votes

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]}}$
edited by

Related questions

19 votes
19 votes
3 answers
1
makhdoom ghaya asked Dec 15, 2016
4,158 views
Find a solution to the following recurrence equation:$T(n)=\sqrt{n}+T\left(\frac{n}{2}\right)$$T(1)=1$
7 votes
7 votes
2 answers
2
makhdoom ghaya asked Dec 15, 2016
2,596 views
A language uses an alphabet of six letters, $\left\{a, b, c, d, e, f\right\}$. The relative frequency of use of each letter of the alphabet in the language is as given be...
12 votes
12 votes
4 answers
4
makhdoom ghaya asked Nov 30, 2016
2,655 views
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.