Back to Course


0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
In Progress
Lesson 19 of 43
In Progress

Quick Sort

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].

KodNest Capture37
Algorithm 8 : Partition the array a[m:p-1] about a[m]

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.

KodNest Capture38
Algorithm 9 : Sorting by partitioning

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.

KodNest Capture39
Table 1 : Average computing times for two sorting algorithms on random
KodNest Capture40
Table 2: Worst-case computing times for two sorting algorithms on
random inputs

New Report