Sorting

Notes on sorting algorithms, time complexity bounds, and binary search patterns.

58 sec read

These are my notes to help me understand sorting and stuff easier. Okay sorting, remember to use sorting during a problem in case it makes the problem alot easier. many times when someone says that the problem can be solved in O(k * N * log N) times where k is any constant and N is just number of elements being processed, the N log N part is likely quicksort or merge sort.

$O(n^2)$ sort#

Bubble sort

Really simple, go through whole array N time, each time swap adjacent elements that are not in correct order. visually, it looks like elements rising top the top correctly.

C++

for (int i = 0; i < n; i++) {    for (int j = 0; j < n - 1; j++) {  // important n-1 bound, we check one                                       // after j rookie mistake...        if (array[j] > array[j + 1]) {            swap(array[j],                 array[j + 1]);  // pattern is swap jth with j+1th.        }    }}

why O(n²)?

because the worst case would be if entire thing was reversed, that would mean that each element at some (i)ndex would have to do size()-i swaps. thus it would be (n-1) + 2 + 1 swaps which is $\frac{n(n-1)}{2}$

$O(n\log(n))$ sort#

Merge Sort

think of it as just taking the data you have and spliting it into two parts and keep spliting until you get to the end and then merge the sorted parts recursively.

actually dont worry about it that much, just use sort(v.begin(),v.end()).

Binary Search#

C++

int k = 0;  // think of k steps we have taken towards goal xfor (int b = n / 2; b >= 1;     b /= 2) {  // b is modifier we are testing out upon k.    while (k + b < n && array[k + b] <= x) k += b;}if (array[k] == x) {    // x was found at index k}

O(n2)O(n^2)O(n2) sort#