Quick sort, Data Structure & Algorithms

Assignment Help:

This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of implementation, moderate use of resources & acceptable behavior for a variety of sorting cases. The fundamental of quick sort is the divide & conquer strategy that means Divide the problem [list to be sorted] into sub-problems [sub-lists], till solved sub problems [sorted sub-lists] are found. It is implemented as follows:

Select one item A[I] from the list A[ ].

Rearrange the list so that this item come to the appropriate position, that means all preceding items have a lesser value and all succeeding items contain a greater value than this item.

1.      Place A[0], A[1] .. A[I-1] in sublist 1

2.      A[I]

3.      Place A[I + 1], A[I + 2] ... A[N] in sublist 2

Repeat steps 1 and step 2 for sublist1 and sublist2 until A[ ] is a sorted list. As can be seen, this algorithm contains a recursive structure.

The divide' procedure is of utmost importance in this algorithm. Usually this is implemented as follows:

1.      Select A[I] as the dividing element.

2.         From the left end of the list (A[O] onwards) scan until an item A[R] is found whose value is greater than A[I].

3.         From the right end of list [A[N] backwards] scan until an item A[L] is found whose value is less than A[1].

4.      Swap A[R] & A[L].

5.      Continue steps 2, 3 & 4 till the scan pointers cross. End at this stage.

6.      At this point, sublist1 and sublist2 are ready.

7.      Now do the same for each of sublist1 & sublist2.


Related Discussions:- Quick sort

Small program on Algorithms , Objective The goal of this project is to ext...

Objective The goal of this project is to extend and implement an algorithm presented in the course and to apply notions introduced by the course to this program/algorithm. The ass

Estimate the probability that the noncritical path , An advertising project...

An advertising project manager developed the network diagram shown below for a new advertising campagign.  In addition, the manager gathered the time information for each activity,

High-level and bubble algorithm , 1. Give both a high-level algorithm and a...

1. Give both a high-level algorithm and an implementation (\bubble diagram") of a Turing machine for the language in Exercise 3.8 (b) on page 160. Use the ' notation to show the co

Draw a flowchart that takes temperatures input, Write an algorithm in form ...

Write an algorithm in form of a flowchart that takes temperatures input over a 100 day period (once per day) and outputs the number of days when temperature was below 20C and numbe

Interest, I=PR/12 numbers of years : Interest Rate up to 1 years : 5...

I=PR/12 numbers of years : Interest Rate up to 1 years : 5.50 Up to 5 years : 6.50 More than 5 year : 6.75 please design an algorithm based on the above information

Algorithm to find maximum and minimum numbers, Give an algorithm to find bo...

Give an algorithm to find both the maximum and minimum of 380 distinct numbers that uses at most 568 comparisons.

Implementing abstract data types, Implementing abstract data types A co...

Implementing abstract data types A course in data structures and algorithms is hence a course in implementing abstract data types. It may seem that we are paying a lot of atten

Define a procedure called make-avl-tree, This question deals with AVL trees...

This question deals with AVL trees. You must use mutable pairs/lists to implement this data structure: (a) Define a procedure called make-avl-tree which makes an AVL tree with o

Explain floyds algorithm, Explain Floyd's algorithm It is convenient to...

Explain Floyd's algorithm It is convenient to record the lengths of shortest paths in an n by n matrix D known as the  distance matrix: the element d ij   in the i th   row an

Tic Tac Toe game , Book to refer: Introduction to Algorithms, 3rd Ed, by Cl...

Book to refer: Introduction to Algorithms, 3rd Ed, by Clifford Stein, Thomas H. Cormen, Ronald Rivest, Charles E. Leiserson Question: Tic Tac Toe game -Design a GUI and implement

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