Selection Sort

The Selection Sort algorithm is a simple comparison-based sorting algorithm that divides the input array into two parts: the sorted part and the unsorted part. The algorithm repeatedly selects the minimum element from the unsorted part and swaps it with the element at the beginning of the sorted part. This process is repeated until the entire array is sorted. Selection Sort is not very efficient for large datasets but is easy to understand and implement.

Problem Statement

Given an array of integers, we need to sort the array in ascending order using the Selection Sort algorithm. The goal is to rearrange the elements of the array such that they are in non-decreasing order.

Example

Let's take an example to understand how the Selection Sort algorithm works:

Input Array: [8, 2, 3, 8, 1, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52]

Step 1

Array: [8, 2, 3, 8, 1, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52] Minimum element in unsorted part: 1 (at index 4) Swap elements 8 and 1. Array after swap: [1, 2, 3, 8, 8, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52]

Step 2

Array: [1, 2, 3, 8, 8, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52] Minimum element in unsorted part: 2 (at index 1) No swap needed, as the minimum element is already at the beginning of the unsorted part.

Step 3

Array: [1, 2, 3, 8, 8, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52] Minimum element in unsorted part: 3 (at index 5) No swap needed, as the minimum element is already at the beginning of the unsorted part.

Step 4

Array: [1, 2, 3, 8, 8, 3, 73, 121, 54, 23, 84, 13, 67, 23, 52] Minimum element in unsorted part: 3 (at index 5) Swap elements 8 and 3. Array after swap: [1, 2, 3, 3, 8, 8, 73, 121, 54, 23, 84, 13, 67, 23, 52]

... (continue this process for each step)

Step 15

Array: [1, 2, 3, 3, 8, 8, 13, 23, 23, 52, 54, 67, 73, 84, 121] Minimum element in unsorted part: 13 (at index 11) Swap elements 84 and 13. Array after swap: [1, 2, 3, 3, 8, 8, 13, 23, 23, 52, 54, 67, 73, 84, 121]

Step 16

Array: [1, 2, 3, 3, 8, 8, 13, 23, 23, 52, 54, 67, 73, 84, 121] Sorting is complete. The entire array is now sorted.

Final Sorted Array

[1, 2, 3, 3, 8, 8, 13, 23, 23, 52, 54, 67, 73, 84, 121]

Each step involves finding the minimum element in the unsorted part of the array and swapping it with the appropriate element in the sorted part. This process is repeated until the entire array is sorted in ascending order.

Idea to Solve

The basic idea of the Selection Sort algorithm is to repeatedly find the minimum element from the unsorted part of the array and swap it with the first element of the unsorted part. This effectively builds the sorted part of the array from left to right.

Algorithm

1. Start with the first element as the minimum in the unsorted part.
2. Iterate through the unsorted part to find the index of the minimum element.
3. Swap the minimum element with the first element of the unsorted part.
4. Repeat steps 1-3 for each iteration, gradually expanding the sorted part.

Pseudocode

function selectionSort(arr):
    n = length of arr
    for i from 0 to n-1:
        minIndex = i
        for j from i+1 to n-1:
            if arr[j] < arr[minIndex]:
                minIndex = j
        swap arr[i] and arr[minIndex]

Program List

1) Selection sort in java 2) Selection sort in c++ 3) Selection sort in c 4) Selection sort in golang 5) Selection sort in c# 6) Selection sort in vb.net 7) Selection sort in php 8) Selection sort in node js 9) Selection sort in typescript 10) Selection sort in python 11) Selection sort in ruby 12) Selection sort in scala 13) Selection sort in swift 14) Selection sort in kotlin

Time Complexity

Selection Sort consists of two nested loops. The outer loop runs n times, and for each iteration of the outer loop, the inner loop runs (n - i) times, where i is the current iteration of the outer loop. This results in a time complexity of O(n^2), where n is the number of elements in the array. It's worth noting that Selection Sort has a consistent performance regardless of whether the input is partially sorted or not, which makes it less suitable for larger datasets.