Sorting Algorithms
Welcome!! In the article, we will learn an introduction to sorting algorithms
Sorting algorithms are the methods that are used to re-order the items in the list in either ascending or descending order or lexicographical order. But why do we need sorting algorithms? Sorting an unordered list of numbers greatly increases the power you have over those numbers. Sorted lists allow you to better pick apart the information hiding inside the numbers.
Get Dhathri Vupparapalli’s stories in your inbox
Join Medium for free to get updates from this writer.
Let's look at the sorting algorithms which are widely used:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Quick Sort
- Merge Sort
- Heap Sort
Time complexities of Sorting algorithms
Bubble Sort
Bubble sort traverses through the array of numbers and looks at the adjacent numbers. Bubble sort will then swap the lower number on the left, towards the beginning of the array, and the higher number on the right, towards the end. This process is repeated and bubble sort will continue to loop through the array until no swaps are made, thus leaving a sorted array. The time complexity of Bubble sort O(n²) and is very slow. Bubble sort can be used when there are little swaps required to sort a list.
Selection Sort
Selection sort works by splitting the input array into two parts: Initially, the whole array will be unsorted. Tae the min element from the unsorted part and shift toward the end of the sorted array. Repeat the same process until the whole array is sorted. Selection sort is also not an efficient algorithm with a Time complexity of O(n²) but it is better than Bubble sort when working with small lists.
Insertion Sort
Insertion sort is the same as the above two algorithms with the Time Complexity of O(n²). Insertion sort is the sorting mechanism where the sorted array is built having one item at a time. The array elements are compared with each other sequentially and then arranged simultaneously in some particular order. The analogy can be understood from the style we arrange a deck of cards. This sort works on the principle of inserting an element at a particular position, hence the name Insertion Sort.
Quick Sort
Quicksort is the best sorting algorithm. The name “Quick Sort” comes from the fact that quicksort is capable of sorting a list of data elements significantly faster (twice or thrice faster) than any of the common sorting algorithms. Sorting is done using a “pivot” element and pushing all the elements lesser than that to the left of it and the greater element to the right of it. Repeat the same process till the array is sorted.
Merge Sort
Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and Conquer. Merge sort repeatedly breaks down a list into several sublists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.
Heap Sort
Heap Sort is a comparison Based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.
Conclusion
In this article, we have seen what is sorting and also different sorting algorithms and their time complexities. We have also seen the best and worst sorting algorithms for both larger and smaller sets of lists.
