**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. **

**A****n****s****.**

**Algo****rithm 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