What are Sorting algorithms?
Sorting algorithms are ways to organize an array of items from smallest to largest.
Why we need it?
A lot of what we ask computers to do involves placing items in the correct order. Also, Certain problems become easier when our collection is sorted.
How we do it?
Through sorting algorism! There is a wide variety of sorting algorithms, Straight Insertion, Shell Sort, Bubble Sort, Quick Sort, Selection Sort, and Heap Sort…Let’s exam some of them one by one.
Insertion Sort
I remember when I was young, I used to play poker with my cousin. When I got a hand of cards. I would start by sorting all the cards in order from smallest to biggest.
Think about how I did it? I find the smallest card of the hand, remove it and place it in a new pile, and then find the smallest card of the remaining cards, remove it and place it on top of the new pile. Repeat this procedure until there is no more card left in my hand. This is basically the idea of insertion Sort.
How we can transfer this procedure into code?
Let think about it in a program way. What do we want? We want to write a function for a given array, find the minimum of the array and remove elements until there are no more elements left in the original array.
We first set array[0] as current smallest, then we compare array[1] with array[0], set current smallest to tAhe smaller one of the two, and move on to the next element until the last one of the array. After loop through the whole array, the current smallest should be the smallest of the array.
Now we have this helper method. What do we want to do next? We want to call this function on the array, find and remove the smallest, push it to a new array until there is no more element left in the array.
What is the big O of insertion sort?
Let’s think about the procedure. It’s a nested loop. In selectionSort function, we call findMinandRemove n times, inside each findMinandRemove function, we go through each element and remove it, So the cost of minAndRemove is n. So the cost of selection sort is n squared.