Selection sort Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.
Example :
Algorithm Selectionsort[A (0..n-1)]
// Sort a given array by Selection sort.
// Input : An array A(0,n-1) of orderable elements.
// Output : Array A [0,n-1] sorted in non- decreasing order .
for = 0 to n-1 do
min =i
for j=i+1 to n-1 do
if A[j] < A[min]
Swap A[i] & A[min]
#include < stdio.h>
void selection(int arr[], int n)
{
int i, j, small;
for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
{
small = i; //minimum element in unsorted array
for (j = i+1; j < n; j++)
if (arr[j] < arr[small])
small = j;
// Swap the minimum element with the first element
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
}
}
void printArr(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
selection(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
Code
public class Selection
{
void selection(int a[]) /* function to sort an array with selection sort */
{
int i, j, small;
int n = a.length;
for (i = 0; i < n-1; i++)
{
small = i; //minimum element in unsorted array
for (j = i+1; j < n; j++)
if (a[j] < a[small])
small = j;
// Swap the minimum element with the first element
int temp = a[small];
a[small] = a[i];
a[i] = temp;
}
}
void printArr(int a[]) /* function to print the array */
{
int i;
int n = a.length;
for (i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
public static void main(String[] args) {
int a[] = { 91, 49, 4, 19, 10, 21 };
Selection i1 = new Selection();
System.out.println("\nBefore sorting array elements are - ");
i1.printArr(a);
i1.selection(a);
System.out.println("\nAfter sorting array elements are - ");
i1.printArr(a);
System.out.println();
}
}
Code
def selection(a): # Function to implement selection sort
for i in range(len(a)): # Traverse through all array elements
small = i # minimum element in unsorted array
for j in range(i+1, len(a)):
if a[small] > a[j]:
small = j
# Swap the found minimum element with
# the first element
a[i], a[small] = a[small], a[i]
def printArr(a): # function to print the array
for i in range(len(a)):
print (a[i], end = " ")
a = [69, 14, 1, 50, 59]
print("Before sorting array elements are - ")
printArr(a)
selection(a)
print("\nAfter sorting array elements are - ")
selection(a)
printArr(a)
Code
2 3 1 8 3 4
1 2 2 3 3 4 8
best case, average case, worst case
Radix Sort
Shell sort