Summary of Basic Sorting Algorithms
April 23, 2020
Understanding algorithms and knowing how to use them is the key in computer science and software engineering. While we know the importance of learning algorithms, many people (including me) have a hard time doing it, and they often give up in the middle of learning.
When we google algorithms and data structures, I see many excellent articles and writings, but they are somewhat burdensome at first to read from the beginning to the end. That's why I created this writing. In this writing, I write a summary of basic sorting algorithms: 1) Selection sort 2) Bubble sort and 3) Insertion sort so that anyone who does not have any or limited knowledge of algorithms can easily start.
Algorithm

A set of instructions

In particular, it is about:
 What a program needs to do, and
 How the program has to solve


The two important keywords for the computers: "efficiency" and "tradeoffs".
 To measure how efficient it is and know what we gain and lose, "Big O notation is used"

Big O notation is about:
 How much time it needs (the time complexity of an algorithm)
 How much memory it needs (the space complexity of an algorithm)

NOTE: By using Big O notation, we ignore external factors because it is hard to tell.
 For example, the speed of a processor
Big O

O(1)
 "Constant time"
 Regardless of a size of inputs
n
, a O(1) function always takes constant time.
 O(logn)

O(n)
 "Linear time"
 As a size of inputs grows, the complexity grows linearly as well.
 O(n logn)

O(n^k)
 When
k = 2
, we say it grows quadratically
 When
 O(k^n)
Sorting Algorithm
Definition
 Sorting is an organizing a set of items in a collection by some properties
Goal
 Making it easier to search, retrieve and read data
Criteria
 Time complexity

Space complexity (memory usage)
 Inplace algorithm: sort the existing dataset (= a risky operation)
 Outofplace algorithm: making new copy and sort it

Stability
 An algorithm is stable when the "relative order" of the elements is kept.
 For example, say that there is [1, 1, 3, 2, 4]
 If the first 1 and second 1 does not change their order, it is stable

Internal vs. External
 It is internal if applicable data can be kept in main memory
 Recursive vs. Nonrecursive

Comparison vs. Noncomparison
 There exists a comparison if a comparator is used to compare two items
NOTE
 We can sort in increasing (i.e, nondecreasing) or decreasing order (by a property)
 Items in a given dataset must be homogeneous (i.e, a comparison between numbers or between strings)
Selection Sort
Definition
 A selection sort algorithm is an algorithm that finds the smallest item and put it in a sorted list.
Pros
 Good to use if it is for a very small dataset
 Easy to implement
Cons
 Not efficient (Time complexity: O(n^2))
How to
 Compare a value of first item with values of rest of the items (i.e, from second to the end)
 If there is an item with a smaller value compare with the first item, switch their position
 Keep the very first item, and do comparison between the second item and the rest of items.
 Switch the position of second item and an item with smaller value (than the second one), if applicable
 Stops after the last element
Code
// JS
function selectionSort(items) {
// NOTE: If shallow copy is satisfactory
let clonedItems = items.slice();
let length = clonedItems.length;
for (let i = 0; i < length; i++) {
let selectedItemIndex = i;
for (let j = i + 1; j < length; j++) {
if (clonedItems[i] > clonedItems[j]) selectedItemIndex = j;
}
if (selectedItemIndex != i) {
let temp = clonedItems[i];
clonedItems[i] = clonedItems[selectedItemIndex];
clonedItems[selectedItemIndex] = temp;
}
}
return clonedItems
}
// TS
// Java
// Python