 ## What is Selection Sdort

• It is a simple sort algorithm that revolves around the comparison
• In each iteration, one element gets placed
• We choose the minimum element in the array and place is at the beginning of the array by swapping with the front element
• We can also do this by choosing maximum element and placing it at the rear end
• Selection sort basically selects an element in every iteration and place it at the appropriate position

## Selection Sort Pseudocode

• Set min  index to the first index of an unsortedddddddddddddddd array
• Iterate the entire unsorted array and do the comparison with min
• If element present at the min is greater than the element present at the current index then update min with a current index
• Once the iteration is complete, swap the element of min index with the first element of the unsorted part
• For descending order, instead of maintaining the smallest element index, maintain the largest element index

## Selection sort Algorithm

``````SelectionSort(arr, n)
iterate (n - 1) times
set the first unsorted element index as the min
for each of the unsorted elements
if element < currentMin
set element's index as new min
swap element at min with first unsorted position
end selectionSort

``````

## Selection sort Algorithm Dry Run

Input:

First step – marking of sorted part

After i=1

After i=2

After i=3

After i=4, no iteration is required as the last element is already sorted

## Selection sort Time Complexity

• In the worst case, in every iteration, we have to traverse the entire array for finding min elements and this will continue for all n elements. Hence this will perform n^2 operations in total.
• In the best case that is sorted array, we can do some modification by using lag to check whether the lament is already sorted or not
• Best Time Complexity: O(n)
• Average Time Complexity: O(n^2)
• Worst Time Complexity: O(n^2)

## Selection sort Space Complexity

• No auxiliary space is required in Selection Sort implementation that is we are not using any arrays, linked list, stack, queue, etc to store our elements
• Hence space complexity is: O(1)

## Selection sort in C

``````#include <stdio.h>

void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}

//selection sort function
void selectionSort(int arr[], int n) {
for (int j = 0; j< n - 1; j++) {
int min = j;
for (int i = j + 1; i < n; i++) {

if (arr[i] < arr[min])
min = i;
}

swap(&arr[min], &arr[j]);
}
}

