In this Sorting technique the list is divided into two parts. first one is left end and second one is right end .
The selection Sort is very simple sorting algorithm.
Steps for Selection Sort in C
We have been given a unsorted array. which we’ll make a sorted array using selection sort. first of all find the smallest value in the array and then swap smallest value with the starting value.
According to the below image, 8 is smallest value in this array so 8 is swapped with the first element that is 72.
Similarly, in the next iteration we’ll find the next smallest value, excluding the starting value so in this array 10 is second smallest value, which is to be swapped with 50.
These iteration will continue until we have the largest element to the right most end, along with all the other elements in their correct position.
And then we can finally say that the given array is converted in sorted array.
// C program for implementation of selection sort
// Time Complexity : O(N^2)
// Space Complexity : O(1)
// Best, Avg, Worst Cases : All of them O(N^2)
#include
/* Display function to print values */
void display(int array[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ",array[i]);
printf("\n");
}
// The main function to drive other functions
int main()
{
int array[] = {72, 50, 10, 44, 8, 20};
int size = sizeof(array)/sizeof(array[0]);
printf("Before sorting: \n");
display(array, size);
int i, j, min_idx,temp;
// Loop to iterate on array
for (i = 0; i < size-1; i++)
{
// Here we try to find the min element in array
min_idx = i;
for (j = i+1; j < size; j++){
if (array[j] < array[min_idx])
min_idx = j;
}
// Here we interchange the min element with first one
temp = array[min_idx];
array[min_idx] = array[i];
array[i] = temp;
}
printf("\nAfter sorting: \n");
display(array, size);
return 0;
}
// Selection sort in C++
#include
using namespace std;
// function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// function to print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; i++) {
cout << array[i] << " ";
}
cout << endl;
}
void selectionSort(int array[], int size) {
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}
// put min at the correct position
swap(&array[min_idx], &array[step]);
}
}
// driver code
int main() {
int data[] = {72, 50, 10, 44, 8, 20};
int size = sizeof(data) / sizeof(data[0]);
cout << "Before Sorting:\n";
printArray(data, size);
selectionSort(data, size);
cout << "After Sorting:\n";
printArray(data, size);
}
// Java Program for Insertion Sort
// Time Complexity : O(N^2)
// Space Complexity : O(1)
// Best Case, Worst Case, Avg Case : O(n^2)
class Main
{
// Main method, responsible for the execution of the code
public static void main(String args[])
{
int arr[] = {72, 50, 10, 44, 8, 20};
System.out.println("Before Sorting:");
printArray(arr);
selectionSort(arr);
System.out.println("After Sorting:");
printArray(arr);
}
static void selectionSort(int a[])
{
int len = a.length;
// One by one move boundary of unsorted sub-array
for (int i = 0; i < len-1; i++)
{
// Find the minimum element in unsorted array
int min = i;
for (int j = i+1; j < len; j++)
if (a[j] < a[min])
min = j;
// Swap the found minimum element with the
// first element in unsorted part of the array
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
// Prints the sorted array
static void printArray(int a[])
{
int len = a.length;
for (int i=0; i< len; ++i)
System.out.print(a[i] + " ");
System.out.println();
}
}
Before sorting:
72 50 10 44 8 20
After sorting:
8 10 20 44 50 72
The Selection Sort best and worst case scenarios both follow the time complexity format O(n^2) as the sorting operation involves two nested loops. The size of the array again affects the performance.[1]
| Best | Average | Worst | Space Complexity |
| O(n2) | O(n2) | O(n2) | O(1) |