# GATE1989-9

1.5k views

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.

recategorized
6

$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$

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
1

According the graph which you have shown above

But in merge sort both side of recurrence tree sorted at same time.

The smallest recurrence tree is 2,5 with 2,5 as root with child 5 and 2..... they are sorted first

then we don't have a sorted list to merge with 2,5

So the tree with 4,7  as root will be sorted.

Then the tree with 2,4,5,7 as root will be sorted by merging 2,5 and 4,7

then we don't have a sorted list to merge with 2,4,5,7

then we apply the same procedure for the tree with root 1,2,3,6 by starting from the smallest recurrence tree i.e. tree with 1,3 as root and with child 1 and 3.

And at last we merge 2,4,5,7 and 1,2,3,6

here we are solving both sides of the recurrence tree at same time , but one after another i.e. left side first then right side.

0

here we are solving both sides of the recurrence tree at same time , but one after another i.e. left side first then right side.

From where r u telling this? Any reference. Cormen doesnot support it

0
where is it written in cormen ?

I have solved it ,using the algo given in cormen whose screenshot is attached in answer.
0
solve the question using the algo which i have attached in answer and tell me the steps
2

And i do think is right here, the recursive algorithm will first solve the left subtree until the base condition is met,after which the right subtree is solved and lastly merging is done.

1

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

${\color{Red} {[7\ 25]}}\ [34\ 2]\ 70\ 9\ 61\ 16\ 49\ 19$

${\color{Red} {[7\ 25]}}\ {\color{Red} {[2\ 34]}}\ [70\ 9]\ 61\ 16\ 49\ 19$

${\color{Red} {[7\ 25]}}\ {\color{Red} {[2\ 34]}}\ {\color{Red} {[9\ 70]}}\ [61\ 16]\ 49\ 19$

${\color{Red} {[7\ 25]}}\ {\color{Red} {[2\ 34]}}\ {\color{Red} {[9\ 70]}}\ {\color{Red} {[16\ 61]}}\ [49\ 19]$

${\color{Red} {[7\ 25]}}\ {\color{Red} {[2\ 34]}}\ {\color{Red} {[9\ 70]}}\ {\color{Red} {[16\ 61]}}\ {\color{Red} {[19\ 49]}}$

$[{\color{Red} {[7\ 25]}}\ {\color{Red} {[2\ 34]}}]\ {\color{Red} {[9\ 70]}}\ {\color{Red} {[16\ 61]}}\ {\color{Red} {[19\ 49]}}$

These steps need to be done in $1$ steps, but @Satbir u done it in 7 steps, which is not correct.

And chk algo again in case of odd elements, it must eliminate last element as odd, any middle element will not left as odd element.

0
why is it wrong if i have just expanded that step ? i have just done it for better explanation for placing the brackets step by step

and according to algo the middle algo is included in first partition.
2

@Satbir you have to do that in a single step, as done in the question below,

https://gateoverflow.in/1467/gate1999-1-14-isro2015-42?show=1467#q1467

If you apply your approach to the above question,you will get the wrong answer.

1

@Satbir

In 2-way merge sort, remove any one step from 2 and 3. Because it should be done in single step

and similarly, edit recursive merge sort too.

0
what will be the changes in recursive merge sort ?
0
Is 2-way merge-sort and recursive calling of merge sort different?
0
yes ...i think it is. k-way merge sort means external sorting and here k=2.
0

Let us check here :https://stackoverflow.com/questions/56696667/2-way-merge-sort-and-merge-sort

And , like previous one u need to do sorting, left and right side at the same time

0

@srestha mam

see here they have done it recursively and have given algo also

https://visualgo.net/en/sorting

0

@Arjun Sir

Is here steps are correct for last merge sort? I mean, left and right should sort at same time. right?Last merge sort should be less than 15 steps. Isnot it?

2
How will they execute at the same time on a sequential machine?
0
But, in book left and right part done same time for merge sort. So, steps are less than this.
0

The book has given that diagram for illustration purpose. If you trace the run of this simple recursive procedure in a Python interpreter -:

def run_me(x):
if x <= 0:
return
print("I am going to run for x - 1: ", x - 1)
run_me(x - 1)
print("I am now going to run for x - 2: ", x - 2)
run_me(x - 2)

The shell will print the following for x = 3 -:

I am going to run for x - 1:  2
I am going to run for x - 1:  1
I am going to run for x - 1:  0
I am now going to run for x - 2:  -1
I am now going to run for x - 2:  0
I am now going to run for x - 2:  1
I am going to run for x - 1:  0
I am now going to run for x - 2:  -1

Notice how it is running x - 1 cases at the top - first it reaches 0, and then it runs x - 2 case. If both calls ran at the same time somehow, then we would have "I am running for x - 1" and "I am running for x - 2" appearing one after the other at the beginning itself.

Why should it be any different for mergesort, which has similar code structure?

0
how to do quicksort i am not gettng ? can you explain pass by pass in simple diagrammatical way having i j and p ?
0

Watch this you'll understand

## Related questions

1
1.8k views
Find a solution to the following recurrence equation: $T(n)=\sqrt{n}+T(\frac{n}{2})$ $T(1)=1$
A language uses an alphabet of six letters, $\left\{a, b, c, d, e, f\right\}$ ... Design a prefix binary code for the language which would minimize the average length of the encoded words of the language.
What is the output produced by the following program, when the input is "HTGATE" Function what (s:string): string; var n:integer; begin n = s.length if n <= 1 then what := s else what :=contact (what (substring (s, 2, n)), s.C [1]) end; Note type string=record length:integer; ... $s_{1}$ length + $s_{2}$ - length obtained by concatenating $s_{1}$ with $s_{2}$ such that $s_{1}$ precedes $s_{2}$.
Match the pairs in the following:$\begin{array}{ll|ll}\hline \text{(A)} & \text{$O (\log n)$} & \text{(p)} & \text{Heapsort} \\\hline \text{(B)} & \text{$O (n)$} & \text{(q)}& \text{Depth-first search} \\\hline \text{(C)}& \text{$ ... $} &\text{(s)} & \text{Selection of the$k^{th}$smallest element in a set of$n$elements} \\\hline \end{array}$