Posts Tagged ‘insertion sort’

Python: Sort Algorithm – 3 – Insertion Sort

June 8, 2021 2 comments

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
1. Quick Sort. [Click Here]
2. Bubble Sort. [Click Here]
3. Merge Sort. [Click Here]
4. Insertion Sort. [Click Here]
5. Selection Sort. [Click Here]
6. Heap Sort. [Click Here]
7. Radix Sort. [Click Here]
8. Bucket Sort. [Click Here]

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 [0] 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

def main_menu ():
    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..

ali radwani python code project sorting algorithm insertion sort
ali radwani python code project sorting algorithm insertion sort

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.

ali radwani python code project sorting algorithm insertion sort

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

… Have fun with Coding … 🙂

To Download my Python code (.py) files Click-Here

ali radwani python projects codeFollow me on Twitter..

By: Ali Radwani