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)$