Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

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

Given an array A of n elements:

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]

Compute the index q (pivot).


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

Try to avoid the worst-case partitioning by chosen the pivot randomly :

With randomized partitioning, expected running time of quicksort : O(n lg⁡n)

Sumber

Slide ASD : MergeSort dan QuickSort

http://informatika.unpar.ac.id/