Selection sort program in Python
In this post, you will learn about the selection sort program in Python.
Selection sort is a simple sorting algorithm. In computer science, selection sort is an in-place comparison sorting algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list. It has an O(n²) time complexity where n is the total number of items in the list, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort.
In selection sort, elements are arranged in two parts- sorted one and unsorted one.
At first, the sorted part is empty, and the unsorted part contains all the elements. At every step, the algorithm finds the minimal element from an unsorted part and places it at the end of the sorted part. In the last part of the process, unsorted part becomes empty and the sorted part contains all the elements in sorted order.
Selection Sort Example
These are the selection sorting techniques.
Search for the element that is less than the first element. A[2] < A[0] so interchange them.
Next search for the next element that is less than the second element. A[2] < A[1] so interchange them.
Next search for the next element that is less than the third element. A[4] < A[2] so interchange them.
Next search for the next element that is less than the fourth element. A[5] < A[4] so interchange them.
Next search for the next element that is less than the fifth element. A[5] < A[4] so interchange them.
Selection Sorting Algorithm
for i <- 1 to n-1 do
min <- i;
for j <- i+1 to n do
if A[j] < A[i] then
min <- j
if min!= i then
temp <- A[i]
A[i] <- A[min]
A[min] <- temp
Selection sort program in Python
In the given example, we create a function selection_sort that takes an array as an argument. Inside this function, we create a loop with a loop variable step to the size of the array. We create a variable min_index with an initial value step. Next, we create an inner loop with a loop variable i that counts from step + 1 up to the size of the array. Inside this loop, if the elements at index i is smaller than the element at index min_index, then set min_index equal to i. After the inner loop finishes, swap the elements at index step and min_index.
# Selection sort program in Python
def selection_sort(array, size):
for step in range(size):
min_index = step
for i in range(step + 1, size):
# select the minimum element in each loop
if array[i] < array[min_index]:
min_index = i
# put min at the correct position
(array[step], array[min_index]) = (array[min_index], array[step])
data = [-12,3,45,26,-11,-4,53]
size = len(data)
selection_sort(data, size)
print('Sorted Array in Ascending Order:')
print(data)
Output of the above code:
Sorted Array in Ascending Order:
[-12, -11, -4, 3, 26, 45, 53]
Related Articles
Convert Python list to numpy arrayConvert string to list Python
Python program to list even and odd numbers of a list
Python loop through list
Sort list in descending order Python
Convert array to list Python
Python take screenshot of specific window
Web scraping Python BeautifulSoup
Check if two strings are anagrams Python
Python program to add two numbers
Print new line python
Python for loop index
Convert List to Dataframe Python
numpy random choice
Dictionary inside list python
Check if list is empty Python
Python raise keyword
Python program to get the largest number from a list
Python program to map two lists into a dictionary