Module 1: Introduction to Programming

What is Programming?
Why Do We Need Programming?
Setting Up Development Environment

Module 2: Your First Program

Hello World Program
Program Structure
Introductory 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: Data Types

Data Types
Problems
Problems
Problems
Problems

Module 6: Loops

The For Loop
Loop Patterns
Problems
Problems
Problems
Problems

Module 7: Arrays

Array Definition
Multi-dimensional arrays
Problems
Problems

Module 8: Functions

Functions
Problems for practice

Module 9: Nested loops and Multi-dimensional array

Nested Loops and Multi-Dimensional Arrays
Problems for practice

Module 10: Linear Search

Linear Search
Problems

Module 11: STL Data Structures 1

STL Data Structures
Problems for practice

Module 12: Basic Sorting Algorithms

Introduction to sorting
Bubble Sort
Selection Sort
Insertion Sort
Problems for practice

Module 13: STL Data Structures 2

STL Data Structures: set and map
Problems for practice

Module 14: Brute-forces

Introduction to bruteforce
Problems for practice

Module 15: Recursion

Introduction to Recursion
Problems for practice

Module 16: Structs in C++

Structs

Insertion Sort - Introduction to Programming - C++

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Introduction to Programming - C++/Module 12: Basic Sorting Algorithms/Insertion Sort

Insertion Sort

Insertion sort algorithm.

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 for practice

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;
        }
    }
}