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

Linked list implementation of a dequeue, Double ended queues are implemente...

Double ended queues are implemented along doubly linked lists. A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and righ

Circular queues and implement circular queues using array, Explain what are...

Explain what are circular queues? Write down routines required for inserting and deleting elements from a circular queue implemented using arrays.           Circular queue:

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

#, if two relations R and S are joined, then the non matching tuples of bot...

if two relations R and S are joined, then the non matching tuples of both R and S are ignored in

Functions for inserting and deleting at either of the end, Q. Develop a rep...

Q. Develop a representation for a list where insertions and deletions can be done at either end. Such a structure is known as a Deque (Double ended queue). Write functions for inse

Graph traversal schemes, Q. Explain various graph traversal schemes and wri...

Q. Explain various graph traversal schemes and write their advantages and disadvantages. A n s . Graph Traversal Scheme is explained below In many troubles we wish

Deletion, sir how can i explain deletion process in a data structure

sir how can i explain deletion process in a data structure

Flowchart, create a flowchart that displays the students average score for ...

create a flowchart that displays the students average score for these quizzes

What is binary search, What is binary search?   Binary search is most ...

What is binary search?   Binary search is most useful when list is sorted. In binary search, element present in middle of the list is determined. If key (the number to search)

Implementation of stack using linked lists, In the last subsection, we have...

In the last subsection, we have implemented a stack by using an array. While a stack is implemented by using arrays, it suffers from the basic restriction of an array - i.e., its s

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