-
Notifications
You must be signed in to change notification settings - Fork 0
/
selection_sort.py
35 lines (26 loc) · 1.2 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
from typing import List
from ..decorators import process_timer
@process_timer
def selection_sort(array: List[int]) -> List[int]:
"""
## Selection Sort
The selection sort algorithm sorts an array by repeatedly finding the minimum item
from unsorted part and putting it at the beginning.
Time Complexity: `O(N^2)`, The time complexity is O(N2) as there are 2 nested loops:
* One loop to select an element of Array one by one: `O(N)`
* Another loop to compare that element with every other Array element: `O(N)`
Therefore overall complexity = `O(N)` *` O(N)` = `O(N*N)` = `O(N^2)`
Auxiliary Space: `O(1)`, selection sort is an in-place sorting algorithm.
:param array: list of integer numbers that we want sort
:type array: list[int]
:return: list of sorted integer number with selection sort algorithm
:rtype: list[int]
"""
length = len(array)
for counter in range(length - 1):
selected = counter
for index, element in enumerate(array[counter + 1 :], start=counter + 1):
if element < array[selected]:
selected = index
array[counter], array[selected] = array[selected], array[counter]
return array