## Sorting Algorithms 2

## Quick Sort

This algorithm was developed by Tony Hoare in 1960. It is a divide and conquer algorithm.

**Algorithm is as follows**

- Select an element ‘pivot’ from the list.
- Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.
- Recursively sort the sub-lists of lesser elements and greater elements.

##### Code In C

void qsort(int v[], int left, int right) { int i, last; void swap(int v[], int i, int j); if(left >= right) return; swap(v, left, (left+right)/2); last = left; for(i = left+1; i <= right; i++){ if(v[i] < v[left]) swap(v, ++last, i); } swap(v, left, last); qsort(v, left, last-1); qsort(v, last+1, right); }

##### Time Analysis

Worst case : O(n²)

Best case : O(n log n)

Average case: O(n log n)

In the best case, each time the list is divided into two equal half. So there will be log n nested calls. And this operation is done n times.

Recurrence relation is T(n) = O(n) + 2T(n/2).

And also selecting the pivot plays a good role in time complexity. For already sorted list selecting the middle element or random element is better than selecting first or last element.

## Merge Sort

Merge sort was developed by John Von Neumann in 1945. It is also a divide and conquer algorithm. It always does a fewer comparison as compared to quick sort.

**Algorithm is as follows**

- Divide the element into n sub-lists of single elements. Now each sub-list is sorted since there is only one element.
- Repeatedly merge sub-lists to to produce a larger sub-list which should be in a sorted list. Until a n element single list is obtained.

##### Code in C

void msort(int a[], int low, int high) { void merge(int a[], int, int, int); int mid; if(low < high){ mid = (low + high)/2; msort(a, low, mid); msort(a, mid+1, high); merge(a,low,high,mid); } } void merge(int a[], int low, int high, int mid) { int i,j,k, c[50]; i = low; j = mid + 1; k = low; while((i <= mid) && (j <= high)){ if(a[i] < a[j]) c[k++] = a[i++]; else c[k++] = a[j++]; } while(i <= mid) c[k++] = a[i++]; while(j <= high) c[k++] = a[j++]; for(i = low; i < k; i++) a[i] = c[i]; }

##### Time Analysis

Worst case : O(n log n)

Best case : O(n log n)

Average case : O(n log n)