The Gateway to Computer Science Excellence
+3 votes
524 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.
in Algorithms by Boss (30.8k points)
recategorized by | 524 views
+1

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

1 Answer

+3 votes
Best answer

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]}}$
by Boss (24k points)
edited by
0
Isn't 2-way mergesort different from mergesort ?
+2
I think it is same because we take 2 sorted list and merge them thats why its called 2- way mergesort.

We can have k-way mergesort also.
+1

2-way merge sort is an iterative process while mergesort is a recursive process.

Using 2-way merge sort, the list will be sorted in the following way, whereas in merge sort it will sorted as shown by you.

25  7  34  2  70  9  61  16  49  19

1st pass  :-  7  25   2  34   9  70   16  61   19  49

2nd pass :-  2  7  25  34   9  16  61  70   19  49

3rd pass :-   2  7  9  16  25  34  61  70   19  49

4th pass :-   2  7  9   16  19  25  34  49  61  70

0

@Meet2698

Can you provide any reference please

+1

Jump to around 12:20.

0
Thank you for correcting me :)
0

You're welcome :)

0

@Meet2698

2 way merge sort is same as merge sort, how far I know. There is nothing like 1 way merge sort. right?

@Satbir Have u applied divide policy  first??

0
yes ,[  ] represents division and ${\color{Red} {[\ ]}}$ represents that they have been sorted
0
But in merge sort both side of recurrence tree sorted at same time.

U sorted left side first, and then right side
0
I disagree, see the algo.

Recursively sort A[1....n/2] and A[n/2+1.....n]

So when we go for sorting A[1....n/2] it will again break to say part-1a and part-1b

now when we start solving part1a it will again break to part-2a and part -2b

and so on till base condition occurs for left part.

So recursively left part is sorted first then right part.
0

no, that is incorrect.

See the recurrence tree. Every level sorted in same time, otherwise divide and conquer policy not applicable

 

0

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

@srestha,

See the below links.

https://gateoverflow.in/53183/mergesort?show=53183#q53183 

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

And i do think @Satbir 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.

0

chk this https://www.geeksforgeeks.org/merge-sort/

$[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.
+1

@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?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,303 answers
198,306 comments
105,008 users