Algorithms 101: Sorting I

#computers

Sorting is very vital when it comes to the algorithms. As the name suggests sorting algorithms help to sort an unordered list or an array. The thing about sorting algorithms is they're easy in a manner but confusing af. Basically whenever I needed to sort anything while solving a problem I've always just googled it on the spot and implemented it but I figured its high time to stop that and learn these damn but important stuff once and for all. As usual, I believe writing about what I've read is the only way to make sure I can learn so another post on algorithms.

There are mainly six sorting algorithms. I like to divide them into three each where the first three are simple ones and the rest are a little complicated. And as we learn about them we can even call the first three are shitty in terms of time complexity and rest three are decent.

Bubble sort is simple af. It just cycles through the array and just compares the adjacent values. If the next number is smaller than the current then swap or else move on. So, it keeps the lower on the left and higher ones onto the right. This process is repeated until no swaps are left thereby leaving the sorted array. As reading this its clear that its insanely slow, with the worst time complexity of O(n²). But it can be used if the array is almost sorted leaving just a couple of numbers to sort.

bubbleSort(array)
for i< -1 to indexOfLastElement-1
if leftelement > rightelement
swap leftelement and rightelement
end 

Let's take an array consisting of elements {2,8,5,3,9,4,1}. So, the code will be as follows:

Selection sort is another simple af algorithm that is a slight improvement over the poor bubble sort. It works by splitting the array into two parts: the list of numbers being built from smallest to largest, and the remaining numbers that have yet to be sorted. It finds the smallest one in the array and places it to the end. So, once all the smallest are in one end the array is sorted. Though it is slightly better than the bubble sort, it still has the awful time complexity of O(n²).

selectionSort(array)
repeat arraysize-1 times
set the first element as minimum
for each of the elements
if element < currentMinumum
set element as new minimum
swap minimum with first position
end 

Let's take an array consisting of elements {1,8,5,3,9,4,2}. So, the code will be as follows:

The insertion sort is quite similar to the above ones and is most commonly used. Here we assume the first element is already sorted and we select an unsorted number. If the unsorted number is greater than the current unsorted number we move it to the right, else to the left. Thereby making the array sorted. So, the algorithm will iterate through the initial array, remove one element, and place it in its proper place as a part of the sorted list. Though it has the same time complexity of O(n²) it is most used than them as for the smaller arrays it's quite better than the above and there's no way we can go wrong with this.

insertionSort(array)
mark first element as sorted
for each element in array
pick key element
for j < lastindex down to 0
if current element j > key
move sorted element to right by 1
insert k here by breaking loop
end 

Let's take an array consisting of elements {2,8,5,3,9,4}. So, the code will be as follows:

So, that sums up the first three sorting algorithms. These are quite simple ones when compared to the next three. Even though its not bad to just google how to sort when required, it's better to have a clear understanding of these to know more about time complexity and arrays.