Selection Sort
Selection sort is one of the sorting algorithms that works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning of the unsorted region of the array.

You are given an unsorted array consisting of N non-negative integers. Your task is to sort the array in non-decreasing order using the Selection Sort algorithm.

For Example:

Selection Sort implementation for the given array: {29,72,98,13,87,66,52,51,36} is shown below :-

Input Format:

The first line of input contains an integer 'T' representing the number of test cases. Then the test case follows. The first line of each test case contains integer 'N' denoting the size of the array. The second line of each test case contains 'N' single space-separated integers representing the array elements.

Output Format:

The only line of output of each test case should contain the given array sorted in non-decreasing order.

Note:

You do not need to print anything, and it has already been taken care of. Just implement the given function. Also, you need to update the given array in place only.

Constraints:

1

Question

Selection Sort

Selection sort is one of the sorting algorithms that works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning of the unsorted region of the array.

You are given an unsorted array consisting of N non-negative integers. Your task is to sort the array in non-decreasing order using the Selection Sort algorithm.

For Example:

Selection Sort implementation for the given array:  {29,72,98,13,87,66,52,51,36} is shown below :-

Alt text

Input Format:

The first line of input contains an integer 'T' representing the number of test cases. Then the test case follows.

The first line of each test case contains integer 'N' denoting the size of the array.

The second line of each test case contains 'N' single space-separated integers representing the array elements.

Output Format:

The only line of output of each test case should contain the given array sorted in non-decreasing order.

Note:

You do not need to print anything, and it has already been taken care of. Just implement the given function. Also, you need to update the given array in place only.

Constraints:

1 <= T <= 100
1 <= N <= 100
1 <= Arr[i] <= 1000

Where 'T' represents the number of test cases, 'N' represents the size of the array, and 'Arr[i]' represents the elements of the array.
Time Limit: 1 sec

Accepted Answer

Selection Sort Approach

Selection sort is a standard sorting algorithm that uses nested loops to find all the minimum elements in the array in each iteration and swap them with the starting element of the unsorted region of the array.

Steps :

Use a minValue variable to find the index of the minimum element of the array.
Use a loop to iterate over all the elements of the array.
Use a nested loop to find the minimum element of the array.
Swap the minValue index element with the starting element of the unsorted region of the array.
After the iterations are finished, the array becomes sorted in place.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra memory.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the length of the input array.

As we are using two nested loops and each one of them takes O(N) time.