selection sort Algorithm
Selection sort is a simple comparison-based sorting algorithm that is easy to understand and implement. The key idea behind the algorithm is to divide the input list into two parts – a sorted part and an unsorted part. Initially, the sorted part is empty, and the unsorted part contains all the elements. The algorithm repeatedly selects the smallest or largest (depending on the desired order) element from the unsorted part and moves it to the end of the sorted part. This process continues until the unsorted part becomes empty, and the sorted part contains all the elements in the desired order.
In each iteration of the selection sort algorithm, it searches for the minimum or maximum element in the unsorted part of the list and swaps it with the first unsorted element. The time complexity of the selection sort algorithm is O(n^2) for the best, worst, and average cases, making it inefficient for large datasets. However, it performs well for small datasets or lists that are already partially sorted. One of the advantages of the selection sort algorithm is that it performs the minimum number of swaps, making it useful in situations where the cost of swapping elements is high. Despite its simplicity, selection sort is generally not used in practice because other sorting algorithms, such as quicksort and merge sort, have better overall performance.
//
// C++ implementation of selection sort
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/sorting
// https://github.com/allalgorithms/cpp
//
// Contributed by: Rituparno Biswas
// Github: @roopbiswas
//
#include <iostream>
// Swap elements
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// Implement selection sort
void selectionSort(int arr[], int n)
{
int i, j, min_id;
for (i = 0; i < n-1; i++)
{
min_id=i;
for (j = i+1; j < n; j++)
if (arr[min_id] > arr[j])
min_id=j;
swap(&arr[i], &arr[min_id]);
}
}
// Function to print elements
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// test
int main()
{
int arr[] = {46, 24, 33, 10, 2, 81, 50};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Unsorted array: \n");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
