# Selection sort Algorithm

## Selection sort

Selection sort is an in-place comparison sort that works by dividing the input list into two parts: a sorted sublist of items that are built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Initially, the sorted portion is empty and the unsorted portion is the entire input list. The algorithm repeatedly selects the smallest element from the unsorted portion of the list and appends it to the sorted portion until there are no more elements remaining in the unsorted portion.

Here is some example pseudocode for the selection sort algorithm:

```for i = 0 to n-2:
# Find the minimum element in the unsorted portion of the list
min_index = i
for j = i+1 to n-1:
if list[j] < list[min_index]:
min_index = j
# Swap the minimum element with the first element of the unsorted portion
list[i], list[min_index] = list[min_index], list[i]
```

Selection sort has a time complexity of O(n^2), which makes it inefficient for large lists. However, it is simple to implement and requires minimal additional space.

## Steps to Sort Array

### To perform selection sort on the list [64, 25, 12, 22, 11], you can follow these steps:

1. Begin with the entire list as the unsorted portion and an empty sorted portion. The unsorted portion is [64, 25, 12, 22, 11] and the sorted portion is [].
2. Find the minimum element in the unsorted portion of the list. The minimum element is 11.
3. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now  and the unsorted portion is [64, 25, 12, 22].
4. Find the minimum element in the unsorted portion of the list. The minimum element is 12.
5. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now [11, 12] and the unsorted portion is [64, 25, 22].
6. Find the minimum element in the unsorted portion of the list. The minimum element is 22.
7. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now [11, 12, 22] and the unsorted portion is [64, 25].
8. Find the minimum element in the unsorted portion of the list. The minimum element is 25.
9. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now [11, 12, 22, 25] and the unsorted portion is .
10. Find the minimum element in the unsorted portion of the list. The minimum element is 64.
11. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now [11, 12, 22, 25, 64] and the unsorted portion is [].
12. There are no more elements remaining in the unsorted portion, so the sorting is complete. The final sorted list is [11, 12, 22, 25, 64].

## Selection Sort in Different language

### C++

```#include <algorithm>
#include <iostream>
#include <vector>

void selectionSort(std::vector<int> &list) {
for (int i = 0; i < list.size() - 1; i++) {
// Find the minimum element in the unsorted portion of the list
int minIndex = i;
for (int j = i + 1; j < list.size(); j++) {
if (list[j] < list[minIndex]) {
minIndex = j;
}
}
// Swap the minimum element with the first element of the unsorted portion
std::swap(list[i], list[minIndex]);
}
}

int main() {
std::vector<int> list = {64, 25, 12, 22, 11};
selectionSort(list);
for (int n : list) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
}
```

### Java

```import java.util.Arrays;

public class SelectionSort {
public static void selectionSort(int[] list) {
for (int i = 0; i < list.length - 1; i++) {
// Find the minimum element in the unsorted portion of the list
int minIndex = i;
for (int j = i + 1; j < list.length; j++) {
if (list[j] < list[minIndex]) {
minIndex = j;
}
}
// Swap the minimum element with the first element of the unsorted portion
int temp = list[i];
list[i] = list[minIndex];
list[minIndex] = temp;
}
}

public static void main(String[] args) {
int[] list = {64, 25, 12, 22, 11};
selectionSort(list);
System.out.println(Arrays.toString(list)); // [11, 12, 22, 25, 64]
}
}
```

### JavaScript

```function selectionSort(list) {
for (let i = 0; i < list.length - 1; i++) {
// Find the minimum element in the unsorted portion of the list
let minIndex = i;
for (let j = i + 1; j < list.length; j++) {
if (list[j] < list[minIndex]) {
minIndex = j;
}
}
// Swap the minimum element with the first element of the unsorted portion
[list[i], list[minIndex]] = [list[minIndex], list[i]];
}
return list;
}

const sortedList = selectionSort([5, 2, 4, 6, 1, 3]);
console.log(sortedList); // [1, 2, 3, 4, 5, 6]
```

### PHP

```<?php

function selectionSort(array &\$list) {
for (\$i = 0; \$i < count(\$list) - 1; \$i++) {
// Find the minimum element in the unsorted portion of the list
\$minIndex = \$i;
for (\$j = \$i + 1; \$j < count(\$list); \$j++) {
if (\$list[\$j] < \$list[\$minIndex]) {
\$minIndex = \$j;
}
}
// Swap the minimum element with the first element of the unsorted portion
\$temp = \$list[\$i];
\$list[\$i] = \$list[\$minIndex];
\$list[\$minIndex] = \$temp;
}
}

\$list = [64, 25, 12, 22, 11];
selectionSort(\$list);
print_r(\$list); // Array (  => 11  => 12  => 22  => 25  => 64 )
```

### Python

```def selection_sort(list):
for i in range(len(list) - 1):
# Find the minimum element in the unsorted portion of the list
min_index = i
for j in range(i + 1, len(list)):
if list[j] < list[min_index]:
min_index = j
# Swap the minimum element with the first element of the unsorted portion
list[i], list[min_index] = list[min_index], list[i]
return list

sorted_list = selection_sort([5, 2, 4, 6, 1, 3])
print(sorted_list) # [1, 2, 3, 4, 5, 6]
```

Bubble Sort Algorithm

Insertion sort: a Sorting Algorithm

List of Sorting Algorithms