Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.
Ans.
Algorithm for Quick Sort is written below
QUICK(A, N, BEG, END, LOC)
Here A is an array with N element. Parameter BEG
and END comprises the boundary value of the sub
list of A to which this method applies. LOC keeps track of the position of the first element A[BEG] of the sublist during the particular procedure. The local varrible LEFT and RIGHT will contain the boundary value of the list elements that have not been scanned.
1. [Initialize] Set LEFT:=BEG, RIGHT;=END and LOC:=BEG.
2. [Scan from left to right]
(a) Repeat while A[LOC] <=A[RIGHT] and LOC!=RIGHT; RIGHT:=RIGHT-1; [End of loop]
(b)If LOC= RIGHT, then Return;
(c)If A[LOC ] > A[RIGHT],then: [Interchange A[LOC] and A[RIGHT]] TEMP:= A[LOC] ,A[LOC] = A[RIGHT] , A[RIGHT] :=TEMP;
(i) Set LOC =RIGHT
(ii) Go to step 3
3.[Scan from left to right]
repeat while A[LEFT] <=A[LOC] and LEFT!= LOC; LEFT := LEFT +1; [End of loop]
(a) If LOC =LEFT, then Return;
(b) If A[LEFT] > A[LOC] ,then
(i) [Interchange A[LEFT] and A[LOC]] TEMP:=A[LOC],A[LOC]:=A[LEFT] . A[LEFT]:= TEMP
(ii) Set LOC :=LEFT (iii) Go to Step 2; [End of if structure]
(Quicksort) This algorithm sorts an array A with N elements.
1. [Intialize.] TOP := NULL
2. [Push boundary values of A onto stacks when A has 2 or more elements.]
If N>1, then: TOP+1,LOWER [1]:=1, UPPER [1]: =N
3. Repeat steps 4 to 7 while TOP != NULL.
4. [Pop sublist from stacks.]
Set BEG: =LOWER[TOP], END:=UPPER[TOP], TOP:=TOP-1.
5. Call QUICK (A, N, BEG, END, LOC). [ Push left
sublist onto stacks when it has 2 or more elements.]
If BEG < LOC -1, then:
TOP:= TOP+1, LOWER[TOP] := BEG, UPPER[TOP]= LOC -1.
[End of If structure.]
6. [Push right sublist onto stacks when it has 2
or more elements.]
If LOC +1< END , then:
TOP := TOP+1, LOWER[TOP] := LOC +1, UPPER[TOP] := END.
[End of If structure .] [End of Step 3 loop.]
7. Exit.
The behaviour of quick sort when the list is sorted is of order O(n2) as this is the worst case for quicksort