DEV Community

Cover image for Implement Insertion sort easily in your program
Parth • imParth
Parth • imParth

Posted on

Implement Insertion sort easily in your program

Insertion Sort is a comparison-based sorting algorithm that works by iteratively building a sorted portion of the array or list, one element at a time. It starts with the assumption that the first element is already sorted. Then, it considers the next element and inserts it into the correct position in the sorted portion, shifting other elements as necessary. This process is repeated until the entire array is sorted.

How Insertion Sort Works

Insertion Sort works by iteratively building a sorted portion of the array or list, one element at a time. It starts with the assumption that the first element is already sorted. Then, it considers the next element and inserts it into the correct position in the sorted portion, shifting other elements as necessary. This process is repeated until the entire array is sorted.

Here are the step-by-step operations of Insertion Sort on this array:

Step 1: Start with the second element (2) and compare it with the element in the sorted portion (5). Since 2 is smaller, we shift 5 to the right and insert 2 at the first position: [2, 5, 8, 12, 1].

Step 2: Move to the third element (8) and compare it with the elements in the sorted portion (2, 5). Since 8 is larger, we leave it at its position: [2, 5, 8, 12, 1].

Step 3: Repeat step 2 for the fourth element (12). Since 12 is larger than all the elements in the sorted portion, it remains in its position: [2, 5, 8, 12, 1].

Step 4: Finally, consider the fifth element (1) and compare it with the elements in the sorted portion (2, 5, 8, 12). Since 1 is smaller, we shift all the larger elements to the right and insert 1 at the first position: [1, 2, 5, 8, 12].

After these steps, the array is sorted in ascending order.

Insertion sort

Implementation Steps

Step 1: Prompt the user to enter the size of the array by using the input() function and convert it to an integer using the int() function. Store the value in a variable named n.

Step 2: Create an empty list called arr to store the elements of the array.

Step 3: Use a for loop to iterate n times. Inside the loop, prompt the user to enter each element of the array using the input() function, convert it to an integer, and append it to the arr list.

Step 4: Use a for loop to iterate over the range from 1 to n.

Step 5: Inside the loop, store the current element in a variable named current.

Step 6: Create a variable named j and set it equal to i - 1.

Step 7: Use a while loop to compare the element at index j with the current element. If the element at index j is greater than the current element and j is greater than or equal to 0, shift the element at index j to the right by assigning the value of arr[j] to arr[j + 1]. Decrement j by 1.

Step 8: After the while loop completes, insert the current element at the correct position by assigning its value to arr[j + 1].

Step 9: After the outer for loop completes, use another for loop to iterate over the arr list and print each element, separated by a space, using the print() function with the end parameter set to " ".

Code

n=int(input("Enter size of array: "))
arr = []

for i in range(n):
    arr.append(int(input()))

print('Unsorted Array: ')
for i in arr:
    print(i, end=" ")

for i in range(1, n):
    current = arr[i]
    j = i-1
    while(arr[j]>current and j>=0):
        arr[j+1] = arr[j]
        j-=1
    arr[j+1] = current

print('Sorted Array: ')
for i in arr:
    print(i, end=" ")
Enter fullscreen mode Exit fullscreen mode

Example

Enter the size of the array: 5
8
5
6
2
7
Unsorted Array: 8 5 6 2 7
Sorted Array: 2 5 6 7 8
Enter fullscreen mode Exit fullscreen mode

Time Complexity

The time complexity of Insertion Sort is O(n^2) in the worst case and average case. In the best case scenario, when the array is already sorted, the time complexity is O(n).

Conclusion

Insertion Sort is a simple yet efficient sorting algorithm that is particularly useful for small datasets or partially sorted arrays. Its simplicity, in-place sorting capability, and average-case time complexity of O(n) make it a valuable tool for programmers. However, it may not be the best choice for large datasets or arrays that are already mostly sorted.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay