🐍
My Docs
PYTHONNOTES
PYTHONNOTES
  • Home
  • Downloads & Misc-Assets
  • README
  • Navigation
  • Curriculum
    • Outline
      • General Content
      • Python-Data-Structures-Unit
    • wk17
      • Outline-w17
      • homework
      • D1-Module 01 - Python I
        • Configuring Ubuntu for Python Web Development
        • Install Python
      • D2- Module 02 - Python II
      • D3- Module 03 - Python III
      • D4-Module 04 - Python IV
    • wk18
      • Outline-W-18
      • D1- Module 01 - Number Bases and Character Encoding
      • D2- Module 02 - Hash Tables I
        • Hash Table / Hash Map In Python:
        • Hash Table Use Cases
        • Practice
      • D3-Module 03 - Hash Tables II
      • D4- Module 04 - Searching and Recursion
    • wk19
      • Outline-W-19
      • D1- Module 01 - Linked Lists
        • Homework
          • Helpful Resource
      • D2- Module 02 - Queues and Stacks
      • D3- Module 03 - Binary Search Trees
        • BST Definition:
      • D4- Module 04 - Tree Traversal
        • Tree Traversals (Inorder, Preorder and Postorder)
    • wk20
      • Outline-W-20
      • D1-Graphs I
      • D2-Graphs 2
      • DFS
      • D4
  • Utilities
    • Utilites
      • Python Libraries
      • YouTube
      • Code Lab Notebook Embeds From Lecture
    • Code lab Notebooks
    • Repl.IT
      • Trinket
  • Abstract Data Structures
    • Algorithms
      • Algo-Resources
        • List-Of-Solutions-To-Common-Interview-Questions
      • Dijkstra's algorithm
      • Calculate a Factorial With Python - Iterative and Recursive
      • DFS
      • BFS
        • BFS Examples
      • Palendrome
    • Data Structures Overview
      • General Data Structures Notes
        • DS-Explained-Simple
      • Untitled
      • Algorithms
      • Dictionary
    • Abstract Data Structures:
      • Array
        • Extra-Array
        • Array Practice
      • Binary Search
      • Binary Tree
        • Binary Tree Explained
        • Find the maximum path sum between two leaves of a binary tree
      • Binary Search Tree
        • BST Explained
        • BST Insert
        • BST-Largest-Sub-Tree
      • Exotic
        • Tire
        • Dynamic Programming
      • Graphs
        • Overflow Practice Problems
        • Graphs Explained
        • Earliest Ancestor
        • _Mini Graph-Projects
          • # Social Graph
          • number of 1 islands
          • Searching and Generating Graphs
        • Graph FAQ
          • Graph DFS
        • Connected Components
        • Randomness
        • Graph BFS
        • Topological Sort
      • Hash Table
        • Hashmap or Hash tables
        • Hash Table and HashMap in Python
      • Heap
        • Heap Examples
      • String
      • Map
        • Examples
      • Queue
        • Queue Continued...
        • Queue Sandbox
        • Dequeue
      • Tree
        • In Order Traversal
        • Tree Equal ?
        • Ternary-search-trees
        • Red_Black Tree
        • Tree Mirror:
        • Tree Traversal
      • Recursion
        • Recursion Explained
          • Recursion Examples
      • Linked List
        • Linked List Background
        • Double Linked List
        • List Example
        • Examples (LL) continued
        • List Operations
      • Set
        • Set
        • Set Intersection Union
        • Disjoint Set
      • Sorting
        • In JavaScript
        • Merge Sort
        • Iterative Sorting
        • Recursive Sorting
        • Graph Topological Sort
        • SelectionSort
        • Quick Sort
        • Merge Sort
        • Insertion Sort
      • Stack
        • Stack Continued
        • Stack Part 3
      • Searching
        • Binary Search
        • Searching & Sorting Computational Complexity (JS)
  • practice
    • GCA Sprint Prep:
      • Practice Problems
      • Code Signal CGA Sprint Resources
      • CGA-Sprint Prep
    • Supplemental Practice:
      • Practice
      • JavaScript Algorithms
      • Industry Standard Algorithms
        • Interview Practice Resources
        • Write a Program to Find the Maximum Depth or Height of a Tree
      • Random Examples
      • Prompts
      • JS_BASICS
  • Resources
    • Python Cheat Sheet
      • Cheatsheet-v2
      • List Of Python Cheat Sheets
    • Youtube
    • PDF Downloads
    • Intro 2 Python
    • Dictionaries
      • Dictionaries Continued
    • Python VS JavaScript
    • Misc. Resources
    • Things To Internalize:
      • Functions
    • Intro To Python w Jupyter Notebooks
    • Calculating Big O
    • Useful Links
      • Awesome Python
      • My-Links
      • Beginners Guide To Python
  • Docs
    • Docs
      • Strings
        • Strings Continued
      • Touple
      • Values Expressions & Statments
      • Dictionaries, sets, files, and modules
        • Modules
      • Built-in Types
      • Built In Functions
        • Zip Function
      • Functions
      • Classes and objects
        • Inheritance
        • Classes
          • Python Objects & Classes
          • index
      • Dictionaries
      • Conditionals and loops
      • Lists
        • Reverse A List
        • Python Data Structures
        • More On Lists
        • Examples
          • More-Examples
        • List Compehensions
      • Basic Syntax
      • String-Methods
    • Queue & Stacks
  • quick-reference
    • My Medium Articles
    • Free Python Books
    • WHY Python?
    • Debugging
    • Python Snippets
    • Python3 Regex
    • Python Module Index:
      • Requests Module
    • Creating Python Modules
    • Useful Info
    • Python Glossary
    • Python Snippets
  • MISC
    • Built-in Methods & Functions
    • Data Structures Types
    • Math
    • Unsorted Examples
    • Outline
    • About Python
      • Python VS JavaScript
      • Python Modules & Python Packages
      • Misc
      • Python's Default Argument Values and Lists
      • SCRAP
  • Interview Prep
    • Interview Resources
      • By Example
        • Algo-Prep
      • Permutation
      • How to Write an Effective Resume of Python Developer
      • Interview Checklist
      • 150 Practice Problems & Solutions
  • Installations Setup & Env
    • python-setup
    • Installing Python Modules
    • Set Up Virtual Enviornment
  • Aux-Exploration
    • Related Studies
      • Self-Organizing Maps: Theory and Implementation in Python with NumPy
      • List Directory Contents
      • Employee Manager
      • OS Module
      • server-side-scripting
      • Web Scraping
      • Reading and Writing to text files in Python
      • General Data Structures
      • Touple
      • How to round Python values to whole numbers?
      • Python Array Module
      • Data Structures In JavaScript
      • Dunder Methods
      • Python GitHub API
      • JS-Event Loop
      • JavaScript Event Loop
      • Manipulating Files & Folders
  • experiments
    • Untitled