void display(int arr[], int n) {
for (int i = 0; i < n; ++i) {
printf("%d  ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {20, 12, 10, 15, 2};
int n = sizeof(arr) / sizeof(arr);
printf("Elements before sorting: \n");
selectionSort(arr, n);
printf("Elements after sorting:\n");
display(arr, n);
}

Output of the program:
Elements before sorting:
2  12  10  15  20

Elements after sorting:
2  12  10  15  20

``````

## Selection sort in Java

``````class SelectionSort {
//selection sort function
void selectionSort(int arr[]) {
int size = arr.length;

for (int j = 0; j < size - 1; j++) {
int min = j;

for (int i = j + 1; i < size; i++) {

if(arr[i]<arr[min])
min = i;

}

int tmp = arr[j];
arr[j] = arr[min];
arr[min] = tmp;
}
}

// method for printing the elements
void display(int arr[]) {
int size = arr.length;
for (int i = 0; i < size; i++)
System.out.print(arr[i]+" ");
System.out.println();

}

public static void main(String args[]) {
int[] arr = { 20, 12, 10, 15, 2 };
SelectionSort ss = new SelectionSort();
System.out.println("Elements after sorting: ");
ss.display(arr);
ss.selectionSort(arr);
System.out.println("Elements before sorting: ");
ss.display(arr);
}
}

Output of the program:
Elements before sorting:
2  12  10  15  20

Elements after sorting:
2  12  10  15  20
``````

## Selection sort in C++

``````#include <iostream>
using namespace std;

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

void display(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

//selection sort function
void selectionSort(int arr[], int n) {
for (int j = 0; j < n - 1; j++) {
int min = j;
for (int i = j + 1; i < n; i++) {

if (arr[i] < arr[min])
min = i;
}

swap(&arr[min], &arr[j]);
}
}

int main() {
int arr[] = {20, 12, 10, 15, 2};
int n = sizeof(arr) / sizeof(arr);
cout << "Elements before sorting:\n";
display(arr, n);
selectionSort(arr, n);
cout << "Elements after sorting:\n";
display(arr, n);
}

Output of the program:
Elements before sorting:
2  12  10  15  20

Elements after sorting:
2  12  10  15  20
``````

## Selection sort in Python

``````//selection sort function
def selectionSort(arr, n):

for stp in range(n):
min = stp

for i in range(stp + 1, n):

if arr[i] < arr[min]:
min = i

(arr[stp], arr[min]) = (arr[min], arr[stp])

arr = [-2, 45, 0, 11, -9]
n = len(arr)
print('Elements before sorting:')
print(arr)
selectionSort(arr, n)
print('Elements after sorting:')
print(arr)

Output of the program:
Elements before sorting:
2  12  10  15  20

Elements after sorting:
2  12  10  15  20
``````

## Selection Sort Example

Example1

Find kth smallest element in the array

Input

5

12 45 17 99 34

2

Output

17

JAVA Code

``````import java.util.*;

class Solution {
//selection sort function
static void findKSmallest(int arr[],int n,int k) {
if(k>n){
System.out.println("No such element possible");
return;
}

for (int j = 0; j < k ; j++) {
int min = j;

for (int i = j + 1; i < n; i++) {

if(arr[i]<arr[min])
min = i;

}

int tmp = arr[j];
arr[j] = arr[min];
arr[min] = tmp;
}
}

public static void main(String args[]) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++)
arr[i]=in.nextInt();
int k=in.nextInt();
findKSmallest(arr,n,k);
}
}
``````

C++ code

``````#include <iostream>
using namespace std;

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

//selection sort function
void findKSmallest(int arr[], int n, int k) {
if(k>n){
printf("No such element possible");
return;
}
for (int j = 0; j < k; j++) {
int min = j;
for (int i = j + 1; i < n; i++) {

if (arr[i] < arr[min])
min = i;
}

swap(&arr[min], &arr[j]);
}

cout<<arr[k-1];
}

int main() {
int n,k;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
cin>>k;
findKSmallest(arr,n,k);
}

``````

C Code

``````#include <stdio.h>

void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}

//selection sort function
void findKSmallest(int arr[], int n, int k) {
if(k>n){
printf("No such element possible");
return;
}
for (int j = 0; j< k; j++) {
int min = j;
for (int i = j + 1; i < n; i++) {

if (arr[i] < arr[min])
min = i;
}

swap(&arr[min], &arr[j]);
}

}

int main() {
int n,k;
scanf("%d",&n);
int arr[n];
for(int i=0; i<n; i++)
scanf("%d",&arr[i]);
scanf("%d",&k);

findKSmallest(arr, n ,k);
}
``````

## Selection sort vs Bubble sort vs Insertion sort

• In terms of algorithm
• In Insertion sort, adjacent elements are compared and sorted if they are in the wrong order.
• In the Selection Sort, we select the smallest element and swap it with the 0th index element in the first iteration. This selection continues for n-1 elements and the single element is already sorted and we will have array sorted by 1 element in every iteration
• In Insertion sort, we create partitions of sorted and unsorted parts. One by one element from the sorted art is taken and sent to the unsorted part for checking and placing it to the right position in sorting using swaps.
• In terms of time and space complexity
• All 3 sorts have O(n2) time complexity. But via flag variables we can reduce the time complexity of Insertion and insertion to O(n) is the best case.
• Space Complexity is the same for all i.e., O(1)

• In terms of speed
• Insertion sort may work best with an already sorted array and there is no need for any extra flag.
• In terms of in-place
• In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space.
• Selection, Insertion, and Insertion are in-place algorithms and do not require any auxiliary memory.
• In terms of stability
• Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same.
• Insertion and Insertion are stable algorithms but the naive selection is not as swapping may cost stability.

0