2020-03-19 12:33:50 +05:30

2.9 KiB

Sorting 3

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)
  • 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?