Powered by GitBook
On this page
  1. Abstract Data Structures
  2. Abstract Data Structures:
  3. Sorting

Insertion Sort

PreviousMerge SortNextStack

Last updated 3 years ago

What is Insertion Sort?

Insertion sort is good for collections that are very small or nearly sorted. Otherwise, it’s not a good sorting algorithm it moves data around too much.

Each time insertion is made, all elements in a greater position are shifted.

It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

of Insertion Sort

  1. Simple implementation.

  2. Much More Efficient for small data sets, much like other quadratic sorting algorithms like and .

  3. Adaptive that is efficient for the type of data sets that are already substantially sorted.

  4. Stable Sorting Algorithm

  5. In-place sorting means O(1) space required.

Define Insertion Sort Function

Now, let’s define a new function named insertion-sort which accepts one parameter which is list we pass as n argument to this function.

So what we are going to do is to use two for loops, one starting from index 1 and another loop inside the first loop from the previous element of the list up to index 0.

Then we compare the outer loop index value with the inner loop index value for each iteration and then swap the small one with the outer index element.

def insertionSort(List):
    for i in range(1, len(List)):
        currentNumber = List[i]
        for j in range(i - 1, -1, -1):
            if List[j] > currentNumber :
                List[j], List[j + 1] = List[j + 1], List[j]
            else:
                List[j + 1] = currentNumber
                break

    return List

Complexity

Insertion sort has a worst-case and average complexity of О(n2), where n is the number of items being sorted.

Most practical sorting algorithms have substantially better worst-case or average complexity, often O(n log n).

When the list is already sorted (best-case), the complexity of the insertion is only O(n).

Best O(n); Average O(n^2); Worst O(n^2)

Define Main Condition

Now, let’s create a main condition where we need to call the above function and pass the list which needs to be sorted.

So let’s manually defined the list which we want to pass as an argument to the function.

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List : ',insertionSort(List))

Source Code

def insertionSort(List):
    for i in range(1, len(List)):
        currentNumber = List[i]
        for j in range(i - 1, -1, -1):
            if List[j] > currentNumber :
                List[j], List[j + 1] = List[j + 1], List[j]
            else:
                List[j + 1] = currentNumber
                break

    return List

if __name__ == '__main__':
    List = [3, 4, 2, 6, 5, 7, 1, 9]
    print('Sorted List : ',insertionSort(List))

Output

Insertion Sort implementation example in Python Output
Advantages
bubble sort
selection sort