Sorting

# Sorting with Insertion Sort

Basic idea behind insertionsort is to take an item from the input list and insert it into the proper position in a sorted output list (which initially starts empty).

The algorithm

starts by building an empty list to hold the sorted output.
Then loops through the unsorted list of input nodes.
For each input nodes, looks through the growing sorted list and finds the node after which the new value belongs.
It then inserts the node there.

Since we end up comparing with all in worst case the time complexity is $O(n^2)$

# Sorting with Selection Sort

Basic idea behind the selectionsort algorithm is to search the input list for the largest item it contains and then add it to the front of a growing sorted list.

For an input list contains $n$ items, finding the largest item in the list takes $n$ steps but adding the largest item to the sorted list takes only a few steps.

The input lenght also shrinks but still the time complexity is $O(n^2)$

# Sorting with Insertion Sort

Basic idea behind insertionsort is to take an item from the input list and insert it into the proper position in a sorted output list (which initially starts empty).

The algorithm

starts by building an empty list to hold the sorted output.

Then loops through the unsorted list of input nodes.

For each input nodes, looks through the growing sorted list and finds the node after which the new value belongs.

It then inserts the node there.

Since we end up comparing with all in worst case the time complexity is

O(n^2)

# Sorting with Selection Sort

Basic idea behind the selectionsort algorithm is to search the input list for the largest item it contains and then add it to the front of a growing sorted list.

For an input list contains

n

items, finding the largest item in the list takes

n

steps but adding the largest item to the sorted list takes only a few steps.

The input lenght also shrinks but still the time complexity is

O(n^2)