Selection Sort in Python
Introduction to Selection Sort in Python
Selection sort in Python is a simple sorting algorithm that repeatedly finds the minimum (or maximum) element from the unsorted part of an array and moves it to the beginning (or end) of the sorted part.
In this guide, we’ll delve into how Selection Sort works, provide Python code examples, and discuss scenarios where it’s most beneficial.
What is Selection Sort in Python?
Selection Sort is a simple comparison-based sorting algorithm used to arrange elements in ascending or descending order in a Python list. The main idea behind Selection Sort is to divide the list into two parts: the sorted part and the unsorted part.
- In each iteration, it finds the minimum (or maximum) element from the unsorted part and moves it to the end of the sorted part. This process repeats until the entire list is sorted.
Pseudocode for Selection Sort in Python
This pseudocode outlines the steps of the Selection Sort algorithm, which involve finding the minimum element in the unsorted part of the list and swapping it with the first element in the unsorted part.
- This process is repeated for each element until the entire list is sorted.
SelectionSort(arr):
n = length of arr # Get the length of the input list
for i from 0 to n - 1: # Iterate through each element in the list
min_index = i # Assume the current element is the minimum
for j from i + 1 to n: # Search for the minimum element in the unsorted part
if arr[j] < arr[min_index]:
min_index = j # Update the index of the minimum element
if min_index is not equal to i:
swap arr[i] and arr[min_index] # Swap the current element with the minimum element
Working of Selection Sort in Python
Following are the steps for the working of Selection Sort :
- Set the first element as minimum one and continuously assess the minimum value by comparing it to subsequent elements. If a smaller element is encountered, update the minimum value accordingly. Repeat this process until the final element is evaluated.
- Following each iteration, the minimum element is positioned at the beginning of the unsorted list.
3. During each iteration, indexing commences from the initial unsorted element. Steps 1 through 3 are reiterated until all elements are correctly positioned
4. Repeat this process until we get final sorted array :
Algorithms for Selection Sort in Python
Here’s the algorithm for the Selection Sort in :
Start with the entire list as the unsorted section. Initialize the sorted section as an empty list.
For each pass, find the minimum (or maximum) element in the unsorted section by iterating through it.
Once you’ve found the minimum (or maximum) element, swap it with the first element in the unsorted section. This effectively moves it from the unsorted section to the sorted section.
Repeat steps 2 and 3 for the remaining unsorted elements. In each pass, the sorted section grows by one element, and the unsorted section shrinks by one element.
Continue these steps until the entire list is sorted.
Example of Selection Sort in Python using Function
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
# Find the minimum element in the unsorted section
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap the minimum element with the first element in the unsorted section
arr[i], arr[min_index] = arr[min_index], arr[i]
# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
selection_sort(my_list)
print("Sorted List:", my_list)
Output :
Sorted List: [11, 12, 22, 25, 34, 64, 90]
Explanation :
In this implementation, the selection sort function takes a list ‘arr’ as an argument and sorts it in ascending order using the Selection Sort algorithm. The sorted result will be stored in the same list.
Implementation of Selection Sort in Python with user input
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
# Find the minimum element in the unsorted section
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap the minimum element with the first element in the unsorted section
arr[i], arr[min_index] = arr[min_index], arr[i]
# Input from the user
user_input = input("Enter a list of numbers separated by spaces: ")
user_list = [int(x) for x in user_input.split()]
# Call the selection_sort function to sort the user's list
selection_sort(user_list)
# Display the sorted list
print("Sorted List:", user_list)
Output :
Enter a list of numbers separated by spaces: 45 12 67 2 89 54 Sorted List: [2, 12, 45, 54, 67, 89]
Explanation :
The user is prompted to input a list of numbers separated by spaces. The input is split into individual numbers and stored in user_list. The selection_sort function is called to sort the user_list. The sorted list is displayed as the output.
Implementation of Selection Sort in Python using list
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
# Find the minimum element in the unsorted section
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap the minimum element with the first element in the unsorted section
arr[i], arr[min_index] = arr[min_index], arr[i]
# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
selection_sort(my_list)
print("Sorted List:", my_list)
Output :
Sorted List: [11, 12, 22, 25, 34, 64, 90]
Explanation :
The Python code uses the Selection Sort algorithm to sort a list of numbers in ascending order. It repeatedly finds the minimum element in the unsorted part of the list and swaps it with the first unsorted element. This process continues until the entire list is sorted, resulting in [11, 12, 22, 25, 34, 64, 90].
Time and Space Complexity for Selection Sort
The time and space complexity of Selection Sort is as follows:
Time Complexity:
- In the worst case, average case, and best case, Selection Sort has a time complexity of O(n^2), where ‘n’ is the number of elements in the list.
- This is because, for each element in the list, it needs to compare with all other elements in the unsorted part, resulting in quadratic time complexity.
Space Complexity:
- Selection Sort is an in-place sorting algorithm, meaning it doesn’t require additional memory to sort the list.
- Its space complexity is O(1), indicating that the amount of memory used by the algorithm remains constant regardless of the input size.
To wrap it up:
In conclusion, Selection Sort in Python is a straightforward sorting algorithm that repeatedly selects the minimum (or maximum) element from the unsorted portion of a list and places it in the sorted section. While it’s easy to implement and requires minimal memory, its time complexity of O(n^2) makes it inefficient for large datasets. It’s best suited for educational purposes or when simplicity is prioritized over performance.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
When should I use Selection Sort ?
Selection Sort is suitable for educational purposes to understand sorting algorithms and for small datasets. It’s not recommended for large lists where more efficient sorting algorithms like Merge Sort or Quick Sort are preferred.
Question 2.
How does Selection Sort differ from other sorting algorithms in Python?
Selection Sort differs from other sorting algorithms like Merge Sort and Quick Sort primarily in terms of efficiency. Selection Sort is less efficient for large datasets but is easier to understand and implement.
Question 3.
What is the main advantage of Selection Sort ?
The main advantage of Selection Sort is its simplicity. It’s easy to understand and implement, making it suitable for educational purposes and small datasets.
Question 4.
What are the limitations of Selection Sort ?
The main limitation of Selection Sort is its quadratic time complexity, which makes it inefficient for larger datasets. It also doesn’t adapt to the existing order of elements in the list.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
