Algorithm
-
Getting Started with AlgorithmWhat is an Algorithm?
-
Characteristics of Algorithm1 Topic
-
Analysis Framework
-
Performance Analysis3 Topics
-
Mathematical Analysis2 Topics
-
Sorting AlgorithmSorting Algorithm10 Topics
-
Searching Algorithm6 Topics
-
Fundamental of Data StructuresStacks
-
Queues
-
Graphs
-
Trees
-
Sets
-
Dictionaries
-
Divide and ConquerGeneral Method
-
Binary Search
-
Recurrence Equation for Divide and Conquer
-
Finding the Maximum and Minimum
-
Merge Sort
-
Quick Sort
-
Stassen’s Matrix Multiplication
-
Advantages and Disadvantages of Divide and Conquer
-
Decrease and ConquerInsertion Sort
-
Topological Sort
-
Greedy MethodGeneral Method
-
Coin Change Problem
-
Knapsack Problem
-
Job Sequencing with Deadlines
-
Minimum Cost Spanning Trees2 Topics
-
Single Source Shortest Paths1 Topic
-
Optimal Tree Problem1 Topic
-
Transform and Conquer Approach1 Topic
-
Dynamic ProgrammingGeneral Method with Examples
-
Multistage Graphs
-
Transitive Closure1 Topic
-
All Pairs Shortest Paths6 Topics
-
BacktrackingGeneral Method
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
Participants2253
The divide-and-conquer approach can be used to arrive at an efficient sorting method different from merge sort.In merge sort,the file a[1 :n] was divided at its midpoint into sub arrays which were independently sorted and later merged. In quicksort, the division into two sub arrays is made so that the sorted sub arrays do not need to be merged later. This is accomplished by rearranging the elements in a[l:n] such that a[i] < a[j] for all i between 1 and m and all j between m + 1 and n for some m, 1< m < n. Thus, the elements in a[l:m] and a[rn + 1:n] can be independently sorted. No merge is needed.The rearrangement of the elements is accomplished by picking some element of a[],say t = a[s],and then reordering the other elements so that all elements appearing before t in a[1:n] are less than or equal to t and all elements appearing after t are greater than or equal to t. This rearranging is referred to as partitioning.
Function Partition of Algorithm 8(due to C.A.R. Hoare)accomplishes an in place partitioning of the elements of a[m:p – 1].It is assumed that a[p] >a[m] and that a[m] is the partitioning element. If m = 1 and p-1 = n, then a[n + 1]must be defined and must be greater than or equal to all elements in a[1:n]. The assumption that a[m] is the partition element is merely for convenience; other choices for the partitioning element than the first item in the set are better in practice. The function Interchange(a,i,j) exchanges a[i] with a[j].

Using Hoare’s clever method of partitioning a set of elements about a chosen element,we can directly devise a divide-and-conquer method for completely sorting n elements. Following a call to the function Partition, two sets S1 and S2 are produced. All elements in S1 are less than or equal to the elements in S2. Hence S1 and S2 can be sorted independently. Each set is sorted by reusing the function Partition. Algorithm 9 describes the complete process.

Performance Measurement
Quick Sort and Merge Sort were evaluated on a SUN work station 10/30.In both cases the recursive versions were used.For Quick Sort the Partition function was altered to carry out the median of three rule (i.e.the partitioning element was the median of a[m],a[[(m+p – 1)/2]]and a[p 1]).Each data set consisted of random integers in the range (0, 1000). Tables 1 and 2 record the actual computing times in milliseconds. Table 1 displays the average computing times.For each n, 50 random data sets were used. Table 2 shows the worst-case computing times for the 50 datasets. Scanning the tables,we immediately see that Quick Sort is faster than Merge Sort for all values. Even though both algorithms require 0(n logn) time on the average, Quick Sort usually performs well in practice.

inputs

random inputs