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 unsorted part contains all the elements. At every step, the algorithm finds the minimal element from an unsorted part and placed 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 less than the first element. A < A so interchange them.
Next search for the next element less than the second element. A < A so interchange them.
Next search for the next element less than the third element. A < A so interchange them.
Next search for the next element less than the fourth element. A < A so interchange them.
Next search for the next element less than the fifth element. A < A 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 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 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 indexes step and min_index.
Output of the above code:
# 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)
Sorted Array in Ascending Order: [-12, -11, -4, 3, 26, 45, 53]
Related ArticlesConvert Python list to numpy array
Convert 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