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
In the previous unit, we have discussed arrays. Arrays are data structures of fixed size. Insertion and deletion involves reshuffling of array elements. Thus, array manipulation

Step-1: For the current node, verify whether it contain a left child. If it has, then go to step-2 or else go to step-3 Step-2: Repeat step-1 for left child Step-3: Visit (th

the voltage wave forms are applied at the inputs of an EX-OR gate. determine the output wave form

For splaying, three trees are maintained, the central, left & right sub trees. At first, the central subtree is the complete tree and left and right subtrees are empty. The target

The following DNA sequences are extracted from promoter region of genes which are co-regulated by the same transcription factor (TF). The nucleotide segments capitalized in the giv

Conceptually, the stack abstract data type mimics the information kept into a pile on a desk. Informally, first we consider a material on a desk, where we might keep separate stack

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

a) Given a digraph G = (V,E), prove that if we add a constant k to the length of every arc coming out from the root node r, the shortest path tree remains the same. Do this by usin

A database is a collection of data organized in a manner that facilitates updation, retrieval and management of the data. Searching an unindexed database having n keys will have a

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen