Scribd
Upload
6 views1 page

Selection Sort: Space Complexity Explained

Selection Sort is a sorting algorithm that iteratively selects the smallest element from an unsorted list and moves it to the front. The process is repeated for the next smallest elements until the entire list is sorted. The algorithm has a time complexity of O(n²) and a space complexity of O(1).

Uploaded by

Rahamatulla Firdous
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
6 views1 page

Selection Sort: Space Complexity Explained

Selection Sort is a sorting algorithm that iteratively selects the smallest element from an unsorted list and moves it to the front. The process is repeated for the next smallest elements until the entire list is sorted. The algorithm has a time complexity of O(n²) and a space complexity of O(1).

Uploaded by

Rahamatulla Firdous
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

✨ What is Selection Sort?

Selection Sort is a sorting algorithm that works like this:


"Find the smallest number in the list, and move it to the front. Then find the next smallest, and move it to
the second position, and so on."
It's like arranging books from shortest to tallest, one by one.
Step-by-Step Example
Let’s say we have this array:
[30, 10, 50, 20]
Pass 1:
• Find the smallest from [30, 10, 50, 20] → it's 10
• Swap 10 with 30 → [10, 30, 50, 20]
Pass 2:
• Find the smallest from [30, 50, 20] → 20
• Swap 20 with 30 → [10, 20, 50, 30]
Pass 3:
• Find the smallest from [50, 30] → 30
• Swap 30 with 50 → [10, 20, 30, 50] ✅ Done! Now the array is sorted.

Time and Space Complexity


• Time Complexity: O(n²)
• Space Complexity: O(1) → no extra memory used
Simple Selection Sort in C
#include <stdio.h>
int main() {
int arr[5] = {30, 10, 50, 20, 40};
int n = 5;
int i, j, minIndex, temp;
// Selection Sort
for (i = 0; i < n - 1; i++) {
minIndex = i;

// Find the index of the minimum element


for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
} if (minIndex != i) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
printf("Sorted array: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

You might also like