Selection sort(sorting algorithm in data structure) and its time complexity

Selection sort Presented by ASMITA 26/01/18 1

SORTING Algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. 2

SELECTION SORT  Selection sorting is conceptually the most simplest sorting algorithm.  This algorithm first finds the smallest element in the array and exchanges it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continues in this way until the entire array is sorted.  Keep doing n-1 times to place all n values in the sorted order. 3

How selection sorting works? 4

Selection sort  input A sequence of n numbers <a1, a2,…..an>  Output A reordering <a1,a2,….an>of the input sequences such that a1<a2<a3…..<an  Idea behind selection sort Left hand Right hand 9 3 6 4 33 9 3 6 4 3 4 9 3 6 4 3 4 6 9 3 6 4 3 4 6 9 6

Pseudo-code for selection sort  Selection sort(A) A[1….N]  For i=1 to A.lenght-1  {  MIN=i  For j=i + 1 to A.lenght  {  If (A[j] <A[MIN])  {  MIN= j  }  } // MIN.elements to its correct position  Temp = A[i]  A[i] =A[MIN]  A[MIN] =temp  } 6 3 1 2 1 2 3 4 i =1 j=2 MIN 1 7

 For i=1 to A.lenght-1  {  MIN=I  For j=i + 1 to A.lenght  {  If (A[j] <A[MIN])  {  MIN= j  } 6 3 1 2 1 2 3 4 i =1 j=2 MIN 1 6 3 1 2 1 2 3 4 i=1 j=3 MIN 2 6 3 1 2 1 2 3 4 i =1 j=4 MIN 3 If (A[j] <A[MIN]) If (A[j] <A[MIN]) 3<6 1<3 9

 For i=1 to A.lenght-1  {  MIN=i  For j=i + 1 to A.lenght  {  If (A[j] <A[MIN])  {  MIN= j  } 1 2 3 4 i =2 j=3 MIN 2 1 2 3 4 i =2 j=3 MIN 2 1 2 3 4 i =2 j=5 MIN 4 If (A[j] <A[MIN]) If (A[j] <A[MIN]) 6<3 2<3 1 3 6 2 1 3 6 21 3 6 2 10

 For i=1 to A.lenght-1  {  MIN=i  For j=i + 1 to A.lenght  {  If (A[j] <A[MIN])  {  MIN= j  } 1 2 3 4 i =3 j=4 MIN 3 1 2 3 4 i =3 j=5 MIN 4 1 2 3 4 MIN 4 If (A[j] <A[MIN]) 3<6 1 2 6 3 1 2 3 61 2 6 3 11

Time complexity of selection sort  Selection sort(A) A[1….N] cost times  For i=1 to A.lenght-1 c1 n  {  MIN=I c2 n-1  For j=i + 1 to A.lenght  {  If (A[j] <A[MIN])  { c3 n+n-1+…..1 // 2 n=n  MIN= j = n(n+1)/2 3 n=n-1  } 4 n=n-2  } n-1 n=1  Temp = A[i] c4 n-1  A[i] =A[MIN] c5 n-1  A[MIN] =temp c6 n-1  } 12

Selection sort(sorting algorithm in data structure) and its time complexity

In this document

More Related Content

What's hot

Similar to Selection sort(sorting algorithm in data structure) and its time complexity

More from Computer_ at_home

Recently uploaded

Selection sort(sorting algorithm in data structure) and its time complexity