Welcome to this concise guide where we'll explore the Selection Sort algorithm, one of the simplest sorting algorithms you can implement in Python. Whether you're just starting out or looking to brush up on your skills, this post will help you understand how selection sort works, see it implemented in code, and grasp its time complexity.
What is Selection Sort?
Selection Sort is a straightforward comparison-based algorithm used for arranging elements of an array in a particular order (typically ascending). The key idea behind the algorithm is to repeatedly find the minimum element from the unsorted part of the list and move it to the beginning. This process continues, progressively reducing the portion of the array that needs sorting.
Python Implementation
Let's dive into the code:
def selection_sort(arr):
# Traverse through all array elements
for i in range(len(arr)):
# Find the minimum element in remaining unsorted array
min_index = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
# Swap the found minimum element with the first element of unsorted part
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# Example usage:
example_list = [64, 25, 12, 22, 11]
sorted_list = selection_sort(example_list)
print("Sorted array:", sorted_list)
Code Explanation:
-
Outer loop (
for i in range(len(arr))
): This iterates over each element of the list, marking it as the current position to fill with the smallest found value. -
Inner loop (
for j in range(i+1, len(arr))
): Searches for the minimum element from the unsorted section starting just afteri
. -
Finding Minimum: We track the index of the smallest element encountered so far using
min_index
. -
Swapping Elements: Once we find the minimum element in the remaining array, we swap it with the first unsorted element.
Example Demonstration
Let's see this algorithm in action:
-
Input:
[64, 25, 12, 22, 11]
-
Step-by-step Execution:
- First pass finds
11
as minimum and swaps with64
, resulting in[11, 25, 12, 22, 64]
. - Second pass finds
12
as the next minimum, resulting in[11, 12, 25, 22, 64]
. - Third pass results in
[11, 12, 22, 25, 64]
. - Fourth and fifth passes maintain order as no smaller elements are found.
- First pass finds
-
Output:
Sorted array: [11, 12, 22, 25, 64]
Time Complexity
The time complexity of selection sort is (O(n^2)), where (n) is the number of elements in the list. This is because for each element in the list, we perform a linear scan to find the minimum element.
Why O(n^2)?
- For each element (outer loop iteration), you might potentially need to check all other remaining elements (inner loop iteration). Hence, it performs (n \times (n-1) / 2) comparisons and swaps in total.
Conclusion
Selection Sort is a great starting point for understanding sorting algorithms. Its simplicity makes it easy to grasp the fundamentals of algorithm design and analysis. While not efficient for large datasets due to its quadratic time complexity, it's an excellent educational tool that reinforces basic programming concepts like loops and swapping elements.
Happy coding, and keep exploring more algorithms to enhance your problem-solving toolkit!
Comments
Post a Comment