[go: up one dir, main page]
Scribd
Upload
139 views20 pages

Selection Sort

This document discusses selection sort, a sorting algorithm where the smallest element is selected from an unsorted list and placed in the first position of the sorted list. It provides explanations, pseudocode, and simulations of selection sort. The time complexity of selection sort is O(n2) as it contains two nested loops to iterate through the list, making it a quadratic time algorithm.

Uploaded by

Akif Vohra
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPS, PDF, TXT or read online on Scribd
139 views20 pages

Selection Sort

This document discusses selection sort, a sorting algorithm where the smallest element is selected from an unsorted list and placed in the first position of the sorted list. It provides explanations, pseudocode, and simulations of selection sort. The time complexity of selection sort is O(n2) as it contains two nested loops to iterate through the list, making it a quadratic time algorithm.

Uploaded by

Akif Vohra
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPS, PDF, TXT or read online on Scribd
You are on page 1/ 20

DATA

STRUCTURES

MAHESH GOYANI
MAHATMA GANDHI INSTITUE OF TECHNICAL EDUCATION & RESEARCH CENTER
mgoyani@rediffmail.com

(C) GOYANI MAHESH 1


SELECTION
SORT

(C) GOYANI MAHESH 2


TERMINOLOGY

 In plain English: Find the smallest element and place it in the


first position, swapping places with the original first element;
continue with successive elements

 In pseudo code:
for each element from first to last
find smallest successive element
swap the elements

(C) GOYANI MAHESH 3


Swapping Action

20 8 5 10 7

5 8 20 10 7

5 7 20 10 8

5 7 8 10 20

5 7 8 10 20

(C) GOYANI MAHESH 4


 Start by finding the smallest entry.
 Swap the smallest entry with the first entry.

7 0
6 0
5 0

4 0
3 0
2 0
1 0

0
[ [0]
1 ] [ [1]
2 ] [ [2]
3 ] [[3]
4 ] [ [4]
5 ] [[5]
6 ]
(C) GOYANI MAHESH 5
7 0
6 0
5 0

4 0
3 0
2 0
1 0

0
[ [0]
1 ] [ [1]
2 ] [ [2]
3 ] [[3]
4 ] [ [4]
5 ] [[5]
6 ]
(C) GOYANI MAHESH 6
 Part of the array is now sorted.

Sorted side Unsorted side


7 0
6 0
5 0

4 0
3 0
2 0
1 0

0
[ [0]
1 ] [ [1]
2 ] [ [2]
3 ] [[3]
4 ] [ [4]
5 ] [[5]
6 ]
(C) GOYANI MAHESH 7
 Find the smallest element in the unsorted side.

Sorted side Unsorted side

[0] [1] [2] [3] [4] [5]


(C) GOYANI MAHESH 8
 Find the smallest element in the unsorted side.
 Swap with the front of the unsorted side.

Sorted side Unsorted side

[0] [1] [2] [3] [4] [5]


(C) GOYANI MAHESH 9
 We have increased the size of the sorted side by one
element.

Sorted side Unsorted side

[0] [1] [2] [3] [4] [5]


(C) GOYANI MAHESH 10
Sorted side Unsorted side

 The process Smallest


Smallest
continues...!! from
from
unsorted
unsorted

[0] [1] [2] [3] [4] [5]


(C) GOYANI MAHESH 11
Sorted side Unsorted side

 The process p eedd


w aappp
continues...!! SSw itih
ww th t
nt
frfroon

[0] [1] [2] [3] [4] [5]


(C) GOYANI MAHESH 12
Sorted
Sortedside
side
is
isbigger
bigger
Sorted side Unsorted side

 The process
continues...!!

[0] [1] [2] [3] [4] [5]


(C) GOYANI MAHESH 13
Sorted side Unsorted side

[0] [1] [2] [3] [4] [5]


(C) GOYANI MAHESH 14
SORTED..!!

[0] [1] [2] [3] [4] [5]


(C) GOYANI MAHESH 15
Simulation

22
13 45 13
22 97 43

13 45
22 22
45 97 43

13 22 43
45 97 45
43

13 22 43 97
45 45
97

13 22 43 45 97 DONE..!!

(C) GOYANI MAHESH 16


Simulation

12
6 12
6 22 14 8 17

6 8
12 22 14 12
8 17

(C) GOYANI MAHESH 17


Simulation

6 8 12
22 14 12
22 17

6 8 12 14 17
22 22
17

(C) GOYANI MAHESH 18


Simulation

7 2 8 5 4

2 7 8 5 4

2 4 8 5 7

2 4 5 8 7

2 4 5 7 8

(C) GOYANI MAHESH 19


COMPLEXITY

 Analysis of the code shows that the outer loop executes n-1 times;

 for the first iteration of the outer loop, the inner loop executes n-1
times

 for the second iteration of the outer loop, the inner loop executes n-
2 times

 etc

 for the last iteration of the outer loop, the inner loop executes 1 time

 thus the execution time is (n-1) + (n-2) + (n-3) + … + 3 + 2 +


1

 the sum of this series is (n2 - n) / 2

 selection sort is O(n2 )

(C) GOYANI MAHESH 20

You might also like