MLEnglish

Sorting Algorithms

For all examples, assume a dummy array, like x = [-5,-3,2,1,-3,-3,7,2,2] This could be any array, but this is simply an example to work with. We are sorting this array in ASCENDING order.

Insertion Sort

The idea behind this sort is that you have a sorted part of the array, and a unsorted part. You take elements from the unsorted part and put them in their respective spots in the sorted part of the array.

Example:

A way to think about this algorithm is having a deck of 10 cards
You want them in ascending order, so you run insertion sort
Well, first you seperate your cards into two hands, one "sorted", and one "unsorted"
You take one card from the unsorted pile, and add it to the sorted pile, and swap anything accordingly
You do so for all the cards, until all the cards are sorted!
To summarize, take one element, slide it left until it lands where it belongs

Algorithm:

Loop through the array for every element past the first one(always assume first one is sorted), via index i
Check for every element behind the sorted index(i), loop through backwards until it's in order, via index j
When done, break and continue to next number, and repeat above steps
Array is sorted via insertion sort!

Complexity:

Time Complexity: O(n²), which means it takes a long time(bad)
Space Complexity: O(1) - takes basically no memory(good)
This is known as an in-place sort because you're not creating a new array

Python code for insertion sort:

x = [-5,-3,2,1,-3,-3,7,2,2, -9] # dummy array 


for i in range(1,len(x)): # for every element that's UNSORTED(always assume first one is)
    for j in range(i,0,-1): # go backwards from the current index to the start of the array
            if(x[j]<x[j-1]): # if the current index is smaller than the one before
                x[j],x[j-1] = x[j-1],x[j] # switch
            else:
                break # go to next element
            
print(x)

Insertion Sort in Python

Sorting Algorithms

Insertion Sort