Selection Sort Algorithm

Shubham Kharche — Wed, 18 Sep 2024 17:54:51 +0000

What is Selection Sort?

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.

Algorithm Steps

Start with the first element in the array and assume it is the smallest.
Compare this element with the other elements in the array.
If you find a smaller element, swap it with the first element.
Move to the next element in the array and repeat the process for the remaining unsorted elements.
Continue this process until the entire array is sorted.

#Suppose we have the following array:

arr = [64, 25, 12, 22, 11]

Pass 1:

The smallest element between index 0 and the rest of the array is 11.
We swap 64 with 11.

Array after the first pass: [11, 25, 12, 22, 64]

Pass 2:

Now, focus on the subarray starting from index 1. The smallest element between 25, 12, 22, 64 is 12.
We swap 25 with 12.

Array after the second pass: [11, 12, 25, 22, 64]

Pass 3:

The smallest element between 25, 22, 64 is 22.
We swap 25 with 22.

Array after the third pass: [11, 12, 22, 25, 64]

Pass 4:

The subarray now contains 25, 64. Since they are already in order, no swap is needed.

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]

Time Complexity of Selection Sort:

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 and Disadvantages

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.

DEV Community: Shubham Kharche