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
Phong Shading Phong shading too is based on interpolation, but instead of interpolating the colour value, it is the normal vector, which is interpolated for each point and a co

The complexity of searching an element from a set of n elements using Binary search algorithm is   O(log n)

Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

Properties of colour Colour descriptions and specifications generally include three properties: hue; saturation and brightness. Hue associates a colour with some position in th

The quick sort algorithm exploit design technique Divide and Conquer

What are expression trees?  The leaves of an expression tree are operands, like as constants or variable names, and the other nodes have operators. This certain tree happens to


Enumerate about the concept of container A Container can have a size() operation. We can also ask (somewhat redundantly) whether a Container is empty. And even though a Contain

since the gregorian calendar was introduced in 1752,a leap year occurs every 4 years.you are to write a pseudo code to find out whether a year is a leap year.your progrm should dis