Merge Sort
The merge sort algorithm divides input array in two halves and sort the two sub arrays respectively, then merge them to get the desired sorted array. As to the sorting method used for each half, merge sort algorithm use itself recursively.
Let A[0..n] be an array of n elements. The merge sort algorithm divides A to A[0..\(\frac n 2\)] and A[\(\frac n 2+1\)..n]. And it performs itself on the two sub arrays to make them sorted. Then it merges two sub arrays to get A[0..n] sorted. The diagram from Wikipedia illustrates the process of merge sort algorithm.
Algorithm 3 MergeSort
Input: An array A[0..n] of n elements.
Output: A[0..n] sorted in non-decreasing order.
- mergesort(A, 0, n)
Function mergesort(A, low, high)
- if low < high
- mid = (low + high)/2
- mergesort(A, low, mid)
- mergesort(A, mid+1, high)
- merge(A, low, mid, high)
- end if
Function merge(A, p, q, r)
Input: An array A[0..n] and three indices p, q and r with \(0 \le p \le q \lt r \le n\). Both sub arrays A[p..q] and A[q+1..r] are sorted in non-decreasing order.
Output: A[p..r] contains the elements from A[p..q] and A[q+1..r] sorted in non-decreasing order.
- B[p..r] is an auxiliary array
- i = p, j = q+1, k = p
- while (\(i \le q\)) and (\(j \le r\))
- if A[i] < A[j] then
- B[k] = A[i]
- i = i + 1
- else
- B[k] = A[j]
- j = j + 1
- end if
- k = k + 1
- end while
- if \(i \le q\) then
- B[k..r] = A[i..q]
- end if
- if \(j \le r\) then
- B[k..r] = A[j..r]
- end if
- A[p..r] = B[p..r]
A JAVA implementation of this algorithm can be found on GitHub Merge Sort.
Time complexity
The basic operation of merge sort algorithm is element comparison. Let C(n) be the number of element comparisons. For simplicity, assume n is a power of 2. If n = 1, C(n) = 0 because the algorithm does not perform any element comparison. If n > 1, in function mergesort(A, low, high), step 3 and step 4 perform C(\(\frac n 2\)) element comparisons. And step 5 calls function merge(A, p, q, r). It is easy to see the number of element comparison performed by function merge is between \(\frac n 2\) and n - 1. Thus, the minimum number of comparison is
$$C(n) = \begin{cases}0 & n=1 \\ 2C(\frac n 2) + \frac n 2 & n \ge 2 \end{cases}$$
Proceed to solve the recurrence by expansion as follows. Note: we assume \(n=2^k\).
$$\begin{align}C(n) & = 2C(\frac n 2) + \frac n 2 \\ & = 2^2C(\frac n {2^2}) + 2\frac n 2 \\ & = ... \\ & = 2^kC(\frac n {2^k}) + k\frac n 2 \\ & = 2^kC(1) + k\frac n 2 \\ & = \frac {nlogn} 2\end{align}$$
The maximum number of comparison is
$$C(n) = \begin{cases}0 & n=1 \\ 2C(\frac n 2) + n - 1 & n \ge 2 \end{cases}$$
Proceed to solve the recurrence by expansion as follows. Note: we assume \(n=2^k\).
$$\begin{align}C(n) & = 2C(\frac n 2) + n - 1 \\ & = 2^2C(\frac n {2^2}) + 2n - 2 - 1 \\ & = ... \\ & = 2^kC(\frac n {2^k}) + kn - 2^k-1 - 2^k-2 - ... - 2 - 1 \\ & = 2^kC(1) + kn - \sum\limits_{i=0}^{k-1} 2^i \\ & = kn - 2^k + 1 \\ & = nlogn - n + 1\end{align}$$
According to the analysis above, The time complexity of merge sort algorithm is \(C(n)=\Omega(nlogn) = O(nlogn) = \Theta(nlogn)\)
Quick Sort
The quick sort algorithm is another divide-and-conquer sorting algorithm. It divides the input array by a chosen pivot, so that all elements smaller than the pivot are at the left of it and all greater elements are at the right. This procedure is called partitioning or splitting. An important observation is that after splitting the array by the pivot, the pivot is in its correct position. Recursively perform the same splitting procedure on each side of the pivot until all elements are in their correct position, the array therefore is sorted. There are many different ways to choose a pivot in the array, here I will pick the first element as the pivot. However, it leads to quadratic running time in the worst case by always picking the first element as the pivot. This will be discussed later in the time complexity analysis of quick sort algorithm. The animation below from Wikipedia illustrates the idea of quick sort algorithm.
The pseudo code is described in QuickSort.
Algorithm 4 QuickSort
Input: An array A[0..n] of n elements.
Output: A[0..n] sorted in non-decreasing order.
- quicksort(A, 0, n)
Function quicksort(A, low, high)
- if low < high then
- w = split(A, low, high)
- quicksort(A, low, w-1)
- quicksort(A, w+1, high)
- end if
Function split(A, low, high)
Input: An array A[0..n] and two indices low and high with \(0 \le low < high \le n\).
Output: An index w with \(low \le w \le high\). And w is the correct position of A[low] in A[low..high].
- i = low
- x = A[low]
- for j = i + 1 to high
- if A[j] < x then
- i = i + 1
- if \(i \ne j\) then swap A[i] and A[j] comment: move the smaller element to the left
- end if
- end for
- swap A[low] and A[i] comment: i is the correct position of A[low]
- return i
A JAVA implementation of this algorithm can be found on GitHub Quick Sort.
Time complexity
The average case scenario
The time complexity of quick sort algorithm depends on the relative order of the elements in the input array. To analyse the average behavior of the algorithm, assume the distribution of each element in the input array is equally likely. Let C(n) be the number of elements comparisons performed by the quick sort algorithm. It is easy to see the number of elements comparison performed by split in step 2 is high - low - 1, which is n - 1 for high = n, low = 0. The recursive call in steps 3 and 4 cost C(w-1) and C(n-w). Based on the assumption of each element is equally likely to be the first element of the input array and thus chosen as the pivot, the probability that any element be the pivot is 1/n. Hence, the total number of comparison is
$$C(n) = (n-1) + \frac {1} {n} \sum\limits_{w=1}^n(C(w-1) + C(n-w))$$
Since
$$\sum\limits_{w=1}^nC(n-w)=C(n-1)+C(n-2)+...+C(0)=\sum\limits_{w=1}^nC(w-1)$$
Thus
$$C(n)=(n-1) + \frac {2} {n} \sum\limits_{w=1}^nC(w-1)$$
Multiply the equation by n
$$nC(n)=n(n-1) + 2\sum\limits_{w=1}^{n}C(w-1)$$
Replace n by n-1
$$(n-1)C(n-1)=(n-1)(n-2) + 2\sum\limits_{w=1}^{n-1}C(w-1)$$
Subtracting the above two equations
$$nC(n) - (n-1)C(n-1)=2(n-1) + 2C(n-1)$$
Rearrange the equation yields
$$\frac {C(n)} {n+1} = \frac {C(n-1)} {n} + \frac {2(n+1)} {n(n+1)}$$
Let \(D(n) = \frac {C(n)} {n+1}\)
$$D(n) = D(n-1) + \frac {2(n+1)} {n(n+1)}$$
Resolve the above equation
$$D(n) = 2\sum\limits_{i=1}^n\frac{i-1}{i(i+1)}=2\sum\limits_{i=1}^n\frac 1 j - \frac {4n} {n+1}=2lnn - \Theta(1)=\frac 2 {log e}log n-\Theta(1) \approx 1.44log n$$
Consequently,
$$C(n) = (n+1)D(n) \approx 1.44nlogn = \Theta(nlogn)$$
The worst case scenario
Suppose that in every call to quicksort, the pivot which is A[low], is the smallest element in the array. It results the w returned by split is equal to low. Then the next recursive calls will be quicksort(A, 0, -1) and quicksort(A, 1, n), and quicksort(A, 0, -1) will do nothing. Thus, if the input array is already sorted in non-decreasing order, the call sequence to quicksort is below:
quicksort(A, 0, n), quicksort(A, 1, n), ... , quicksort(A, n-1, n), quicksort(A, n, n)
These result in calls to split as following:
split(A, 0, n), split(A, 1, n), ... , split(A, n-1, n), split(A, n, n)
The number of elements comparison performed by split is high - low - 1. Thus, the total number of comparison done by quick sort algorithm in the worst case is
$$(n-1) + (n-2) + ... + 1 + 0 = \frac {n(n-1)} 2 = \Theta(n^2)$$
The scenario above however is not the only case that results in quadratic running time. If the algorithm always picks the smallest k elements with k is sufficiently small relative to n, the running time of quick sort algorithm is also quadratic. This can be improved to \(\Theta(nlogn)\) by always picking the median element as the pivot which splits the input array in balance. But the time complexity of the median finding algorithm needs to be considered carefully. Another approach to improve the quick sort algorithm is to choose the pivot randomly which will result in a very efficient algorithm. It will be discussed in my future post.
Reference:
Algorithm Design Techniques and Analysis by M.H. Alsuwaiyel
No comments:
Post a Comment