Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the list and putting it at the beginning. Selection Sort is easy to understand and implement, but it is not very efficient for large lists. In this article, we will discuss how to implement Selection Sort in Python, its time and space complexities, and provide examples with detailed explanations.
How Selection Sort Works
The algorithm starts at the beginning of the list and searches for the smallest element. It then swaps the smallest element with the first element. The algorithm then moves to the next position and searches for the smallest element in the remaining unsorted part of the list. It then swaps the smallest element found with the element at the current position. This process continues until the entire list is sorted.
The steps involved in implementing Selection Sort can be summarized as follows:
- Find the smallest element in the unsorted part of the list
- Swap the smallest element found with the first element
- Move to the next position and search for the smallest element in the remaining unsorted part of the list
- Swap the smallest element found with the element at the current position
- Repeat steps 2-4 until the entire list is sorted
Time Complexity
The time complexity of Selection Sort is O(n^2), where n is the number of elements in the list. This means that for a list of n elements, Selection Sort will perform n^2 operations. In the worst-case scenario, when the list is in reverse order, Selection Sort will perform (n^2 – n) / 2 swaps. Although Selection Sort is easy to understand and implement, it is not very efficient for large lists, making it unsuitable for real-world applications.
Space Complexity
The space complexity of Selection Sort is O(1), which means that the amount of memory used by the algorithm is constant and does not depend on the size of the list. Selection Sort works by swapping elements, so it does not require any additional memory to store temporary variables or data structures.
Python Code Examples
Let’s take a look at some Python code examples for implementing Selection Sort:
Example 1: Sorting a List of Integers
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("Sorted array:", arr)
In this example, we define a function called selection_sort that takes a list of integers as input. The function then uses two nested loops to iterate over the list and find the smallest element in the unsorted part of the list. The outer loop iterates over each element in the list, while the inner loop searches for the smallest element in the remaining unsorted part of the list. If the current element is larger than the next element, they are swapped. The range function is used to determine the range of values that the loop should iterate over.
We then call the selection_sort function and pass it a list of integers. The function sorts the list in place, meaning that it modifies the original list rather than creating a new one. Finally, we print the sorted list using the print function.
The output of the code above will be:
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Example 2: Sorting a List of Strings
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
arr = ["apple", "banana", "cherry", "date", "fig", "grape"]
selection_sort(arr)
print("Sorted array:", arr)
This example is similar to the previous one, except that we are sorting a list of strings instead of integers. The selection_sort function works the same way, by comparing the elements using the < operator. Since strings are compared lexicographically, the function will sort the strings in alphabetical order.
The output of the code above will be:
Sorted array: ['apple', 'banana', 'cherry', 'date', 'fig', 'grape']
Example 3: Sorting a List of Tuples
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j][1] < arr[min_index][1]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
arr = [("Alice", 25), ("Bob", 19), ("Charlie", 32), ("David", 21)]
selection_sort(arr)
print("Sorted array:", arr)
In this example, we are sorting a list of tuples, where each tuple contains a name and an age. The selection_sort function works the same way as before, except that it compares the second element of each tuple instead of the entire tuple. This is because the second element is an integer, which can be compared using the < operator.
The output of the code above will be:
Sorted array: [('Bob', 19), ('David', 21), ('Alice', 25), ('Charlie', 32)]
Conclusion
Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the list and putting it at the beginning. Although Selection Sort is easy to understand and implement, it is not very efficient for large lists, making it unsuitable for real-world applications. The time complexity of Selection Sort is O(n^2), while its space complexity is O(1). Python provides an easy and concise way to implement Selection Sort using loops and swapping elements.
