← Back to DSA Course | Chapter 9: Sorting Algorithms | Lesson 3 of 9

Insertion Sort क्या है

Insertion sort अपने हाथ में playing cards sort करने जैसा है: आप हर नया card लेते हैं और इसे पहले से sorted cards के बीच सही जगह slide करते हैं।

In this page:

  1. Basic Idea
  2. Step by Step
  3. Small Array
  4. Practice
  5. Summary
Syntax
markup 
for i in range(1, n):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key

Basic Idea

Insertion sort array के front पर एक समय में एक element एक sorted हिस्सा बनाता है, अगला unsorted element लेकर और इसे sorted हिस्से में पीछे की ओर shift करते हुए जब तक यह अपनी सही position पर न land करे — अपने हाथ में playing cards sort करने जैसा बहुत कुछ।

उदाहरण: Basic Idea

#include <iostream>
using namespace std;
int main() {
	int arr[] = {5, 1, 4, 2, 8};
	int n = 5;
	for (int i = 1; i < n; i++) {
		int key = arr[i], j = i - 1;
		while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
		arr[j + 1] = key;
	}
	for (int i = 0; i < n; i++) cout << arr[i] << " ";
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {5, 1, 4, 2, 8};
		for (int i = 1; i < arr.length; i++) {
			int key = arr[i], j = i - 1;
			while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
			arr[j + 1] = key;
		}
		System.out.println(Arrays.toString(arr));
	}
}
arr = [5, 1, 4, 2, 8]
for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key
print(arr)
#include <stdio.h>
int main() {
	int arr[] = {5, 1, 4, 2, 8};
	int n = 5;
	for (int i = 1; i < n; i++) {
		int key = arr[i], j = i - 1;
		while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
		arr[j + 1] = key;
	}
	for (int i = 0; i < n; i++) printf("%d ", arr[i]);
	return 0;
}

Step by Step

हर नए element के लिए, algorithm इसे right से left sorted elements से compare करता है, बड़े वालों को एक position दाईं ओर shift करते हुए, जब तक यह वह spot न ढूंढ ले जहां नया element belong करता है और इसे वहां insert करता है।

उदाहरण: Step by Step

#include <iostream>
using namespace std;
int main() {
	int arr[] = {5, 1, 4, 2};
	int n = 4;
	for (int i = 1; i < n; i++) {
		int key = arr[i], j = i - 1;
		cout << "Inserting " << key << " into sorted part" << endl;
		while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
		arr[j + 1] = key;
	}
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {5, 1, 4, 2};
		for (int i = 1; i < arr.length; i++) {
			int key = arr[i], j = i - 1;
			System.out.println("Inserting " + key + " into sorted part");
			while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
			arr[j + 1] = key;
		}
	}
}
arr = [5, 1, 4, 2]
for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    print("Inserting", key, "into sorted part")
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key
#include <stdio.h>
int main() {
	int arr[] = {5, 1, 4, 2};
	int n = 4;
	for (int i = 1; i < n; i++) {
		int key = arr[i], j = i - 1;
		printf("Inserting %d into sorted part\n", key);
		while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
		arr[j + 1] = key;
	}
	return 0;
}

Small Array

[3, 1, 2] जैसे एक छोटे, ज़्यादातर-sorted array पर insertion sort trace करना दिखाता है कि जब input पहले से sorted के करीब हो तो असल में कितनी कम shifts चाहिए, एक reverse-sorted array के मुकाबले जहां लगभग हर insertion पूरे sorted हिस्से को shift करती है।

उदाहरण: Small Array

#include <iostream>
using namespace std;
int main() {
	int arr[] = {5, 1, 4, 2};
	int n = 4;
	for (int i = 1; i < n; i++) {
		int key = arr[i], j = i - 1;
		while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
		arr[j + 1] = key;
		for (int k = 0; k < n; k++) cout << arr[k] << " ";
		cout << endl;
	}
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {5, 1, 4, 2};
		for (int i = 1; i < arr.length; i++) {
			int key = arr[i], j = i - 1;
			while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
			arr[j + 1] = key;
			System.out.println(java.util.Arrays.toString(arr));
		}
	}
}
arr = [5, 1, 4, 2]
for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key
    print(arr)
#include <stdio.h>
int main() {
	int arr[] = {5, 1, 4, 2};
	int n = 4;
	for (int i = 1; i < n; i++) {
		int key = arr[i], j = i - 1;
		while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
		arr[j + 1] = key;
		for (int k = 0; k < n; k++) printf("%d ", arr[k]);
		printf("\n");
	}
	return 0;
}

Practice

एक already-sorted array पर insertion sort का behavior उसी size के एक reverse-sorted से compare करने की कोशिश करें — sorted case लगभग कोई shifting नहीं करता, जो वह property है जो insertion sort को nearly-sorted data पर genuinely fast बनाती है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	int arr[] = {9, 3, 7, 1};
	int n = 4, shifts = 0;
	for (int i = 1; i < n; i++) {
		int key = arr[i], j = i - 1;
		while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; shifts++; }
		arr[j + 1] = key;
	}
	cout << "Total shifts: " << shifts;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {9, 3, 7, 1};
		int shifts = 0;
		for (int i = 1; i < arr.length; i++) {
			int key = arr[i], j = i - 1;
			while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; shifts++; }
			arr[j + 1] = key;
		}
		System.out.println("Total shifts: " + shifts);
	}
}
arr = [9, 3, 7, 1]
shifts = 0
for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
        shifts += 1
    arr[j + 1] = key
print("Total shifts:", shifts)
#include <stdio.h>
int main() {
	int arr[] = {9, 3, 7, 1};
	int n = 4, shifts = 0;
	for (int i = 1; i < n; i++) {
		int key = arr[i], j = i - 1;
		while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; shifts++; }
		arr[j + 1] = key;
	}
	printf("Total shifts: %d", shifts);
	return 0;
}

Summary

Insertion sort का worst case O(n²) है, bubble और selection sort जैसा, लेकिन already-sorted input पर इसका best case O(n) है, इसे छोटे या nearly-sorted arrays के लिए एक practical choice बनाते हुए बाकियों जैसे ही worst-case complexity class के बावजूद।

उदाहरण: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Insertion sort: O(n^2) worst case but fast and adaptive on nearly-sorted data";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Insertion sort: O(n^2) worst case but fast and adaptive on nearly-sorted data");
	}
}
print("Insertion sort: O(n^2) worst case but fast and adaptive on nearly-sorted data")
#include <stdio.h>
int main() {
	printf("Insertion sort: O(n^2) worst case but fast and adaptive on nearly-sorted data");
	return 0;
}
Related Topics

Selection Sort क्या है · Merge Sort क्या है · Bubble Sort क्या है · Quick Sort क्या है

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. Shift करने से पहले arr[i] को एक key variable में save न करना, इसलिए value overwrite होकर खो जाती है।
  2. arr[j] > key के बाद j >= 0 जांचना, जो key सबसे छोटी होने पर arr[-1] पढ़ता है।
  3. Outer loop को 1 के बजाय 0 पर शुरू करना, जब पहला element पहले से एक sorted run है।
🔒

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Selection Sort Next Lesson → Merge Sort

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.