Sort Algorithms

Intro

Example are on Github repo https://github.com/Stopaloglu16/LearningCsharp/tree/master/Src/AdvancedTopics/DataStructures 

Bubble Sort

Repeatedly compares and swaps adjacent elements until get in order 

Time O(n^2), space O(1)

Used if

• complexity does not matter

• short and simple code is preferred

Selection Sort

Find the minimum value of an array by iterating through each element

Time O(n^2), space O(1)

Used when

• a small list is to be sorted

• cost of swapping does not matter

• checking of all the elements is compulsory

• cost of writing to a memory matters like in flash memory (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)

Insertion Sort

Builds the sorted array one element at a time by repeatedly picking the next item and inserting it into its correct position within the sorted portion of the array

Time O(n^2), space O(1)

Merge Sort

Divides the array into halves, recursively sorts each half, and then merges the sorted halves back together

Time: O(n log(n)),  Space: O(n)

Quick Sort

Picks a pivot element, partitions the array into two halves around the pivot, and recursively sorts the two halves.

Time average: O(n log(n)), time:  worst: O(n^2), space: O(log(n))

Used when

• the programming language is good for recursion

• time complexity matters

• space complexity matters

Heap Sort

Builds a max-heap (or min-heap) from the array and then repeatedly extracts the maximum (or minimum) element and rebuilds the heap until the array is sorted

Time: O(nlog n) Space: O(1)

Counting Sort

Counts the occurrences of each element, uses that count to place elements into the correct position in the output array

Time, Space: O(n+k), where k is the range of the non-negative key values

• there are smaller integers with multiple counts.

• linear complexity is the need.

Radix Sort

Sorts numbers by processing individual digits (or groups of digits) starting from the least significant digit to the most significant digit

Time: O(n+k) k being the space used to hold counts, indices, and output arrays  Space: O(n)

Bucket Sort

Divides the array into several "buckets," sorts each bucket individually (usually using another sorting algorithm), and then combines the buckets.

Time: O(n^2) Space: O(n+k)

Shell Sort

Sorting further elements first effectively reduces the interval between the elements that still need to undergo the sorting process 

Time: O(n^2) Space: O(1)