Basic Algorithims - Sorting

May 27th, 2022

#cs fundamentals

Time Complexity Examples:

1
2
3
4
5
6
7
8
for (var i = 0; i < n; i++) {
  let minIndex = i;
  for (var j = i; j < n; j++) {
    if (unsortedList[j] < unsortedList[minIndex]) {
      minIndex = j;
    }
  }
}

This is O(n * (n - 1) / 2) which is reducible to O(n^2).

Nested Loop w/ inner Loop doing j + 1 look ups:

1
2
3
4
5
6
7
8
9
10
11
for (var i = n - 1; i >= 0; i--) {
    let swapped = false;
    for (var j = 0; j < i; j++) {
        if (unsortedList[j] > unsortedList[j + 1]) {
            const temp = unsortedList[j];
            // this will always be ok! 👇
            unsortedList[j] = unsortedList[j + 1];
            unsortedList[j + 1] = temp;
            swapped = true;
        }
    }