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
