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

Complete trees, This is a k-ary position tree wherein all levels are filled...

This is a k-ary position tree wherein all levels are filled from left to right. There are a number of specialized trees. They are binary trees, AVL-trees, binary search trees, 2

#title.structured programming, what do you understand by structured program...

what do you understand by structured programming?explain with eg. top down and bottem up programming technique

The threaded binary tree, By changing the NULL lines in a binary tree to th...

By changing the NULL lines in a binary tree to the special links called threads, it is possible to execute traversal, insertion and deletion without using either a stack or recursi

Merge sort , What is the best-case number of comparisons performed by merge...

What is the best-case number of comparisons performed by mergesort on an input sequence of 2 k distinct numbers?

Illustrate the visual realism applications, Illustrate the Visual realism a...

Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

The best average behaviour, The best average behaviour is shown by  Qui...

The best average behaviour is shown by  Quick Sort

Applications of linear and binary search, The searching method are applicab...

The searching method are applicable to a number of places in current's world, may it be Internet, search engines, text pattern matching, on line enquiry, finding a record from data

Flow chart, that will determine the volume of the sphere or the volume of c...

that will determine the volume of the sphere or the volume of cone or volume of pyramid depending on the choice of the user

Red-black trees, A Red-Black Tree (RBT) is a type of Binary Search tree wit...

A Red-Black Tree (RBT) is a type of Binary Search tree with one extra bit of storage per node, i.e. its color that can either be red or black. Now the nodes can have any of the col

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