Quick Sort and Merge Sort
Activity Outcomes:
This lab teaches you the following topics:
- How to sort the input data using Quick and Merge sort
Introduction
Quick Sort
Â
Quicksort is a fast sorting algorithm, which is used not only for educational purposes, but widely applied in practice. On the average, it has O(n log n) complexity, making quicksort suitable for sorting big data volumes. The idea of the algorithm is quite simple and once you realize it, you can write quicksort as fast as bubble sort.
Algorithm
Â
The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:
- Choose a pivot value. We take the value of the middle element as pivot value, but it can be any value, which is in range of sorted values, even if it doesn’t present in the array.
- Rearrange elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and all elements greater than the pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Notice, that array may be divided in non-equal parts.
- Sort both Apply quicksort algorithm recursively to the left and the right parts.
Partition algorithm in detail
Â
- There are two indices i and j and at the very beginning of the partition algorithm i points to the first element in the array and j points to the last one.
- Then algorithm moves i forward, until an element with value greater or equal to the pivot is found.
- Index j is moved backward, until an element with value lesser or equal to the pivot is found.
- If i ≤ j then they are swapped and i steps to the next position (i + 1), j steps to the previous one (j – 1).
- Algorithm stops, when i becomes greater than j.
- After partition, all values before i-th element are less or equal than the pivot and all values after j-th element are greater or equal to the pivot.
Merge Sort
Â
Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarrayA[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.
Algorithm
Â
To sort A[p .. r]:
- Divide Step
If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].
- Conquer Step
Conquer by recursively sorting the two subarraysA[p .. q] and A[q + 1 .. r].
- Combine Step
Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q
+ 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).
Note that the recursion bottoms out when the subarray has just one element, so that it is trivially sorted.
Lab Activities:
Activity 1:
Write a function to sort array elements using quick sort
Â
Solution:
Void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i<= j)
{
while (arr[i] <pivot) i++;
while (arr[j] >pivot) j–;
if (i<= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j–;
}
};
/* recursion */
if (left<j)
  quickSort(arr, left, j);
if (i<right)
  quickSort(arr, i, right);
}
Activity 2:
Write a function to sort array elements using merge sort
Â
Solution:
Void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size – 1);
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
 {
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
// m – size of A
// n – size of B
// size of C array must be equal or greater than
// m + n
void merge(int m, int n, int A[], int B[], int C[])
{
int i, j, k;
i = 0;
j = 0;
k = 0;
while (i< m && j < n)
{
if (A[i] <= B[j])
{
C[k] = A[i]; i++;
}
else
{
C[k] = B[j];
j++;
}
k++;
}
if (i< m)
{
for (int p = i; p < m; p++)
{
}
}
else
{
C[k] = A[p];
k++;
for (int p = j; p < n; p++)
{
C[k] = B[p]; k++;
}
}
}
Related linksÂ
Single link list         Stack        AVL Trees       Binary search      Counting Sort
Doubly link list        Queue        Graphs         Bubble Sort        Radix sort
Circular link list        Binary search tree    Hashing     Insertion Sort     Bucket Sort
Josephus Problem      Tree Traversal        Heaps         Quick Sort       Merge Sort
At Cui tutorial, courses, past papers and final year projects
#tutorial #cui #pastpaper #courses