Scribd
Upload
4 views10 pages

Selection Sort Algorithm Explained

Selection Sort is an algorithm that sorts an array by repeatedly finding the smallest element and exchanging it with the first unsorted element. It has a time complexity of O(n^2) and a space complexity of O(1), making it inefficient for large datasets but memory-efficient. The algorithm is simple to implement but requires a significant number of comparisons, leading to poor performance in larger datasets.

Uploaded by

saqibsani009
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views10 pages

Selection Sort Algorithm Explained

Selection Sort is an algorithm that sorts an array by repeatedly finding the smallest element and exchanging it with the first unsorted element. It has a time complexity of O(n^2) and a space complexity of O(1), making it inefficient for large datasets but memory-efficient. The algorithm is simple to implement but requires a significant number of comparisons, leading to poor performance in larger datasets.

Uploaded by

saqibsani009
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Selection Sort

Data Structures and Algorithm


Selection Sort – Concept

 Find the smallest element in the array


 Exchange it with the element in the first position
 Find the second smallest element and exchange it
with the element in the second position
 Continue until the array is sorted
Example
(Procedure to find MIN) – MIN(A, K, N, LOC)

 Here A is an array. This procedure will find location LOC of


the smallest element among A[K] to A[N]
1. Set MIN:=A[K] and LOC:=K
2. Repeat for J:=K+1, K+2 … N
If MIN > A[J], then set MIN:=A[J] and LOC:=J
3. [End of Loop]
4. Return
(Selection Sort) SELECTION(A, N)

1. This algorithm will sort the element of array A.


2. Repeat Step 2 and 3 for K:=1, 2, 3 .. N-1
 Call MIN(A, K, N, LOC)
 [Interchange A[K] and A[LOC]]. Set TEMP :=A[K], A[K] := A[LOC] and A[LOC]:=TEMP
3. [End of Step 1 Loop]
4. Exit
Selection Sort - Time Complexity

 Selection Sort has a time complexity of O(n^2) in the


worst, average, and best cases.
 This makes it inefficient for large datasets or
performance-critical applications.
 Selection Sort performs n-1 comparisons in the first pass,
n-2 in the second pass, and so on, resulting in n*(n-1)/2
comparisons in total.
Selection Sort - Space Complexity

 Selection Sort has a space complexity of O(1), as it sorts


the array in-place without requiring any additional
memory for temporary storage.
 This makes it memory-efficient and suitable for systems
with limited memory.
Selection Sort - Advantages and
Disadvantages
 Advantages of Selection Sort:
 Simple and easy to implement.
 In-place sorting algorithm with low space complexity.
 Disadvantages of Selection Sort:
 Quadratic time complexity, making it inefficient for large datasets.
 Requires n*(n-1)/2 comparisons in the worst case, resulting in poor performance.
//Implementation of Selection Sort }
#include <iostream> }
// Function to swap two elements return min_idx;
void swap(int& a, int& b) { }
int temp = a; // Function to perform Selection Sort
a = b; void selectionSort(int arr[], int n) {
b = temp; for (int i = 0; i < n - 1; i++) {
} int min_idx = findMinIndex(arr, i, n);
// Function to find the index of the minimum if (min_idx != i) {
value in an array swap(arr[i], arr[min_idx]);
int findMinIndex(int arr[], int start, int end) { }
int min_idx = start; }
for (int i = start + 1; i < end; i++) { }
if (arr[i] < arr[min_idx]) {
min_idx = i;
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

std::cout << "Original array: ";


for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}

selectionSort(arr, n);

std::cout << "\nSorted array: ";


for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}

return 0;
}

You might also like