Properties of Sorting Algorithms

Stability, Adaptability and In-Placedness of certain Sorting Algorithms

Selection Sort

Find the smallest value in the collection of items. Swap it with the first element. This is now apart of our sorted section. Find the smallest number in the unsorted section, swap it with the second element. This is not apart of our sorted section. Etc, etc.

Unstable, Non-adaptive, In-place

Bubble Sort

Compares values in pairs from left to right. Swaps pairs of values if they are out of order. Larger values “bubble” up to the end. If it does a sweep of the array where no swaps are performed, it stops. If the last element of the data is the smallest, this leads to a worst-case time complexity.

Stable, Adaptive, In-place

Take the first element of the array and treat it as sorted. Take the next element and insert it into this sorted part of the array such that order is preserved. Repeat.

Insertion Sort

Stable, Adaptive, In-place

Merge Sort

Split the array into two roughly equal sized part. Recursively sort these partitions. Merge the two now-sorted partitions into a sorted array. (Note, an array of size 1 is already sorted)

Stable, Non-Adaptive, Out-of-place

Naive Quick-Sort

Take the first value in your array. Use this as your pivot. Partition the array so that all elements to the left of the pivot are less than or equal to the pivot. Recursively sort the partitions.

Unstable, Non-adaptive, In-place

Median-Of-Three Quick-Sort

Take the middle number out of the value in the first, middle and last index of your array. Use this as your pivot. Partition the array so that all elements to the left of the pivot are less than or equal to the pivot. Recursively sort the partitions.

Unstable, Non-adaptive, In-place

Radix Sort

Decompose our sorting keys into individual symbols. Ideally, the range of symbols is very small. Stable sort based on last element of the key. Then on second last element… all the way to first element

Stable, Non-adaptive, Out-of-place, Non-comparative