Last Updated: 21 Sep, 2016
Selection Sort
Easy
Asked in company
Sort the given unsorted array 'arr' of size 'N' in non-decreasing order using the selection sort algorithm.
Note:
Change in the input array/list itself.
Example:
Input:
N = 5
arr = {8, 6, 2, 5, 1}
Output:
1 2 5 6 8
Explanation:
Input format :
First line contains an integer 'N' representing the size of the array/list.
Second line contains 'N' single space separated integers representing the elements in the array/list.
Output format :
The output contains the integers of the sorted array, separated by a single space.
Note:-
You don’t need to print anything. Just implement the given function.
Approaches
Approach:
The selection sort algorithm works by repeatedly selecting the smallest element from the unsorted part of the array and moving it to the beginning of the unsorted part. This process is done iteratively until the entire array is sorted.
Here is the step-by-step approach for selection sort:
- Start with the entire array as the unsorted part.
- Find the minimum element in the unsorted part.
- Swap the found minimum element with the first element of the unsorted part.
- Move the boundary between the sorted and unsorted parts one element to the right. The element at the boundary is now considered part of the sorted subarray.
- Repeat steps 2 to 4 until the entire array is sorted.
Algorithm:
function selectionSort(arr):
- n = length(arr)
- for i from 0 to n-1:
- minIndex = i
- for j from i+1 to n:
- if arr[j] < arr[minIndex]:
- minIndex = j
- swap arr[i] with arr[minIndex]
Similar problems