The Bubble Sort compares every number against every other number, sometimes multiple times, to move numbers around in the array. The entire array is always in a state of change, which adds to the inefficiency of that algorithm.
The Selection Sort works differently -- it splits the array into two logical parts: sorted and unsorted. At every step, the lowest number in the unsorted part of the array is selected and added to the end of the sorted part of the array. This selection step gives this algorithm its name.
Selection Sort Animation
Here's what these actions look like with a small dataset:
Credit: Swfung8, CC BY-SA 3.0, via Wikimedia Commons
Selection Sort Big O Complexity
The Big O complexity of a selection sort is $`O(n^2)`$, where n is the number of elements in the list. This is because, in a worst-case scenario, for each element, the selection sort needs to determine the minimum or maximum element in the unsorted portion of the array. This requires nested loops, and the complexity therefore grows exponentially.
Selection Sort in Java
Of course, code is always telling, so here it is:
public static int[] selectionSort(int nums[]) {
// iterate over the length of the array (outer loop)
// everything at or below "i" will be considered sorted
// everything after "i" is unsorted
for (int i = 0; i < nums.length; i++) {
// set a default value for the index of the smallest value found
int minVal = i;
// Find the index of the smallest element in the unsorted array
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minVal]){
minVal = j;
}
// Swap the smallest element in the unsorted portion of the list
// with the first element in the unsorted portion of the list
int temp = nums[minVal];
nums[minVal] = nums[i];
nums[i] = temp;
// when you loop, you're effectively moving the "sorted"
// marker (in this case "i") up by one
}
}
return nums;
}
Note that you still have two nested for loops, but the similarities end there. The outer loop iterates over every item in nums. It acts as the dividing point between the sorted and unsorted portions of the array -- everything at that index or higher is unsorted, while everything at a lower index is sorted.
You start finding the lowest unsorted value by picking the first unsorted index, which will always be i. You then loop through the rest of the array to find the lowest value and store its index in minVal. Finally, you swap that item with nums[i], which will be the end of the sorted part of the list on the next iteration.
Selection Sort in Python
The Python example below demonstrates a selection_sort function. This function takes in a list nums as a parameter and sorts it using the selection sort. The selection sort iterates through the array, finds the smallest element in the unsorted part of the array, and swaps it with the first element of the unsorted part of the array. Every element at or below that point is now considered sorted. This process is repeated until the entire array is sorted.
def selection_sort(nums):
"""
This function performs the selection sort algorithm on a list.
:param nums: A list of comparable elements
:return: The sorted list in ascending order
"""
# Iterate through the array
for i in range(len(nums)):
# Find the minimum element in the unsorted part of the array
min_index = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[min_index]:
min_index = j # Update the minimum index
# Swap the found minimum element with the first element of the unsorted part
nums[i], nums[min_index] = nums[min_index], nums[i]
return nums # Ensure the function returns only after sorting is complete
# Example usage:
unsorted_list = [564, 323, 789, 63, 222, 1001, 24, 99]
sorted_list = selection_sort(unsorted_list)
print("Sorted array:", sorted_list)
Summary: Selection Sort
As with the Bubble Sort, the Big O complexity is $`O(n^2)`$ due to the existence of similarly nested for loops. However, the Selection Sort is more efficient because it only swaps values in the outer loop. While it is better, it's still only good for small data sets -- you can still improve your sorting with a different algorithm.
Selection Sort is a modest improvement over Bubble Sort. It splits the dataset into sorted and unsorted portions and then selects the next item to be moved to the end of the sorted portion. This algorithm still suffers from poor performance over larger datasets due to the nested loops used.