Algoritma dan Struktur Data : Merge Sort dan Quick Sort
Divide & Conquer
General Plan
Divide the problem into a number of sub-problems ideally of about equal size. Sub-problem: smaller instances of the same problem.
Conquer the sub-problems: solving them (typically) recursively. If the sizes are small enough: solve the sub-problems in a straightforward manner (or using different algorithm).
If necessary, the solutions to the sub-problems are combined to get a solution to the original problem
Illustration
Advantages
- Easy to model
- Parallelizable
- Efficient
- Powerful for difficult problems
Merge Sort
Idea
Divide : Divide the n-element sequence to be sorted into two sub-sequences of n/2 elements each.
Conquer : Sort the two sub-sequences recursively using merge sort.
Combine : Merge the two sorted sub-sequences to produce the sorted answer.
Pseudocode
Example
Running Time
Quicksort
- Not difficult to implement
- Works well for a variety kinds of input data
- Substantially faster in typical application
- In-place
Idea
Given an array A[p..r]
Divide :
Partition the array A[p..r] into two (possibly empty) subarrays :
- A[p..q-1] : each element is <= A[q]
- A[q+1..r] : each element is > A[q]
Conquer: Sort both subarrays by recursive calls to quicksort
Combine: The subarrays are already sorted, the entire array A[p..r] is now sorted
Pseudocode
Example
Running Time
Running time of Quicksort depends on the partitioning :
Worst-case partitioning : Partitioning produces one subproblem with n-1 elements and one with 0 elements.
Best case partitioning: Partitioning produces two subproblems, each of size no more than n/2
Randomized Partitioning
With randomized partitioning, expected running time of quicksort : O(n lgn)
Posting Komentar