Home > Learning, Lesson > Python: Sort Algorithm – 3 – Insertion Sort

## Python: Sort Algorithm – 3 – Insertion Sort

Learning : Python coding, Math, Algorithm,
Subject: Writing Merge Sorting Algorithm in Python

[NOTE: To keep the code as simple as we can, We WILL NOT ADD any user input Varevecations. Assuming that our user will Enter the right inputs.]

Sorting Algorithm is a way to sort a given list/Array of numbers, there are several sorting Algorithm as follow:
Type of Sorting Algorithm

Here in this post we will write a function to take a given list and sort it then pass it back. We assume the user will enter a serial of numbers, that he want to sort, our function will sort it and print out the original numbers and the sorted one.

Insertion Sort: Steps of Insertion Sorting Algorithm are:

1. Start with index (x = 1), Compare the Element (k) in index [x] with the Element in index [x-1].
1.1 If Element in [x-1] SMALLER than Element in [x] we swap the two elements.
1.2 Once we Swap we will have new index for k , and again we will compare the (k) in (new index) with element before it (new index -1), and keep moving it to left until we stop at index  or we face an Element GRATER than k.

2. If the Element k GRATER than the element before it, we left k and take the Next Element (to be k) and start comparing K [in x index] with Element in [x-1] index.

3. We do this until k will be in index (length on the list)

Now starting with the codes, as our standard we follow in Sorting Algorithm Applications we will have a Main-Menu and three Items the user will chose among them, and Function to let the user to enter the Numbers [The List or the Array] to be sorted. The Options in the Main-Menu are :
1. Insertion Sort Algorithm – Fast Run.
2. Insertion Sort Algorithm – Step By Step.
9. Exit.

The Fasr-Run we call the create_list(): Function first so the user will Enter the Numbers in the Array, then the Fast-Run will show the sorted Array on the screen.
In the Step-By-Step (Option 2 in the Menu) again calling create_list(): Function first, after the user Enters the Array, we will print-out on the screen each steps of selecting the index, and index-1, the k values and when/if we will SWAP or not.
The last option in the Menu is to Exit the Application (option 9).

Now we start coding.. Here is the Main-Menu.

``` # Main-Menu

os.system('clear')
print('\n\n',' '*5,'******************************')
print(' '*5,' ***','  Sorting Algorithm ',' '*1,'***')
print(' '*5,' ***','     Insertion Sort     ',' '*1,'***')
print(' '*5,' ***',' '*22,'***')
print(' '*5,' ******************************\n\n')
print(' '*7,'1. Insertion Sort Algorithm - Fast Run.')
print(' '*7,'2. Insertion Sort Algorithm - Step By Step.')
print(' '*7,'9. Exit.')

user_choice = input('\n   Select your choice.  > ')
return user_choice ```

Here is the codes for create_list(): to collect the Array from the user..

Finaly, here is the code for the Step-by-Step running for the Insetion Sort Algorithm. It is the same copy of the Fast-Run but with some print statements to show what is happening.

We Done another coding for Sorting Algorithms, another one will be published in coming days..

… Have fun with Coding … 🙂 Follow me on Twitter..