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

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort.
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

1. Selection sort Presented by ASMITA 26/01/18 1

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

3. 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

4. How selection sorting works? 4

5. 5

6. 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 3 3 9 3 6 4 3 4 9 3 6 4 3 4 6 9 3 6 4 3 4 6 9 6

7. 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 2 3 4 i =1 j=2 MIN 1 7

8. Selection sort 8

9. 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 2 3 4 i =1 j=2 MIN 1 6 3 1 2 2 3 4 i =1 j=3 MIN 2 6 3 1 2 2 3 4 i =1 j=4 MIN 3 If (A[j] <A[MIN ]) If (A[j] <A[MIN ]) 3<6 1<3 9

10. For i=1 to A.lenght-1 { MIN=i For j=i + 1 to A.lenght { If (A[j] <A[MIN]) { MIN= j } 2 3 4 i =2 j=3 MIN 2 2 3 4 i =2 j=3 MIN 2 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 2 1 3 6 2 10

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

12. 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

13. Total time 13

14. As in insertion sort 14

15. 15

16. For example 16

17. 17

18. 18

19. 19

20. 20 Thank you