Home / Sortings / Selection Sort

Selection Sort

It is a sorting technique. It improves bubble sort by making only one exchange for every pass through the list of elements. First selection sort looks for the largest value when it through the pass and after completing the pass, after that it place in a proper location.


Time complexity of Selection sort: O(n2)

Average Performance: O(n2)

Worst case Performance: O(n2)

Best case performance: O(n2)

Worst Case Space complexity: O(n) total, O(1) auxiliary.

Example on Selection Sort:

52, 45, 789, 46, 89 [Initial Array of elements]

45, 52, 789, 46, 89 [After the first pass, First sub list {45}]

45, 46, 52, 789, 89 [After the second pass, Second sub list {45, 46}]

45, 46, 52, 89, 789 [After the third pass, Third sub list {45, 46, 52}]

45, 46, 52, 89, 789 [After the fourth pass, Fourth sub list {45, 46, 52, 89}]

45, 46, 52, 89, 789 [After the fifth pass or Last pass, sub list {45, 46, 52, 89, 789}]

Algorithm for Selection Sort:

Start

Construct a single dimensional array

Fill the array with elements.

Using the selection sort technique bring the smallest number to the first unsorted position of the array.

Repeat the last step till the entire array is sorted.

Print the sorted array

Stop.

Program for selection Sort in java:

public class SelectionSort {

public static void selectionSort(int[] arr){

for (int i = 0; i < arr.length – 1; i++)

{

int index = i;

for (int j = i + 1; j < arr.length; j++){

if (arr[j] < arr[index]){

index = j;//searching for lowest index

}

}

int smallerNumber = arr[index];

arr[index] = arr[i];

arr[i] = smallerNumber;

}

}

public static void main(String a[]){

int[] arr1 = {9,14,3,2,43,11,58,22};

System.out.println(“Before Selection Sort”);

for(int i:arr1){

System.out.print(i+” “);

}

System.out.println();

selectionSort(arr1);//sorting array using selection sort

System.out.println(“After Selection Sort”);

for(int i:arr1){

System.out.print(i+” “);

}

}

}

Output of the above program:

Before Selection Sort

9 14 3 2 43 11 58 22

After Selection Sort

2 3 9 11 14 22 43 58

selection sort
selection sort

Click here to View otherSorting Techniques

About GSK

Hi, i am Santosh Gadagamma, a tutor in Software Engineering and an enthusiast for sharing knowledge in Computer Science and other domains. I developed this site to share knowledge to all the aspirants of technologies like, Java, C/C++, DBMS/RDBMS, Bootstrap, Big Data, Javascript, Android, Spring, Hibernate, Struts and all levels of software project design, development, deployment, and maintenance. As a programmer I believe that, "The world now needs computers to function." Hope, this site guides you as a learning tool towards greater heights. I believe that Education has no end points and i wish to learn more in the process of teaching you.

Check Also

Sorting Technique

In this blog I am going to discuss about sorting, what is sorting and how …