Sorting Algorithm

ShareIn this tutorial we will learn about Selection sort algorithm.

In this technique we find the smallest element in each pass and place it in the appropriate position to get the elements in ascending or descending order.

In pass 1, smallest element is searched between a[0] to a[n-1] and swapped with a[0].

In pass 2, smallest element is searched between a[1] to a[n-1] and swapped with a[1].

In a similar way the process is carried out n-1 times.

- Selection sort requires n – 1 pass to sort an array of n elements.
- In each pass we search for the smallest element from the search range and swap it with appropriate place.
- In each pass we have n – k comparisons, where n is the number of elements and k is the pass number.

So, 1st pass requires n – 1 comparisons,

kth pass requires n – k comparisons and

the last pass requires 1 comparison.

```
/**
* a[0:n-1] is an array of n elements.
* temp is a variable to facilitate exchange.
*/
SelectionSort(a,n)
Begin
for k = 1 to n-1 by 1 do //this is for pass
Set small = a[k-1];
Set pos = k-1;
for j = k to n-1 by 1 do //this is for searching small element
if(a[j] < small) then
Set small = a[j];
Set pos = j;
endif
endfor
if(pos != k-1) then //swap value
Set temp = a[k-1];
Set a[k-1] = a[pos];
Set a[pos] = temp;
endif
endfor
End
```

```
#include <stdio.h>
//function declaration
void selectionSort(int *a, int n);
int main(){
//variable declaration
int arr[5], i;
//input
for(i = 0; i < 5; i++)
scanf("%d", &arr[i]);
//sort
selectionSort(arr, 5); //passing arr address and no. of elements
//output
for(i = 0; i < 5; i++)
printf("%d\n", arr[i]);
return 0;
}
//function definition
void selectionSort(int *a, int n){
int k, j, pos, small, temp;
for(k = 1; k <= n-1; k++){
small = a[k-1];
pos = k-1;
for(j = k; j <= n-1; j++){
if(a[j] < small){
small = a[j];
pos = j;
}
}
if(pos != k-1){
temp = a[k-1];
a[k-1] = a[pos];
a[pos] = temp;
}
}
}
```

1st pass requires (n-1) comparison

2nd pass required (n-2) comparison

...
last pass requires 1 comparison.

So, total comparison = (n-1) + (n-2) + ... + 1

= n(n-1)/2

= O(n^{2})

- How to install Apache, MySQL, PHP on macOS Mojave 10.14 How to Mac
- Exercise 1 Flowchart
- How to install Apache, MySQL, PHP on macOS Catalina 10.15 How to Mac
- How to install PostgreSQL on Mac using Homebrew How to Mac
- How to change default shell to bash on macOS Catalina How to Mac
- How to backup and restore MySQL or MariaDB database using mysqldump Reference Database
- HTML Getting Started HTML
- ChartJS | How to create Doughnut Chart using data from MySQL (MariaDB) table and PHP ChartJS
- MongoDB - Delete Documents MongoDB
- MongoDB - Update Documents MongoDB