Home > Article > Backend Development > Selection Sort Algorithm
The Selection Sort algorithm divides the array into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, and the unsorted part contains all the elements. The algorithm works by finding the smallest (or largest, depending on sorting order) element from the unsorted part and swapping it with the first element of the unsorted part. This process continues until the entire array is sorted.
#Suppose we have the following array: arr = [64, 25, 12, 22, 11]
Array after the first pass: [11, 25, 12, 22, 64]
Array after the second pass: [11, 12, 25, 22, 64]
Array after the third pass: [11, 12, 22, 25, 64]
Final sorted array: [11, 12, 22, 25, 64]
def selection_sort(arr): # Traverse through all array elements for i in range(len(arr)): # Find the minimum element in the remaining unsorted part 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 the unsorted part arr[i], arr[min_index] = arr[min_index], arr[i] # Example usage arr = [64, 25, 12, 22, 11] selection_sort(arr) print("Sorted array:", arr)
Sorted array: [11, 12, 22, 25, 64]
Best Case: O(n²)
Average Case: O(n²)
Worst Case: O(n²)
Even though Selection Sort performs well for small datasets, it is not ideal for larger arrays because its time complexity is O(n²). However, it is easy to implement and can be useful in cases where memory is a concern, as Selection Sort is in-place (requires no additional memory).
Advantages:
Simple to understand and implement.
Performs well on small lists.
Doesn't require extra memory since it sorts the array in place.
Disadvantages:
Inefficient for large datasets due to its O(n²) time complexity.
It isn't a stable sorting algorithm, meaning equal elements might not preserve their order relative to each other.
The above is the detailed content of Selection Sort Algorithm. For more information, please follow other related articles on the PHP Chinese website!