# Sorting

- Define sorting: permuting the sequence to enforce some order.
- Brute force Approach: $O(n! \times n)$. 
Here n! is for finding out all the permutations for a list of number and n is for traversing all the permutations to pick the relevant one. 



## Sorting Terminologies

__Stability__
- __Definition__: A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
- __Importance:__
    - preserving order - values could be orders and chronological order may be important. 
    - sorting tuples - sort on first column, then on second column. s

- __Example__: Bubble Sort, Insertion Sort, Selection Sort etc. 

__In-Place Sorting__

- __Definition__: In-Place Sorting algorithms uses constant extra space to produce the output. <br>
- **Example:** Insertion Sort, Selection Sort


Insertion Sort
--------------
**Explain:** <br> 
- 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:**
 
  ```c++
  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:** Yes Stable, because swap only when strictly >. Had it been >=, it would be unstable
- **In Place Sorting**
- **Complexity:** $O(n^2)$
- **Auxiliary Space:** O(1)
- **Boundary Cases:** Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
- **Uses:** Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

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.
- Works by repeatedly swapping the adjacent elements if they are in wrong order.

**Pseudo code:**
 
  ```c++
  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)$ ( Worst Case ) $O(n)$ Best Case
- **Auxiliary Space:** O(1)
- **In Place Sorting** 
- **Boundary Cases:** Bubble sort takes minimum time ( Order n ) when elements are already sorted. 


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

Selection Sort
-----

**Explain**
- Works by repeatedly finding the minimum element from unsorted part and putting it at the beginning.
- The algorithm maintains two subarrays in a given array.
    - The subarray which is already sorted.
    - Remaining subarray which is unsorted.
- In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray.

**PseudoCode**
```c++
void selectionSort(int arr[], int n)  
{  
    int i, j, min_idx;  
  
    // One by one move boundary of unsorted subarray  
    for (i = 0; i < n-1; i++)  
    {  
        // Find the minimum element in unsorted array  
        min_idx = i;  
        for (j = i+1; j < n; j++)  
        if (arr[j] < arr[min_idx])  
            min_idx = j;  
  
        // Swap the found minimum element with the first element  
        swap(&arr[min_idx], &arr[i]);  
    }  
}  
```

**Time Complexity**: $O(n^2)$ <br>
**Space Complexity**: O(1)

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:**
  ```c++
  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
- **Time Complexity**: $O(n + \max(a[i]))$
- why not just put the element there? if numbers/value, can do. Else, could be objects
- **Space Complexity**: $O(n + \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

-- --