Labyrinth - sorting II

Summary

Sorting algorithms

	Comparison based?	In-place?	Stable?
optimized bubble sort	Y	Y	Y
selection sort	Y	Y	N
insertion sort	Y	Y	Y
merge sort	Y	N, extra space	Y
quick sort	Y	Y	depends on partitioning strategy
counting sort	N	N, extra space	depends on implementation
radix sort	N	N, extra space	depends on per-digit sorting algorithm

Performance

with different input arrays
to sort in non-decreasing(ascending but allowing for duplicates) order

	Random	Sorted Non-decreasing	Sorted Non-increasing	Almost Sorted Non-decreasing	Almost Sorted Non-increasing	Many Duplicates
optimized bubble sort
selection sort
insertion sort
merge sort
quick sort
randomized quick sort
counting sort

bubble and insertion sort are not entirely useless; if we know that the array will already be mostly sorted, they may be faster then merge/quick sort

Concept

Swap

exchange two elements
temporary storage uses only space regardless of how many swaps are done

java

void swap(int a[], int i, int j) { // swap array elements i and j
	int temp = a[i]; // O(1) space
	a[i] = a[j];
	a[j] = temp;
}

Minimum swaps to sort an array

each cycle of n elements takes n - 1 swaps

In-place sorting

only require extra space
exclusively using swap

Stable sorting

relative order of elements with the same value is preserved
using < instead of <= when determining when a swap should occur

Unsorted vs Sorted arrays

sorting makes the array easier to work with

	Unsorted	Sorted
search	linear search,	binary search,
min/max	linear search,	first and last index,
kth smallest/largest	linear search, quickselect,	k or (last - k) index,
duplicates	nested loops,	duplicates are adjacent,
counting repititons	hash table	duplicates are adjacent,
set intersection/union (without repitition)	nested linear search,	nested binary search, merge from merge sort,
two sum	nested loops,	two pointer approach,
count within range	hash table	two pointer approach,

Application

Search

sorting is not necessarily the best solution in all cases

Java blackbox sorting

Collections.sort()
- modified merge sort(tim sort)
Arrays.sort()
- modified merge sort(tim sort) for objects
- dual-pivot quick sort for primitive types

Leetcode: Shortest Unsorted Continuous Subarray

naive sort then check

java

int len = nums.length;
int[] sorted = Arrays.copyOf(nums, len);

Arrays.sort(sorted); // O(n log n)

int l = len, r = 0;

for (int i = 0; i < len; i++) { // O(n)
	if (nums[i] != sorted[i]) {
		l = Math.min(l, i);
		r = Math.max(r, i);
	}
}

return r - l >= 0 ? r - l + 1 : 0;