| Sorting algorithms |

Techniques for Sorting

In-place vs extra memory Analyze by counting compares and exchanges(array accesses)

1. Selection
2. Insertion
3. Bubble
4. Merge
5. Quick

1. Selection Sorting

Iterative and in-place sorting algorithm that divides the data structure in two sublists: the ordered one, and the unordered one

1. First, find the smallest item in the array, and exchange it with the first entry.
2. Then, find the next smallest item and exchange it with the second entry.
3. Continue in this way until the entire array is sorted.
4. This method is called selection sort because it works by repeatedly selecting the smallest remaining item.

Selection sort uses ~n2/2 compares and n exchanges to sort an array of length n.

public void sortArray(int[] input) {
		System.out.println("Selection Sort - ");

		for (int i = 0; i <= input.length - 2; i++) { // last element will be already sorted when we finish for second last
			int minIndex = i;
			int curr = input[i];
			for (int j = i + 1; j <= input.length - 1; j++) {
				if (input[j] < input[minIndex]) { // we compare everytime hence O(n^2) in total
					minIndex = j;
				}
			}
			input[i] = input[minIndex]; //we swap only once per one outer loop hence n exchange
			input[minIndex] = curr;
		}

	}

2. Insertion Sorting

Divides the data structure in two sublists: a sorted one, and one still to sort.

Initially, the sorted sublist is made up of just one element and it gets progressively filled.

For every iteration, the algorithm picks an element on the unsorted sublist and inserts it at the right place in the sorted sublist

1. Consider the cards one at a time, inserting each into its proper place among those already considered (keeping them sorted)
2. Make space for the current item by moving larger items one position to the right, before inserting the current item into the vacated position

For randomly ordered arrays of length N with with distinct keys, insertion sort uses ~N2/4 compares and ~N2/4 exchanges on the average. The worst case is ~ N2/2 compares and ~ N2/2 exchanges and the best case is N-1 compares and 0 exchanges.

public void sortArray(int[] input) {
		System.out.println("Insertion Sort - ");

		for (int i = 0; i < input.length; i++) {
			int j = i;
			while (j > 0 && input[j - 1] > input[j]) { // if its sorted array then this while block will not be executed making only N compares and no exchanges hence O(N)
				int temp = input[j - 1]; 
				input[j - 1] = input[j]; //worst case we always compare and exchange for every element with others at every iteration, hence O(n^2)
				input[j] = temp;
				j--;
			}
		}

	}

3. Bubble Sorting

Iterative sorting algorithm that imitates the movement of bubbles in sparkling water.

The bigger bubbles reach the top faster than smaller bubbles, and this algorithm works in the same way.

It iterates through the data structure and for each cycle compares the current element with the next one, swapping them if they are in the wrong order.

1. Adjacent swapping of i and i+1 if element at i+1 < i1
2. Continue so that end of iteration the max reaches at n-1 index
3. Adjacent swapping decreases at each iteration, since i has to compare with less elements because elements at end of array will start getting sorted

We can do small optimization when on the a complete iteration of inner loop while outer loop is on first iteration, if no swapping was done, we can break since we know its a sorted array(Best time complexity scenario)

public void sortArray(int[] input) {
		System.out.println("Bubble Sort - ");

		for (int i = input.length - 1; i >= 1; i--) {
			boolean swapHappened = false;
			for (int j = 0; j <= i - 1; j++) {
				if (input[j] > input[j + 1]) {
					int temp = input[j];
					input[j] = input[j + 1];
					input[j + 1] = temp;
					swapHappened = true;
				}
			}
			if (!swapHappened) {
				// if no swap happened on first pass, we know its sorted array
				// no need to check and compare further
				System.out.println("No swapping so we break " + i);
				break;
			}
		}
	}

4. Merge Sorting

Out of place algorithm since we need extra array to merge n/2 two arrays on each sub-step

Uses divide and conquer where we divide given array into two parts.

Combine two ordered arrays to make one larger ordered array.

Can be implemented iteratively or recursively, using the Top-Down and Bottom-Up algorithms respectively

1. Each part gets broken down further into two parts and so on.
2. We divide each part until we reach single element for one subarray.
3. Once two parts are sorted on their own then we merge those two sorted parts.
4. Merge takes O(n), sort recursive takes O(logn) at worst, hence total O(nlogn)

public void sortArray(int[] input) {
	System.out.println("Merge Sort - ");
	sort(input, 0, input.length - 1);

}
private void merge(int[] arr, int left, int mid, int right) {
		int leftP = left;
		int rightP = mid + 1;
		int[] dummy = new int[right + 1];
		int dummyIndex = 0;

		while (leftP <= mid && rightP <= right) {
			if (arr[leftP] < arr[rightP]) {
				dummy[dummyIndex++] = arr[leftP++];
			} else {
				dummy[dummyIndex++] = arr[rightP++];
			}
		}

		while (leftP <= mid) {
			dummy[dummyIndex++] = arr[leftP++];
		}

		while (rightP <= right) {
			dummy[dummyIndex++] = arr[rightP++];
		}

		dummyIndex = 0;

		for (int i = left; i <= right; i++) {
			arr[i] = dummy[dummyIndex++];
		}
}

public void sort(int[] arr, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			sort(arr, left, mid);
			sort(arr, mid + 1, right);
			merge(arr, left, mid, right);
		}
	}

5. Quick Sorting

Also uses divide and conquer

In place algorithm unlike merge sort

Divide in smaller partitions and sort them recursively until the data structure is sorted.

1. After one iteration one element(pivot) will be sorted in its right place.
2. Elements left to it will be less than it, right to it will be more than it.

public class QuickSort  {

    public void sortArray(int[] input) {
		quickSort(input, 0, indx);
	}

	public int partition(int nums[], int left, int right) {
		int pivot = nums[right]; //consider the last element is pivot for us
		int i = left - 1;

		while (left < right) {
			if (nums[left] < pivot) {
				int temp = nums[left];
				nums[left] = nums[++i];
				nums[i] = temp;
			}
			left++;
		}

		int temp = nums[i + 1];
		nums[i + 1] = pivot;
		nums[right] = temp;
		return i + 1;
	}

	public void quickSort(int[] input, int left, int right) {
		if (left < right) {
			int partition = partition(input, left, right);
			quickSort(input, left, partition - 1);
			quickSort(input, partition + 1, right);
		}

	}

}