# 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__

__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