Module 1: Introduction to Programming

Setting Up Development Environment

Module 2: Your First Program

Hello World Program
Program Structure
Problems

Module 3: Input/Output and Arithmetic Operators

Data Input/Output
Arithmetic Operators
Problems

Module 4: Conditional Statements

Comparison Operators
Conditional Operators
Problems
Problems

Module 5: Numeric data types

Numeric data types
Problems
Problems

Module 6: Loops

The for loop with range()
While loop
Nested loops
Problems
Problems
Problems
Problems

Module 7: Lists

List basics
Tuples
Multi-dimensional lists
Problems
Problems

Module 8: Strings

Characters and strings
String methods
Problems
Problems
Problems

Module 9: Functions

Functions
Functions. Advanced
Problems

Module 10: Linear search and basic brute-force

Linear Search
Brute-force
Problems
Problems

Module 11: Built-in data structures

Stack, queue, deque
Hash based data structures: set, dict, counter
Priority Queue: heapq
Problems
Problems

Module 12: Basic Sorting Algorithms

Introduction to sorting
Bubble Sort
Selection sort
Insertion sort
Problems

Module 13: Useful Python Tricks

List and Dict Comprehensions
Generators
Useful built-in functions
Standard Library Modules
Fast Input/Output
Working with files

Module 14: Recursion

Introduction to recursion
Problems

Insertion sort - Programming Language Python for Competitive Programming

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Programming Language Python for Competitive Programming/Module 12: Basic Sorting Algorithms/Insertion sort

Insertion sort

Insertion sort

The algorithm consists of $n-1$ iterations. At iterations $1 \leq i \leq n-1$ , we sort the prefix of array $a$ of length $i+1$ . That is, before iteration , the subarray is sorted, and after the -th iteration, the subarray will be sorted. To do this, it is enough to find the right place to put .

Up next

Problems

Problems for practice

i

i

a[1\ldots i]

i

a[1\ldots i+1]

a_{i+1}

Asymptotics: $O(N^2)$

for (int i = 1; i <= n - 1; i++) {
    for (int j = i + 1; j > 1; j--) {
        if (a[j - 1] > a[j]) {
            swap(a[j - 1], a[j]);
        } else {
            break;
        }
    }
}