Problem #QuickSort

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

1. Always pick first element as pivot.
2. Always pick last element as pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot.

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

private void sort(int[] arr, int low, int high) {
	// TODO Auto-generated method stub
	if(low < high){
		int pivot = partition(arr, low, high);
		sort(arr, low, pivot - 1);
		sort(arr, pivot + 1, high);
	}
}

private int partition(int[] arr, int l, int r){
    int pivot = arr[r], i = l;
    for(int j = l; j < r; j++){
        if(arr[j] <= pivot){
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, r);
    return i;
}

private void swap(int[] arr, int i, int r){
    int tmp = arr[i];
    arr[i] = arr[r];
    arr[r] = tmp;
}

Solution of above recurrence is also O(nLogn)

Although the worst case time complexity of QuickSort is O(n2) which is more than many other sorting algorithms like Merge Sort and Heap Sort, QuickSort is faster in practice, because its inner loop can be efficiently implemented on most architectures, and in most real-world data. QuickSort can be implemented in different ways by changing the choice of pivot, so that the worst case rarely occurs for a given type of data. However, merge sort is generally considered better when data is huge and stored in external storage.

See Problem #215. Kth Largest Element in an Array.

Problem #Merge Sort

Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following C implementation for details.

private void sort(int[] arr, int l, int r) {
	// TODO Auto-generated method stub
	if(l < r){
		int m = l + (r - l)/2;
		sort(arr, l, m);
		sort(arr, m + 1, r);
		mergesort(arr, l, m, r);
	}
}

private void mergesort(int[] arr, int l, int m, int r) {
	int[] left = new int[m - l + 1];
	int[] right = new int[r - m]; 
	for(int i = 0; i < left.length; i++)
		left[i] = arr[i + l];
	for(int i = 0; i < right.length; i++)
		right[i] = arr[m + 1 + i];
	int l1 = 0, r1 = 0, k = l;
	while(l1 < m - l + 1 || r1 < r - m){
		if(r1 >= r - m || (l1 < m - l + 1 && left[l1] <= right[r1])){
			arr[k] = left[l1];
			l1++;
		}else{
			arr[k] = right[r1];
			r1++;
		}
		k++;
	}
}

Time complexity of Merge Sort is \Theta(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.

Problem #Count Inversions

inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

	public static int inversion_merge(int[] nums, int l, int r){
		int count = 0;
		if(l < r){
			int m = (r - l) / 2 + l;
			count = inversion_merge(nums, l, m);
			count += inversion_merge(nums, m + 1, r);
			count += inversion_mergeSort(nums, l, m, r);
		}
		return count;
	}
	
	public static int inversion_mergeSort(int[] nums, int l, int m, int r){
		int[] left = new int[m - l + 1];
		int[] right = new int[r - m];
		int count = 0;
		for(int i = 0; i <= m - l; i++)
			left[i] = nums[i + l];
		for(int i = 0; i <= r - m - 1; i++)
			right[i] = nums[i + m + 1];
		int l1 = 0;
		int l2 = 0;
		int k = l;
		while(l1 <= m - l || l2 <= r - m - 1){
			if(l2 > r - m - 1 || (l1 <= m - l && left[l1] < right[l2])){
				count += l2;
				nums[k++] = left[l1];
				l1++;
			}else{
//				count += m - l - l1 + 1;
				nums[k++] = right[l2];
				l2++;
			}
		}
		return count;
	}