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
- Start with the first element as the minimum in the unsorted part.
- Iterate through the unsorted part to find the index of the minimum element.
- Swap the minimum element with the first element of the unsorted part.
- 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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment