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

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard Problems1 Topic
Participants2253
The divideandconquer 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 p1 = 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 divideandconquer 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 worstcase 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.