mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 13:33:11 +08:00
RONGALI MOHAN KRISHNA 2400033266andChristian Clauss
1440e2f5b2
Added Time Complexity O(n^2) and Space Complexity O(1) documentation to the selection_sort function docstring, improving code documentation for beginners as requested in issue #13948. Co-authored-by: Christian Clauss <cclauss@me.com>
85 lines
2.4 KiB
Python
85 lines
2.4 KiB
Python
from collections.abc import MutableSequence
|
|
from typing import Any, Protocol
|
|
|
|
|
|
class Comparable(Protocol):
|
|
def __lt__(self, other: Any, /) -> bool: ...
|
|
|
|
|
|
def selection_sort[T: Comparable](collection: MutableSequence[T]) -> MutableSequence[T]:
|
|
"""
|
|
Sorts a list in ascending order using the selection sort algorithm.
|
|
|
|
Selection sort divides the input list into a sorted and unsorted region.
|
|
It repeatedly finds the minimum element from the unsorted region and
|
|
places it at the end of the sorted region.
|
|
|
|
Time Complexity: O(n²) in all cases
|
|
Space Complexity: O(1)
|
|
|
|
:param collection: A mutable sequence of comparable items to be sorted.
|
|
:return: The same sequence sorted in ascending order.
|
|
|
|
|
|
Time Complexity: O(n^2) - Due to the nested loops, where n is the length
|
|
of the collection. The outer loop runs n-1 times, and the inner loop
|
|
runs n-i-1 times for each iteration.
|
|
Space Complexity: O(1) - Only a constant amount of extra space is used
|
|
for variables (length, i, min_index, k).
|
|
Examples:
|
|
>>> selection_sort([0, 5, 3, 2, 2])
|
|
[0, 2, 2, 3, 5]
|
|
|
|
>>> selection_sort([])
|
|
[]
|
|
|
|
>>> selection_sort([-2, -5, -45])
|
|
[-45, -5, -2]
|
|
|
|
>>> selection_sort([1])
|
|
[1]
|
|
|
|
>>> selection_sort([5, 4, 3, 2, 1])
|
|
[1, 2, 3, 4, 5]
|
|
|
|
>>> selection_sort([1, 2, 3, 4, 5])
|
|
[1, 2, 3, 4, 5]
|
|
|
|
>>> selection_sort([3, 3, 3, 3])
|
|
[3, 3, 3, 3]
|
|
|
|
>>> selection_sort([0])
|
|
[0]
|
|
|
|
>>> selection_sort([2, -3, 0, 5, -1])
|
|
[-3, -1, 0, 2, 5]
|
|
|
|
>>> selection_sort([0, 5, 3, 2, 2]) == sorted([0, 5, 3, 2, 2])
|
|
True
|
|
|
|
>>> selection_sort([-2, -5, -45]) == sorted([-2, -5, -45])
|
|
True
|
|
|
|
>>> selection_sort(["d", "a", "c", "b"])
|
|
['a', 'b', 'c', 'd']
|
|
|
|
>>> selection_sort([3.2, 1.1, 2.4, 0.5])
|
|
[0.5, 1.1, 2.4, 3.2]
|
|
"""
|
|
length = len(collection)
|
|
for i in range(length - 1):
|
|
min_index = i
|
|
for k in range(i + 1, length):
|
|
if collection[k] < collection[min_index]:
|
|
min_index = k
|
|
if min_index != i:
|
|
collection[i], collection[min_index] = collection[min_index], collection[i]
|
|
return collection
|
|
|
|
|
|
if __name__ == "__main__":
|
|
user_input = input("Enter numbers separated by a comma:\n").strip()
|
|
unsorted = [int(item) for item in user_input.split(",")]
|
|
sorted_list = selection_sort(unsorted)
|
|
print("Sorted List:", sorted_list)
|