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

Complexity of an algorithm, An algorithm is a sequence of steps to solve a ...

An algorithm is a sequence of steps to solve a problem; there may be more than one algorithm to solve a problem. The choice of a particular algorithm depends upon following cons

Conversion of general trees into the binary trees, By taking an appropriate...

By taking an appropriate example explain how a general tree can be represented as a Binary Tree.                                                                    C onversio

How do collisions happen during hashing, How do collisions happen during ha...

How do collisions happen during hashing? Usually the key space is much larger than the address space, thus, many keys are mapped to the same address. Assume that two keys K1 an

Algorithms, 2. Write a note on i) devising ii) validating and...

2. Write a note on i) devising ii) validating and iii) testing of algorithms.

Multidimensional array, Q. The system allocates the memory for any of the m...

Q. The system allocates the memory for any of the multidimensional array from a big single dimensional array. Describe two mapping schemes that help us to store the two dimensi

Files structures, The structures of files vary from operating system to ope...

The structures of files vary from operating system to operating system. In this unit, we will discuss the fundamentals of file structures with the generic file organisations. A

Several operations on a aa-tree, The following are several operations on a ...

The following are several operations on a AA-tree: 1. Searching: Searching is done using an algorithm which is similar to the search algorithm of a binary search tree. 2. Ins

Total impedent of the circuit, an electrical student designed a circuit in...

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

#title.state charts., explain two strategies to implement state charts with...

explain two strategies to implement state charts with the help of an example of each.

Insertion sort, Data array A has data series from 1,000,000 to 1 with step ...

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

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