Selection Sorting Algorithm

Last updated on December 16th, 2024 at 01:56 am

This article thoroughly explores the Selection Sorting Algorithm, compares it with other sorting methods, and provides practical examples in Python and Java.

1. What is Selection Sorting Algorithm?

The Selection Sorting Algorithm is an in-place comparison-based sorting algorithm that divides the array into two parts: the sorted portion and the unsorted portion. The algorithm iterates through the array, selecting the smallest or largest element from the unsorted portion and swapping it with the first element of the unsorted portion. This process continues until the entire array is sorted.

1.1 Example for Selection Sort

Sort the given elements (29, 64, 73, 34 and 20) by using selection sort.

We have
29, 64, 73, 34, 20
After the first pass, we get
20, 64, 73, 34, 29
After the second pass, we get
20, 29, 73, 34, 64
After the third pass, we get
20, 29, 34, 73, 64
After the fourth pass, we get
20, 29, 34, 64, 73
After the fifth pass, we get
20, 29, 34, 64, 73

The sorted list is 20, 29, 34, 64, 73.

2. Selection Sort Pseudocode

Here is a step-by-step pseudocode for the Selection Sorting Algorithm:

1. Initialize the array and its length.
2. Iterate through the array from the first element to the second last element.
3. For each iteration, assume the current element as the smallest or largest element.
4. Iterate through the unsorted portion of the array to find the smallest or largest element.
5. If a smaller or larger element is found, update the smallest or largest element index.
6. Swap the smallest or largest element with the current element.
7. Repeat steps 3-6 until the entire array is sorted.

procedure selectionSort(list, n)
    for i = 0 to n-1
        minIndex = i
        for j = i+1 to n
            if list[j] < list[minIndex]
                minIndex = j
        end if
    end for
    swap list[i] and list[minIndex]
end procedure

3. Insertion Sort vs Selection Sort

Both Insertion Sort and Selection Sort are simple sorting algorithms used for small datasets.

However, Insertion Sort is more efficient than Selection Sort for nearly sorted arrays, while Selection Sort is more efficient for arrays with a large number of duplicate elements.

4. Python Program for Selection Sort

Simple Python program for implementing the Selection Sorting Algorithm:

def selection_sort(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example
numbers = [64, 25, 12, 22, 11]
selection_sort(numbers)
print("Sorted array:", numbers)

5. Selection Sort Program in Java

Implementing Selection Sort Program in Java:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {64, 25, 12, 22, 11};
        selectionSort(numbers);
        System.out.println("Sorted array: " + Arrays.toString(numbers));
    }
}

6. Advantages of Selection Sort

1. Simple implementation.
2. Doesn’t require extra space other than the array being sorted.
3. Stable sorting algorithm

7. Disadvantages of Selection Sort

1. Inefficient for large lists. Its complexity is O(n^2), where n is the number of elements.
2. Not adaptive. The time complexity remains the same even if the list is partially sorted.
3. Not suitable for real-time data

8. Time and Space Complexity of Selection Sort

FAQs