mirror of
https://github.com/dholerobin/Lecture_Notes.git
synced 2025-03-15 13:49:59 +00:00
3.7 KiB
3.7 KiB
Sorting
- define sorting: permuting the sequence to enforce order. todo
- brute force:
O(n! \times n)
Stability
- definition: if two objects have the same value, they must retain their original order after sort
- importance:
- preserving order - values could be orders and chronological order may be important
- sorting tuples - sort on first column, then on second column
Insertion Sort
- explain:
- 1st element is sorted
- invariant: for i, the array uptil i-1 is sorted
- take the element at index i, and insert it at correct position
- pseudo code:
void insertionSort(int arr[], int length) { int i, j, key; for (i = 1; i < length; i++) { key = arr[i]; j = i-1; while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; } arr[j + 1] = key; } }
- Stablility: Stable, because swap only when strictly >. Had it been >=, it would be unstable
- Complexity:
O(n^2)
Bubble Sort
- explain:
- invariant: last i elements are the largest one and are in correct place.
- why "bubble": largest unsorted element bubbles up - just like bubbles
- pseudo code:
void bubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) for (int j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); }
- Stability: Stable
- Complexity:
O(n^2)
Bubble Sort with window of size 3
- explain bubble sort as window of size 2
- propose window of size 3
- does this work?
- no - even and odd elements are never compared
Counting Sort
- explain:
- given array, first find min and max in O(n) time
- create space of O(max-min)
- count the number of elements
- take prefix sum
- constraint: can only be used when the numbers are bounded.
- pseudo code:
void counting_sort(char arr[]) { // find min, max // create output space // count elements // take prefix sum // To make it stable we are operating in reverse order. for (int i = n-1; i >= 0; i--) { output[count[arr[i]] - 1] = arr[i]; -- count[arr[i]]; } }
- Stability: Stable, if imlpemented correctly
- Complexity:
O(n + \max(a[i]))
- why not just put the element there? if numbers/value, can do. Else, could be objects
Radix Sort
- sort elements from lowest significant to most significant values
- explain: basically counting sort on each bit / digit
- Stability: inherently stable - won't work if unstable
- complexity:
O(n \log\max a[i])
Partition Array
Array of size
n
Givenk
,k <= n
Partition array into two partsA, ||A|| = k
andB, ||B|| = n-k
elements, such that|\sum A - \sum B|
is maximized
- Sort and choose smallest k?
- Counterexample
1 2 3 4 5
k = 3
bad: {1, 2, 3}, {4, 5}
good: {1, 2}, {3, 4, 5}
- choose based on n/2 - because we want the small sum to be smaller, so choose less elements, and the larger sum to be larger, so choose more elements
Sex-Tuples
Given A[n], all distinct find the count of sex-tuples such that
\frac{a b + c}{d} - e = f
Note: numbers can repeat in the sextuple
- Naive:
{n \choose 6} = O(n^6)
- Optimization. Rewrite the equation as
ab + c = d(e + f)
- Now, we only need
{n \choose 3} = O(n^3)
- Caution:
d \neq 0
- Once you have array of RHS, sort it in
O(\log n^3)
time. - Then for each value of LHS, count using binary search in the sorted array in
\log n
time. - Total:
O(n^3 \log n)
- Now, we only need