Algorithm to sort a given list by quick sort method, Data Structure & Algorithms

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

Posted Date: 7/13/2012 2:15:20 AM | Location : United States







Related Discussions:- Algorithm to sort a given list by quick sort method, Assignment Help, Ask Question on Algorithm to sort a given list by quick sort method, Get Answer, Expert's Help, Algorithm to sort a given list by quick sort method Discussions

Write discussion on Algorithm to sort a given list by quick sort method
Your posts are moderated
Related Questions
Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g. (define stack1 (make-stack))  (define stack2 (make-stack)) W

How To implement stack using two queues , analyze the running time of the stack operations ?

Determine YIQ Colour Model Whereas an RGB monitor requires separate signals for the red, green, and blue components of an image, a television monitor uses a single composite si

The two famous methods for traversing are:- a) Depth first traversal b) Breadth first


Each data record contains a fixed place in a relative file. Each record ought to have associated with it in integer key value which will help identify this slot. Therefore, this ke

Write a recursive function the computes the number of digits in a positive integer n. For example if n = 6598, the function should return 4. Find a variant expression and a thresho

An algorithm is a sequence of steps to solve a problem; there may be more than one algorithm to solve a problem. The choice of a particular algorithm depends upon following cons

/* the program accepts two polynomials as a input & prints the resultant polynomial because of the addition of input polynomials*/ #include void main() { int poly1[6][

padovan string