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

Test whether a binary tree is a binary search tree, Q. Write down an algori...

Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

Draw the process flow diagram, Draw the process flow diagram: Anand   ...

Draw the process flow diagram: Anand   Dairy (AD) sources 150,000 litres of milk daily from large number of local villagers .The milk is collected from 4:00 AM to 6:00 am and

Program segment for deletion of any element from the queue, Program segment...

Program segment for deletion of any element from the queue delete() { int delvalue = 0; if (front == NULL) printf("Queue Empty"); { delvalue = front->value;

Explain time complexity, Time Complexity:- The time complexity of an algori...

Time Complexity:- The time complexity of an algorithm is the amount of time it requires to run to completion. Some of the reasons for studying time complexity are:- We may be in

Explain about the preconditions assertion, Preconditions assertion A ...

Preconditions assertion A precondition is an assertion which should be true at the initiation of an operation. For instance, a square root operation can't accept a negative a

Algorithm that counts number of nodes in a linked list, Q. Write an algorit...

Q. Write an algorithm that counts number of nodes in a linked list.                                       A n s . Algo rithm to Count No. of Nodes in Linked List C

Explain how two dimensional arrays are represented in memory, Explain how t...

Explain how two dimensional arrays are represented in memory. Representation of two-dimensional arrays in memory:- Let grades be a 2-D array as grades [3][4]. The array will

Perform inorder, QUESTION (a) Construct a binary tree for the following...

QUESTION (a) Construct a binary tree for the following numbers assuming that a number greater than the node (starting from the root) goes to the left else it goes to the right.

Number of leaf nodes in a complete binary tree, The number of leaf nodes in...

The number of leaf nodes in a complete binary tree of depth d is    2 d

Red black tree, red black tree construction for 4,5,6,7,8,9

red black tree construction for 4,5,6,7,8,9

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