Talk about Algorithms and sorting comes to mind at first as it is
the king of algorithms. Not only because there are many sorting algorithms but
sorting is the fundamental operation in computing. Sorting means arranging
items in some specific order and we see these all the times when working on our
files or folder and working in database when we need records in some certain
fashion. Sorting also find its use in searching and other algorithms.
There are many sorting algorithms and we will describe each
algorithm and its implementation one post at a time.
Insertion sort
Insertion Sort is
one of the simplest sorting algorithm. It is same as we sort cards in our
hand. We look at cards from left to right pick the unsorted card and insert it
at correct position.
For explaining the insertion sort algorithm we have taken the
below unsorted list having 5 elements.
5

1

3

2

4

On first Iteration Second element will be compared with the first
element it is smaller than first element they are swapped resulting in below
list
1

5

3

2

4

On second iteration 3rd element will be checked against 1st and
2nd element and below list is formed.
1

3

5

2

4

And so on till
the last element...
1

2

3

5

4

Final sorted
list
1

2

3

4

5

Implementation
__author__ = 'Dharmjit' def InsertionSort(list): for index in range(1,len(list)): curr = list[index] position = index while position > 0 and list[position1] > curr: list[position] = list[position1] position = position  1 list[position] = curr return list l = [2,1,5,3,9,6,7] print(InsertionSort(l)) [1,2,3,5,6,7,9]
Time complexity
Best Case Scenario: If the list is already sorted the insertion algorithm runs in O(n) time which is linear
Worst Case Scenario: When the List is sorted in reverse order, it will take o(n^2) time which is quadratic.
Best Case Scenario: If the list is already sorted the insertion algorithm runs in O(n) time which is linear
Worst Case Scenario: When the List is sorted in reverse order, it will take o(n^2) time which is quadratic.
No comments :
Post a Comment