Lecture_Notes/imperfect_notes/pragy/Sorting 1.md

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 Given k, k <= n Partition array into two parts A, ||A|| = k and B, ||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)

---

Anagrams