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

Assignment Help:

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


Related Discussions:- Algorithm to sort a given list by quick sort method

Merging 4 sorted files containing 50, Merging 4 sorted files having 50, 10,...

Merging 4 sorted files having 50, 10, 25 and 15 records will take time  O (100)

Tree Traversal, If preorder traversal and post order traversal is given the...

If preorder traversal and post order traversal is given then how to calculate the pre order traversal. Please illustrate step by step process

Define the term - array, Define the term - Array A fixed length, ord...

Define the term - Array A fixed length, ordered collection of values of same type stored in contiguous memory locations; collection may be ordered in several dimensions.

Design and implement a software system, In this assignment, you are invited...

In this assignment, you are invited to design and implement a software system for catalogue sale. A catalogue is organised in a tree structure. Each node of the catalogue tree repr

Data Mining and Neural Networks, I am looking for some help with a data min...

I am looking for some help with a data mining class with questions that are about neural networks and decision trees. Can you help? I can send document with questions.

Write an algorithm outputs number of books using psuedocode, A shop sells b...

A shop sells books, maps and magazines. Every item is identified by a unique 4 - digit code. All books have a code starting with a 1, all maps have a code which starts with a 2 and

A bst is traversed in which order recursively, A  BST is traversed in the ...

A  BST is traversed in the following order recursively: Right, root, left e output sequence will be in In Descending order

Prefix and Postfix Expressions, Q.   Draw the expression tree of the infix ...

Q.   Draw the expression tree of the infix expression written below and then  convert it intoPrefix and Postfix expressions. ((a + b) + c * (d + e) + f )* (g + h )

Explain what is stack. describe ways to execute stack. , ST AC K is ...

ST AC K is explained as follows : A stack is one of the most usually used data structure. A stack is also called a Last-In-First-Out (LIFO) system, is a linear list in

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd