Sorting Algorithms

#computerscience

Sorting Algorithm

is an algorithm used for rearranging a given array or list in a specific manner according to a comparison operators on the elements. The comparison operator is used to decide the new order of elements in the perspective data structure.

Some of the most well-known sorting algorithms are:

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Heap Sort

Bubble Sort

is one of the simplest sorting algorithms. Bubble sort works by repeatdly swapping the adjacent elements if they are in the wrong order. This algorithm is not advised for a large data sets, because of it's high time complexity.

Selection Sort

Considering we're sorting a list/array in ascending order, selection sort sorts a list by repeatdly finding the minimum element from the unsorted part and shifting it to the beginning of the array.

Insertion Sort

Just like Bubble Sort, insertion sort is one the simplest sorting algorithms. The array of list is split into two parts. Sorted and unsorted part. The values from the unsorted are separated picked and placed at the correct position in the sorted part.

Merge Sort

A sorting algorithm that works by dividing an array into smaller subarrays. The subarrays are then sorted, and then merging the sorted subarrays back together to form the final sorted array. This process is repeated until the entire array/list is sorted. One of the main advantages of merge sort is the time complexity of O(n log n), which means it can sort large set of arrays relatively quickly and efficient.

Quick Sort

Like merge sort, quick sort picks picks an element as a pivot and partitions the given array around the picked pivot. It partitions an array and calls itself recursively twice to solve the two resulting subarrays. Quick Sort is highly efficient for large sets of data with a time complexity of O(n2).

Heap Sort

Similar to selection sort where we find the minimum element and place the minimum element at the beginning. This process is repeated until the entire array/list is sorted. Heap Sort is not very efficient sorting algorithm when working with highly complex data. It is also unstable, and might rearrange the relative order.

Conclusion

Sorting Algorithm is a set of instructions that take an array or list as an input and arrange an item into a particular order. The sorts mostly in numerical or alphabetical order, and can be in ascending or descending order.

Thank you!
Jonny

Top comments (9)

Medea • Jan 26 '23

I didn't know that there were this many sorting algorithms-

cubiclesocial • Jan 28 '23

Any basic concept that takes O(N log N) or worse time that is a common operation in computing generally has many different algorithms to optimize for various scenarios. Many devs wander down the "general purpose sorting algorithm" rabbit hole thinking they will be the first to beat O(N log N) time.

When designing an optimal sorting algorithm for practical use, you actually want to combine 3-4 different classical sorting algorithms that kick in at different points during the sorting operation to overcome the weaknesses of the other algorithms. The net gain by doing so is roughly 30% faster over any single algorithm. Every sorting algorithm has different Big-O for best, average, and worst case. It's the worst case that you want to avoid. Big-O comes with C as well (constant time per operation). The functionally correct notation is C * O(N log N). Some single sorting algorithms have O(N log N) for all cases but the caveat is they come with a very large hidden C value that largely negates the overall apparent benefits (e.g. allocating memory, which is an expensive operation).

Maintaining locality during the sorting operation helps keep data in the onboard CPU caches of modern computer systems. If you are able to keep data in the L1 cache, then the CPU doesn't have to go far to get the data. Even L2/L3 caches are a lot faster than RAM accesses. And RAM accesses are obviously a lot faster than disk I/O.