mirror of
https://github.com/dholerobin/Lecture_Notes.git
synced 2025-03-15 13:49:59 +00:00
2.9 KiB
2.9 KiB
Sorting 2
Merge Sort
- Divide and Conquer
- didive into 2
- sort individually
- combine the solution
- Merging takes
O(n+m)
time.- needs extra space
- code for merging:
// arr1[n1] // arr2[n2] int i = 0, j = 0, k = 0; // output[n1+n2] while (i<n1 && j <n2) { if (arr1[i] <= arr2[j]) // if <, then unstable output[k++] = arr1[i++]; else output[k++] = arr2[j++]; } // only one array can be non-empty while (i < n1) output[k++] = arr1[i++]; while (j < n2) output[k++] = arr2[j++];
- stable? Yes
- in-place? No
- Time complexity recurrence:
T(n) = 2T(n/2) + O(n)
- Solve by Master Theorem.
- Solve by algebra
- Solve by Tree height (
\log n
) * level complexity (O(n)
)
Intersection of sorted arrays
2 sorted arrays
1 2 2 3 4 9 2 3 3 9 9 intersection: 2 3 9
- calculate intersection. Report an element only once
- Naive:
- Search each element in the other array.
O(n \log m)
- Search each element in the other array.
- Optimied:
- Use merge.
- Ignore unequal.
- Add equal.
- Move pointer ahead till next element
Merging without extra space
- can use extra time
- if a[i] < b[j], i++
- else: swap put b[i] in place of a[i]. Sorted insert a[i] in b array
- so,
O(n^2)
time
Count inversions
inversion: i < j, but a[i] > a[j] (strict inequalities)
- naive:
O(n^2)
- Split array into 2.
- Number of inversions = number of inversions in A + B + cross terms
- count the cross inversions by example
- does number of cross inversions change when sub-arrays are permuted?
- no
- can we permute so that it becomes easier to count cross inversions?
- sort both subarrays and count inversions in A, B recursively
- then, merge A and B and during the merge count the number of inversions
- A_i B_j
- if A[i] > B[j], then there are inversions
- num inversions for A[i], B[j] = |A| - i
- intra array inversions? Counted in recursive case.
Find doubled-inversions
same as inversion just i < j, a[i] > 2 * a[j]
- same as previous. Split and recursilvely count
- while merging, for some b[j], I need to find how many elements in A are greater than 2 * b[j]
- linear search for that, but keep index
- linear search is better than binary search
Sort n strings of length n each
- T(n) = 2T(n/2) + O(n^2) = O(n^2)
is wrong
- T(n) = 2T(n/2) + O(n) * O(m) = O(nm\log n)
is correct. Here m = the initial value of n
.
I G N O R E
.
Bounded Subarray Sum Count
given A[N] can have -ve given lower <= upper find numbe of subarrays such that lower <= sum <= upper
- naive:
O(n^2)
(keep prefix sum to calculate sum in O(1), n^2 loop) - if only +ve,
O(n\log n)
using prefix sum - but what if -ve?