PythonHaven | Selection Sort Algorithm

The solution below implements the Selection Sort algorithm, which is a simple comparison-based sorting algorithm.

def selection_sort(array):
	i = 0
	while i < len(array):
		smallest=i
		for j in range(i+1, len(array)):
			if array[smallest] > array[j]:
				smallest = j
		array[smallest], array[i]=array[i], array[smallest]
		i +=1
	return array
	
print("selection_sort::", selection_sort([8, 5, 2, 9, 5, 6, 3]))

Solution Overview

The function selection_sort takes an array as input.

Outer Loop (i)

The outer loop iterates over each element of the array, starting from the first element (index 0) and continuing until the second-to-last element.

The variable i represents the index of the current element being considered as the starting point for finding the smallest element.

Finding the Smallest Element

Within the outer loop, the variable smallest is initialized to i, indicating that the current element (array[i]) is assumed to be the smallest.

The inner loop iterates over the elements of the array starting from the element after the current element (i+1) and continuing until the end of the array.

For each element in the inner loop, if it is smaller than the current smallest element (array[smallest]), its index (j) is updated to become the new value of smallest.

Swapping Elements

After finding the index of the smallest element (smallest), a swap operation is performed between the current element (array[i]) and the smallest element (array[smallest]).

This effectively moves the smallest element found so far to its correct sorted position at index i.

After completing the inner loop, i is incremented by 1 to move to the next unsorted element in the array. Finally, after the outer loop completes all its iterations, the sorted array is returned.

Time Complexity

Here's an analysis of the worst-case, best-case and average-case time complexity of the selection sort algorithm.

Worst-Case Time Complexity

The worst-case time complexity of Selection Sort is O(n^2), where n is the number of elements in the array. This is because it repeatedly iterates over the entire array to find the smallest element, resulting in a quadratic number of comparisons and swaps.

Best-Case Time Complexity

The best-case time complexity is also O(n^2), as Selection Sort does not take advantage of any existing order in the array and always performs the same number of comparisons and swaps.

Average-Case Time Complexity

The average-case time complexity is O(n^2), making Selection Sort inefficient for large datasets.

Space Complexity

The space complexity of Selection Sort is O(1), as it operates in-place and does not require any additional space proportional to the size of the input array.

Example:

For example, given the input array [8, 5, 2, 9, 5, 6, 3], the Selection Sort algorithm would rearrange the elements in ascending order:

Pass 1: [2, 5, 8, 9, 5, 6, 3]
Pass 2: [2, 3, 8, 9, 5, 6, 5]
Pass 3: [2, 3, 5, 9, 8, 6, 5]
Pass 4: [2, 3, 5, 5, 8, 6, 9]
Pass 5: [2, 3, 5, 5, 6, 8, 9]
Pass 6: [2, 3, 5, 5, 6, 8, 9]

Here's a slight variation to the implementation of the selection sort algorithm. Have a look, you may even find it communicating to you better than the first approach.

def selection_sort_updated(array):
	currentIdx = 0
	while currentIdx < len(array) -1:
		smallestIdx = currentIdx
		for i in range(currentIdx + 1, len(array)):
			if array[smallestIdx] >array[i]:
				smallestIdx = i
		swap(currentIdx, smallestIdx, array)
		currentIdx +=1
	return array

def swap(i, j, array):
	array[i], array[j]=array[j],array[i]
	
print("selection_sort_updated::", selection_sort_updated([8, 5, 2, 9, 5, 6, 3]))

Selection Sort Algorithm