Selection
Sort
Selection Sort
• Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly selecting
the smallest (or largest) element from the unsorted portion and swapping it with the first unsorted
element. This process continues until the entire array is sorted.
• First, we find the smallest element and swap it with the first element. This way we get the smallest
element at its correct position.
• Then we find the smallest among remaining elements (or second smallest) and swap it with the second
element.
• We keep doing this until we get all elements moved to correct position.
Time Complexity:
• Best-case: O(n2), best case occurs when the array is already sorted. (where n is the number of
integers in an array)
• Average-case: O(n2), the average case arises when the elements of the array are in a disordered or
random order, without a clear ascending or descending pattern.
• Worst-case: O(n2), The worst-case scenario arises when we need to sort an array in ascending order,
but the array is initially in descending order.
Auxiliary Space Complexity: O(1), as no extra space is required for the Selection sort algorithm.
Selection Sort Algorithm
def selectionSort(array, size):
for ind in range(size):
min_index = ind
for j in range(ind + 1, size):
# select the minimum element in every iteration
if array[j] < array[min_index]:
min_index = j
# swapping the elements to sort the array
(array[ind], array[min_index]) = (array[min_index], array[ind])
Selection Sort
def selectionSort(array, size):
for ind in range(size):
min_index = ind
for j in range(ind + 1, size):
# select the minimum element in every iteration
if array[j] < array[min_index]:
min_index = j
# swapping the elements to sort the array
(array[ind], array[min_index]) = (array[min_index], array[ind])
arr = [-2, 45, 0, 11, -9,88,-97,-202,747]
size = len(arr)
print('The array before sorting is:’)
print(arr)
selectionSort(arr, size)
print('The array after sorting in Ascending Order by selection sort is:')
print(arr)
Thankyou
Made by Sukanya Rakshit