Index
Selection Sort
Selection Sort is a simple sorting algorithm that divides the input array into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, and the unsorted part contains all the elements of the array. The algorithm repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the beginning (or end) of the sorted part. This process continues until the entire array is sorted.
Here’s how the Selection Sort algorithm works:
Algorithm:
- Divide the input array into two parts: the sorted part and the unsorted part.
- Find the smallest element in the unsorted part.
- Swap the smallest element with the first element of the unsorted part, effectively adding it to the sorted part.
- Repeat steps 2 and 3 for the remaining unsorted part of the array until the entire array is sorted.
#include <stdio.h>
// Function to perform Selection Sort
void selectionSort(int arr[], int n) {
int i, j, min_index;
// Traverse through all array elements
for (i = 0; i < n - 1; i++) {
// Find the minimum element in the unsorted part
min_index = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Output:
Original array:
64 25 12 22 11
Sorted array:
11 12 22 25 64
Code Explanation
1. selectionSort
Function
void selectionSort(int arr[], int n) {
int i, j, min_index;
// Traverse through all array elements
for (i = 0; i < n - 1; i++) {
// Find the minimum element in the unsorted part
min_index = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
- Purpose: Sorts the array in ascending order using the Selection Sort algorithm.
- How it works:
- The outer loop (
i
) iterates through the array from the first element to the second-to-last element. - For each iteration of the outer loop:
- The inner loop (
j
) finds the index of the smallest element in the unsorted part of the array (fromi+1
ton-1
). - The
min_index
variable keeps track of the index of the smallest element found.
- The inner loop (
- After finding the smallest element, it swaps it with the element at the current position (
i
). - This process continues until the entire array is sorted.
- The outer loop (
2. printArray
Function
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
- Purpose: Prints the elements of the array.
- How it works:
- Iterates through the array and prints each element followed by a space.
- After printing all elements, it adds a newline (
\n
) for better readability.
3. main
Function
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
- Purpose: Drives the program.
- How it works:
- Declares and initializes an array
arr
with unsorted integers. - Calculates the size of the array (
n
) usingsizeof(arr) / sizeof(arr[0])
. - Prints the original array using the
printArray
function. - Calls the
selectionSort
function to sort the array. - Prints the sorted array using the
printArray
function.
- Declares and initializes an array
Key Points
- Selection Sort:
- Time Complexity: O(n²) in all cases (worst, average, and best).
- Space Complexity: O(1) (in-place sorting).
- It is a simple but inefficient sorting algorithm for large datasets.
- How Selection Sort Works:
- Divides the array into a sorted and an unsorted part.
- Repeatedly selects the smallest element from the unsorted part and swaps it with the first element of the unsorted part.
- The sorted part grows from left to right.
- Swapping:
- A temporary variable (
temp
) is used to swap two elements.
- A temporary variable (
