Sorting
- An invariant is a condition that remains unchanged while an algorithm runs.
- A sort is stable if the order of elements with the same key is retained.
Bubble Sort
-
Summary
- Each inner iteration ensures the largest/smallest is at the end by swapping.
- After each inner iteration, the sorted element is the largest/smallest element at the end.
- Each outer iteration excludes the sorted elements at the end.
-
Principle
Selection Sort
-
Summary
- Each inner iteration finds out the index of the smallest/largest element
- Swap the smallest/largest with the first element, hence making it sorted
- Each outer iteration excludes the sorted elements.
-
Principle
-
Notes
- Improve performance by reducing number of swapping.
Insertion Sort
-
Summary
- Store the marked element temporarily.
- Compare the marked element to each partially sorted element.
- Shift the element to the right if it's smaller/larger than the marked element.
- Repeat until the right spot for the marked element is found.
- Insert the marked element into the empty spot.
-
Principle
-
Notes
- Works best with partial sorted data
Counting Sort
-
Summary
- Counting sort determines, for each input element x, the number of elements less than x.
-
Algorithm
- countingSort(array, size)
- max <- find largest element in array
- initialize count array with all zeros
- 0 -> size by 1
- find the total count of each unique element and store the count at jth index in count array
- 1 -> max by 1
- find the cumulative sum and store it in count array itself
- size -> 1 by 1
- decrease cumulative count of each element by 1
- use it as the new index and restore the element to array
- countingSort(array, size)
-
Pros
- No comparison between elements
-
Cons
- When the integers are very large, the array of that size has to be made.
-
Usage
- There are smaller integers of multiple counts.
- linear complexity is the need.