0

Selection Sort Algorithm & K’th Largest Element in Array

Selection Sort Algorithm | K’th Largest Element in Array | Find kth smallest element in the array | Selection sort in data structure | Selection Sort Algorithm in data structure | Selection sort program | What is selection sort?

Selection sort is also known as IN-Place Sorting Algorithm.

Rearranging the elements in a meaningful order can be done using a sorting algorithm. A sorting algorithm is used to sort a List/Array of integers, characters, floating-point numbers, and other user-defined data structures.

✔️ Approach

In the Selection sort, We choose the largest element from an array and swap it with the last element of the array.

The next step is to swap the second largest element of an array with the second last element of the array & so on.

Every time we have an array divided into two parts, sorted and unsorted, we look for an element to be added at the end of the sorted part.


❓Why called the In-Place Sorting algorithm?

Because it does not require any extra space for sorting.

Selection Sort Algorithm | Sorting by selection | What is selection sort?


💻 First Find the max element from a given array

function findMax(A) {
    let ans = A[0];
    for (let i = 1; i < A.length; i++) {
        if (A[i] > ans) {
            ans = A[i];
        }
    }
    return ans;
}

findMax([5, 8, 1, 15, 7, 6, 2]) // output is 15.

Time Complexity of this way is O(n)


💻 Find 2nd max element from an array

Use the same above program with two For loops sequentially. First, find the first max element and then the second element. The Time Complexity of this way is also O(n).

💻 Find 3rd max element from an array

Use the same above program with three For loops sequentially. At First find 1st max, then 2nd & then 3rd. The Time Complexity of this way is still O(n).


❓Above solution approach, we can use till 3rd or 4th max element but If we have to find the 100th or 1000th or Kth max element then how?

Selection Sort

TC is – O(n^2) & SC – O(1)
Given Array = [5, 8, 1, 15, 7, 6, 2]

Length  = 7, first Index = 0 & Last Index  = 6

1. Find Max element from 0 to 6th index => 15 => Swap this with last element of array.

[5, 8, 1, 2, 7, 6, 15]; // 15 is now its sorted position.

2. Find Max element from 0 to 5th index => 8 => Swap with last element of remaining array 0 to 5th index.

[5, 6, 1, 2, 7, 8, 15]; // 8, 15 are now their sorted positions.

3. Find Max element from 0 to 4th index => 7 => Swap with last element of remaining array 0 to 4th index. 7 is already on 7th so swapping does not any impact.

[5, 6, 1, 2, 7, 8, 15]; // 7, 8, 15 are now their sorted positions.

4. Find Max element from 0 to 3th index => 6 => Swap it.

[5, 2, 1, 6, 7, 8, 15]; // 6, 7, 8, 15 are now their sorted positions.

5. Find max element in 0 to 2nd indices => 5

[1, 2, 5, 6, 7, 8, 15]; // 5, 6, 7, 8, 15 are now their sorted positions.

6.  Find max element in 0 to 1 indices => 2 > Already on its correct position.

[1, 2, 5, 6, 7, 8, 15]; // 2, 5, 6, 7, 8, 15 are now their sorted positions.

So array length was 7, 6 elements are sorted so last 7th element automatically will be on its correct position.


function selectionSort(A) {
    let n = A.length;
    for (let i = n - 1; i > 0; i--) {
        let maxIndex = 0; // Initially Consider 0th index as Max element Index.
        for (let j = 1; j <= i; j++) { // start from 1.
            if (A[j] > A[maxIndex]) {
                maxIndex = j;
            }
        }
        [A[i], A[maxIndex]] = [A[maxIndex], A[i]]; // swap with last ith element
    }
    return A;
}

 Outer For Loop is running from the last index to the first index. The purpose of this for loop is to swap the Max element to the Last element.

Inner For loop is running from the First index to the Last Unsorted index. The purpose of this for loop is to find the Max element.

Now find kth largest element with same above selection sort

function findKthLargest(A, k) {
    let n = A.length;
    for (let i = n - 1; i > 0; i--) {
        let maxIndex = 0;
        for (let j = 1; j <= i; j++) {
            if (A[j] > A[maxIndex]) {
                maxIndex = j;
            }
        }
        [A[i], A[maxIndex]] = [A[maxIndex], A[i]]; // swap
    }
    return A[n - k]; // Larger elements are in Right side that's why did (n-k)
}

Find kth smallest element with same above selection sort

function findKthSmallest(A, k) {
    let n = A.length;
    for (let i = n - 1; i > 0; i--) {
        let maxIndex = 0;
        for (let j = 1; j <= i; j++) {
            if (A[j] > A[maxIndex]) {
                maxIndex = j;
            }
        }
        [A[i], A[maxIndex]] = [A[maxIndex], A[i]]; // swap
    }
    return A[k - 1];
}

findKthSmallest([8, 16, 80, 55, 32, 8, 38, 40, 65, 18, 15, 45, 50, 38, 54, 52, 23, 74, 81, 42, 28, 16, 66, 35, 91, 36, 44, 9, 85, 58, 59, 49, 75, 20, 87, 60, 17, 11, 39, 62, 20, 17, 46, 26, 81, 92], 9)) // find 9th smallest

output = 17

findKthLargest([8, 16, 80, 55, 32, 8, 38, 40, 65, 18, 15, 45, 50, 38, 54, 52, 23, 74, 81, 42, 28, 16, 66, 35, 91, 36, 44, 9, 85, 58, 59, 49, 75, 20, 87, 60, 17, 11, 39, 62, 20, 17, 46, 26, 81, 92], 12) // Fidn 12th max element

output = 62

Time & Space Complexity of Selection sort

This sorting algorithm uses two For Loops so Time Complexity is O(n^2) & no extra space is required here. So Space complexity is O(1).

Quick Sort Algorithm with example | Step-by-Step Guide

 

Selection Sort Algorithm

Selection Sort & K’th Largest Element

0

Leave a Reply

Your email address will not be published.