Insertion Sort Algorithm | Python Programming

Introduction

Insertion sort is a simple sorting algorithm that works by repeatedly inserting the next element in the sorted array. It is an in-place comparison-based sorting algorithm that builds the final sorted array one item at a time.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/sorting_searching("`Sorting Searching`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills algorithm/sorting_searching -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} python/conditional_statements -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} python/for_loops -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} python/lists -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} python/tuples -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} python/function_definition -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} python/classes_objects -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} python/encapsulation -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} python/raising_exceptions -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} python/build_in_functions -.-> lab-268874{{"`Efficient Insertion Sort Algorithm`"}} end

Insertion Sort

Problem

The problem is to implement insertion sort in Python. Given an unsorted list of elements, the algorithm should sort the list in ascending order. The algorithm works by iterating over the list and inserting each element in its correct position in the sorted part of the list.

The algorithm starts by assuming that the first element in the list is already sorted. It then iterates over the remaining elements in the list, comparing each element to the elements in the sorted part of the list. If the element is smaller than the current element in the sorted part of the list, it is inserted before that element. If the element is larger than all the elements in the sorted part of the list, it is inserted at the end of the sorted part of the list.

Requirements

To implement insertion sort in Python, the following requirements should be met:

A naive solution is sufficient.
Duplicates are allowed.
The input is not necessarily valid, so the algorithm should handle invalid input gracefully.
The algorithm should fit in memory.

Example Usage

The following are some examples of how to use the insertion sort algorithm:

None -> Exception: If the input is None, an exception should be raised.
Empty input -> []: If the input is an empty list, the output should also be an empty list.
One element -> [element]: If the input is a list with only one element, the output should be the same list.
Two or more elements: If the input is a list with two or more elements, the output should be a sorted list in ascending order.

Summary

Insertion sort is a simple and efficient sorting algorithm that works well for small lists or partially sorted lists. It has a time complexity of O(n^2) in the worst case, but it can be faster than other sorting algorithms for small lists or partially sorted lists. The algorithm works by repeatedly inserting the next element in the sorted array, building the final sorted array one item at a time. The implementation of insertion sort in Python should meet the requirements mentioned above and handle invalid input gracefully.

Efficient Insertion Sort Algorithm