Scribd
Upload
11 views10 pages

Selection Sort

Uploaded by

samarth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPSX, PDF, TXT or read online on Scribd
11 views10 pages

Selection Sort

Uploaded by

samarth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPSX, PDF, TXT or read online on Scribd
You are on page 1/ 10

Sorting

There are so many things in our real life


that we need to search, like
•A particular record in database,
•Roll numbers in merit list,
•A particular telephone number,
•Any particular page in a book etc.
•Search word from dictionary
Selection Sort
Simplest sorting 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.
Continues in this way until the
entire array is sorted.
Selection Sort (Example)
Consider the set of values:
Find out minimum
Original After Sorted element which is 1
Array one Array at 3rd position
pass Move minimum
3 1
2 1 element at first
2 position
1 2 Take second
3
3 minimum element
4 4 which is 2
4 Here index of
5 5
5 minimum element
6 6 and index of the
6 element to replace
is same…so no
If we continue for
exchange
all elements, there
will be no
exchanges.
Algorithm- Selection
Sort(K,N)
1. [Loop on pass index]
Repeat through step 4 for pass=1,2,…n-1
2. [Initialize minimum index]
min_index <- pass
3. [Make a pass and obtain element with
smallest value]
Repeat for i=pass+1, pass+2,…N
If K[i]<K[min_index]
Then min_index<-I
4. Exchange elements
If min_index!= pass
Then K[pass]<->K[min_index]
Example : 9 2 5 7 4
1. [Loop on pass 1. pass=1
index] 2. min_index=1
3. Repeat for 2 to 5
Repeat through step 4
for pass=1,2,…n-1 for i=2
k[i]<k[min_index]
2. [Initialize minimum
k[2]<k[1]
index]
2<9 true
min_index <- pass
min_index=2
3. [Make a pass and 3. for i=3, k[3]<k[2]
obtain element with 5<2 false
smallest value] for i=4, k[4]<k[2]
Repeat for i=pass+1,
7<2 false
pass+2,…N
If K[i]<K[min_index] for i=5, k[5]<k[2]
Then min_index<-I 4<2 false
4. Exchange 4. If min_index(2)!=
elements pass(1)
Not same
If min_index!= pass
Then exchange elements
Then K[pass]<-
>K[min_index] k[1] and k[2]
Array elements after 1 pass: 2 9 5 7 4
Array elements after 1 pass: 2 9 5 7 4

Pass-2
min_index=2
i 3 4 5
K[i] 5 7 4
K[min_index] 9 5 5
Condition K[i]<k[min_ind K[i]<k[min_ind
ex] K[i]<k[min_in ex]
K[3]<k[2] dex] K[5]<k[3]
5<9 True K[4]<k[3] 4<5 True
7<5 False
Updated
min_index 3 3 5
Exchange Elements : if min_index!= pass
5!=2

Array after 2nd pass is : 2 4 5 7 9


Array after 2nd pass is : 2 4 5 7 9

Pass-3
min_index=3
i 4 5
K[i] 7 9
K[min_index] 5 5
Condition K[i]<k[min_inde
K[i]<k[min_ind
x]
ex]
K[4]<k[3]
7<5 False K[5]<k[3]
9<5 False
Updated
min_index 3 3
Exchange Elements : if min_index!= pass
3!=3 False
No exchange

Array after 2nd pass is : 2 4 5 7 9


For pass 4 and Pass 5,

No exchange would be in array as elements are in sorted


order now.

Analysis of Selection Sort

1. [Loop on pass index]


Repeat through step 4 n-1
for pass=1,2,…n-1 times
2. [Initialize minimum index]
min_index <- pass
3. [Make a pass and obtain
element with smallest value]
Repeat for i=pass+1, n-i
pass+2,…N times
If K[i]<K[min_index] Overall it can be
then min_index<-I considered
4. Exchange elements (n-1)*(n-1)= O(n2)
If min_index!= pass
Then K[pass]<-
>K[min_index]
Stability of sorting
algorithm
A Stable Sort is one where the initial
order of equal items is preserved.

Stabilityis important when we want


to sort by multiple fields.
 For example, if sort the words
"apple", "tree" and "pink" by length,
then "tree", "pink", "apple" is a
stable sort but "pink", "tree", apple"
is not.
Is Selection Sort stable?

You might also like