Problem 7: Stepwise Selection Sort!

Software Development
#1

Stepwise Selection Sort!

Problem Description

Given an integer array A of size N.

You need to sort the elements in increasing order using SelectionSort. Return a array containing the min value’s index position before every iteration.

NOTE:

  • Consider 0 based indexing while looking for min value in each step of selection sort.
  • There will be total N - 1 iterations in selection sort so the output array will contain N - 1 integers.

Problem Constraints

2 <= N <= 104

1 <= A[i] <= 106

All elements are distinct in array A.

Input Format

First and only argument is an integer array A.

Output Format

Return an integer array containing N - 1 integers denoting min value’s index position before every iteration.

Example Input

Input 1:

A = [6, 4, 3, 7, 2, 8]

Example Output

Output 1:

[4, 2, 2, 4, 4]

Example Explanation

Explanation 1:

Explanation : 6 4 3 7 2 8 : Index of 1st min - 4
After 1st Iteration : 2 4 3 7 6 8 : Index of 2nd min - 2
After 2nd Iteration : 2 3 4 7 6 8 : Index of 3rd min - 2
After 3rd Iteration : 2 3 4 7 6 8 : Index of 4th min - 4
After 4th iteration : 2 3 4 6 7 8 : Index of 5th min - 4
After 5th iteration. : 2 3 4 6 7 8.

#2

Solution 7: Stepwise Selection Sort


public class Solution {
    public ArrayList<Integer> solve(ArrayList<Integer> A) {
        ArrayList<Integer> minValIdx = new ArrayList<>();
        
        for (int idx = 0; idx < A.size() - 1; ++idx) {
            minValIdx.add( findMinIdx(A, idx) );
        }
        return minValIdx;
    }
    
    public int findMinIdx( ArrayList<Integer> A, int startIdx ) {
        int minIdx = 0;
        int minElem = Integer.MAX_VALUE;
        
        for (int idx = startIdx; idx < A.size(); ++idx ) {
            if ( A.get(idx) < minElem ) {
                minElem = A.get(idx);
                minIdx = idx;
            }
        }
        swap(A, startIdx, minIdx);
        return minIdx;
    }
    
    public void swap( ArrayList<Integer> A, int startIdx, int minIdx ) {
        A.set( startIdx, A.get(startIdx) + A.get(minIdx) );
        A.set( minIdx, A.get(startIdx) - A.get(minIdx) );
        A.set( startIdx, A.get(startIdx) - A.get(minIdx) );
    }
}
#3
#4
#5