-
Notifications
You must be signed in to change notification settings - Fork 202
/
Copy pathSelection_Sort.py
87 lines (64 loc) · 3.14 KB
/
Selection_Sort.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#Selection sort involves finding the minimum element in one pass through the array
#and then swapping it with the first position of the unsorted part of the array.
#Time complexity of selection sort is O(n^2) in all cases
def selection_sort(array):
count = 0
for i in range(len(array)-1): #-1 because when only 1 elment remians, it will be already be sorted
print(array)
minimum = array[i] #We set the minu=imum element to be the ith element
minimum_index = i #And the minimum index to be the ith index
for j in range(i+1,len(array)): #Then we check the array from the i+1th element to the end
count += 1
if array[j] < minimum: #If a smaller element than the minimum element is found, we re-assign the minimum element and the minimu index
minimum = array[j]
minimum_index = j
if minimum_index != i: #If minimum index has changed, i.e, a smaller element has been found, then we swap that element with the ith element
array[minimum_index], array[i] = array[i], array[minimum_index]
return (f'{array} \nNumber of comparisons = {count}')
array = [5,9,3,10,45,2,0]
print(selection_sort(array))
'''
[5, 9, 3, 10, 45, 2, 0]
[0, 9, 3, 10, 45, 2, 5]
[0, 2, 3, 10, 45, 9, 5]
[0, 2, 3, 10, 45, 9, 5]
[0, 2, 3, 5, 45, 9, 10]
[0, 2, 3, 5, 9, 45, 10]
[0, 2, 3, 5, 9, 10, 45]
Number of comparisons = 21
'''
sorted_array = [5,6,7,8,9]
print(selection_sort(sorted_array))
"""
[5, 6, 7, 8, 9]
[5, 6, 7, 8, 9]
[5, 6, 7, 8, 9]
[5, 6, 7, 8, 9]
[5, 6, 7, 8, 9]
Number of comparisons = 10
"""
reverse_sorted_array = [9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]
print(selection_sort(reverse_sorted_array))
'''
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10]
[-10, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, 9]
[-10, -9, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, 8, 9]
[-10, -9, -8, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, 7, 8, 9]
[-10, -9, -8, -7, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, 3, 2, 1, 0, -1, -2, -3, -4, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, 2, 1, 0, -1, -2, -3, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, 1, 0, -1, -2, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, 0, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Number of comparisons = 190
'''