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

Selection Sort क्या है

Selection sort एक crowd में से shortest kid चुनने जैसा है, फिर अगला shortest, और उन्हें एक-एक करके front में line up करना।

In this page:

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

Basic Idea

Selection sort array को front पर एक sorted हिस्से और back पर एक unsorted हिस्से में divide करता है, और हर pass पर यह unsorted हिस्से में बची सबसे छोटी value ढूंढता है और इसे sorted हिस्से की अगली position में swap करता है।

उदाहरण: Basic Idea

#include <iostream>
using namespace std;
int main() {
	int arr[] = {29, 10, 14, 37};
	int n = 4;
	for (int i = 0; i < n - 1; i++) {
		int minIdx = i;
		for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
		swap(arr[i], arr[minIdx]);
	}
	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 = {29, 10, 14, 37};
		int n = arr.length;
		for (int i = 0; i < n - 1; i++) {
			int minIdx = i;
			for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
			int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
		}
		System.out.println(Arrays.toString(arr));
	}
}
arr = [29, 10, 14, 37]
n = len(arr)
for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
        if arr[j] < arr[min_idx]:
            min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(arr)
#include <stdio.h>
int main() {
	int arr[] = {29, 10, 14, 37};
	int n = 4;
	for (int i = 0; i < n - 1; i++) {
		int minIdx = i;
		for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
		int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
	}
	for (int i = 0; i < n; i++) printf("%d ", arr[i]);
	return 0;
}

Step by Step

हर pass पूरे unsorted हिस्से को इसकी minimum value ढूंढने के लिए scan करता है, फिर बिल्कुल एक swap करता है उस minimum को sorted और unsorted के बीच boundary पर रखने के लिए। इसका मतलब है selection sort हमेशा कुल ज़्यादा से ज़्यादा n-1 swaps करता है, उन algorithms के विपरीत जो हर comparison पर swap करते हैं।

उदाहरण: Step by Step

#include <iostream>
using namespace std;
int main() {
	int arr[] = {29, 10, 14, 37};
	int n = 4;
	for (int i = 0; i < n - 1; i++) {
		int minIdx = i;
		for (int j = i + 1; j < n; j++) {
			cout << "Scanning " << arr[j] << endl;
			if (arr[j] < arr[minIdx]) minIdx = j;
		}
		swap(arr[i], arr[minIdx]);
		cout << "Placed " << arr[i] << " at position " << i << endl;
	}
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {29, 10, 14, 37};
		int n = arr.length;
		for (int i = 0; i < n - 1; i++) {
			int minIdx = i;
			for (int j = i + 1; j < n; j++) {
				System.out.println("Scanning " + arr[j]);
				if (arr[j] < arr[minIdx]) minIdx = j;
			}
			int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
			System.out.println("Placed " + arr[i] + " at position " + i);
		}
	}
}
arr = [29, 10, 14, 37]
n = len(arr)
for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
        print("Scanning", arr[j])
        if arr[j] < arr[min_idx]:
            min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
    print("Placed", arr[i], "at position", i)
#include <stdio.h>
int main() {
	int arr[] = {29, 10, 14, 37};
	int n = 4;
	for (int i = 0; i < n - 1; i++) {
		int minIdx = i;
		for (int j = i + 1; j < n; j++) {
			printf("Scanning %d\n", arr[j]);
			if (arr[j] < arr[minIdx]) minIdx = j;
		}
		int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
		printf("Placed %d at position %d\n", arr[i], i);
	}
	return 0;
}

Small Array

[29, 10, 14, 37] जैसे एक array पर selection sort trace करना per pass एक element बढ़ती sorted boundary दिखाता है, हर pass के single swap के साथ सही next-smallest value रखते हुए।

उदाहरण: Small Array

#include <iostream>
using namespace std;
int main() {
	int arr[] = {29, 10, 14, 37};
	int n = 4;
	for (int i = 0; i < n - 1; i++) {
		int minIdx = i;
		for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
		swap(arr[i], arr[minIdx]);
		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 = {29, 10, 14, 37};
		int n = arr.length;
		for (int i = 0; i < n - 1; i++) {
			int minIdx = i;
			for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
			int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
			System.out.println(java.util.Arrays.toString(arr));
		}
	}
}
arr = [29, 10, 14, 37]
n = len(arr)
for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
        if arr[j] < arr[min_idx]:
            min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
    print(arr)
#include <stdio.h>
int main() {
	int arr[] = {29, 10, 14, 37};
	int n = 4;
	for (int i = 0; i < n - 1; i++) {
		int minIdx = i;
		for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
		int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
		for (int k = 0; k < n; k++) printf("%d ", arr[k]);
		printf("\n");
	}
	return 0;
}

Practice

चूंकि selection sort का swap count इतना कम है, इसे उसी input पर bubble sort से compare करना worth है यह देखने के लिए कि कम swaps का ज़रूरी नहीं मतलब कम comparisons है — दोनों अब भी element pairs की roughly वही total संख्या scan करते हैं।

उदाहरण: Practice

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

Summary

Selection sort input के initial order की परवाह किए बिना O(n²) time में चलता है, क्योंकि यह हमेशा हर pass पर पूरा unsorted हिस्सा scan करता है भले ही array पहले से sorted हो — एक property जो इसे bubble sort के early-exit behavior से अलग करता है।

उदाहरण: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Selection sort: O(n^2) always, but far fewer swaps than bubble sort";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Selection sort: O(n^2) always, but far fewer swaps than bubble sort");
	}
}
print("Selection sort: O(n^2) always, but far fewer swaps than bubble sort")
#include <stdio.h>
int main() {
	printf("Selection sort: O(n^2) always, but far fewer swaps than bubble sort");
	return 0;
}
Related Topics

Activity Selection समस्या · Bubble Sort क्या है · Insertion Sort क्या है · Merge 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. Inner loop के अंदर हर बार एक छोटा item दिखने पर swap करना बजाय minimum ढूंढने के बाद एक बार, जो इसे एक अलग, धीमी sort में बदल देता है।
  2. Minimum की index के बजाय इसकी value store करना, इसलिए swap करने के लिए कुछ नहीं बचता।
  3. Inner loop i के बजाय i + 1 पर शुरू करना, या outer वाले को n - 1 के बजाय n तक loop करना।
🔒

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Bubble Sort Next Lesson → Insertion 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.