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

algorithm for multiplication of two sparse matrices using linked lists..

sdsd.

Q. Construct a complete binary tree with depth 3 for this tree which is maintained in the memory using the linked representation. Make the adjacency list and adjacency matrix for t

(a) Write (delay ) as a special form for (lambda () ) and (force ), as discussed in class. (b) Write (stream-cons x y) as a special form, as discussed in class. (c) Write

What is an Algorithm? An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for getting a needed output for any legitimate input in a finite amoun

Define the Carrier set of the Symbol ADT Carrier set of the Symbol ADT is the set of all finite sequences of characters over Unicode characters set (Unicode is a standard char

What is Access Restrictions Structured containers with access restrictions only allow clients to add, remove and examine elements at certain locations in their structure. For

We will start by defining a new structure called Heap. Figure 3 illustrates a Binary tree. Figure: A Binary Tree A complete binary tree is said to assure the 'heap con

Question 1 Explain the use of algorithms in computing Question 2 Explain time complexity and space complexity of an algorithm Question 3 Explain how you can analyz