Sorting Algorithms

Bubble Sort

On each pass, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped.

This process continues until all elements are sorted.

Best-time: O(n) (1 pass only – if they are all ordered)

Worst-time: O(n^2)

Selection Sort

Finds the largest number in the list and places it last. Then it finds the second largest and places it next to the last, and so on.

Worst-time: O(n^2)

Insertion Sort

From left to right it identifies a list with a number of elements that increases by one in each pass. It starts with the first element in the list.

It looks at the new element it’s considering and inserts it in the right place in the imaginary sublist.

Worst-time: O(n^2)

Merge Sort

Divides the array into two and applies merge sort recursively.

Average-time: O(n log(n))

Worst-time: O(n log(n))

Quick Sort

First the algorithm selects an element in the array to use as pivot.

Then it divides the array into two parts such that all the elements in the first part are less than or equal to the pivot and all the elements in the second part are greater than the pivot.

To do this it searches for the first element from the left forward that is greater than the pivot, then searches for the first element from the right backwards that is less than or equal to the pivot. Then it swaps them.

Then it does the same thing in each halve.

It does this in the array itself, so there’s not need to merge them afterwards.

Average-time: O(n log(n))

Worst-time: O(n^2)

Heap Sort

1. Creates a heap object

2. Add all elements to the heap

3. Removes all elements form the heap

Time: O(n log(n))

Bucket Sort

Each bucket holds the elements with the same key value.

Radix Sort

Divides the keys into subgroups based on their radix position.