Implement Selection Sort and print the index which gets swapped at each step.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines. The first line of each test case contains N - the size of the array. The next line contains N integers - elements of the array.Output FormatFor each test case, print the index which gets swapped at each step, separated by space. Separate the output of different tests by a new line.Constraints1 <= T <= 1002 <= N <= 100-1000 <= ar[i] <= 1000ExampleInput68176 -272 -272 -45 269 -327 -945 1762-274 1617274 204 -161 481 -606 -767 -3512154 -10945 3 1 5440 10 20 40Output4 0 4 3 1 2 113 0 1 2 2 100 0 10 0 0
Question
Implement Selection Sort and print the index which gets swapped at each step.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines. The first line of each test case contains N - the size of the array. The next line contains N integers - elements of the array.Output FormatFor each test case, print the index which gets swapped at each step, separated by space. Separate the output of different tests by a new line.Constraints1 <= T <= 1002 <= N <= 100-1000 <= ar[i] <= 1000ExampleInput68176 -272 -272 -45 269 -327 -945 1762-274 1617274 204 -161 481 -606 -767 -3512154 -10945 3 1 5440 10 20 40Output4 0 4 3 1 2 113 0 1 2 2 100 0 10 0 0
Solution 1
This problem is asking to implement the Selection Sort algorithm on a given array and print the indices that get swapped at each step.
Here is a Python solution:
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(min_idx, end=' ')
print()
T = int(input())
for _ in range(T):
N = int(input())
arr = list(map(int, input().split()))
selection_sort(arr)
This solution works by iterating over the array and finding the minimum element from the unsorted part of the array. When the minimum element is found, it is swapped with the first unsorted element. This process is repeated until the entire array is sorted. The indices that get swapped are printed at each step.
For example, given the input:
1
6
8 1 7 6 -2 7 2 -2 7 -4 5 2 6 9 -3 2 7 -4 5 2 6 9 -3 2 7
The output will be:
4 0 4 3 1 2 1
This means that the elements at indices 4 and 0 were swapped, then the elements at indices 4 and 3 were swapped, and so on.
Solution 2
This problem is asking to implement the Selection Sort algorithm on a given array and print the indices that get swapped at each step.
Here is a Python solution:
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(min_idx, end=' ')
print()
T = int(input())
for _ in range(T):
N = int(input())
arr = list(map(int, input().split()))
selection_sort(arr)
This solution works by iterating over the array and finding the minimum element from the unsorted part of the array. The minimum element is then swapped with the first element of the unsorted part. This process is repeated until the entire array is sorted. The indices that get swapped are printed at each step.
For example, given the input:
1
6
8 1 7 6 -2 7 2 -2 7 2 -4 5 2 6 9 -1 7 6 -2 7 2 -2 7 2 -4 5 2 6 9 -1
The output would be:
1 3 4 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
This means that at each step, the element at the printed index was swapped with the first element of the unsorted part of the array.
Similar Questions
Implement Bubble Sort and print the total number of swaps involved to sort the array.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines. The first line of each test case contains N - the size of the array. The next line contains N integers - the elements of the array.Output FormatFor each test case, print the total number of swaps, separated by a new line.Constraints1 <= T <= 1001 <= N <= 100-1000 <= ar[i] <= 1000ExampleInput48176 -272 -272 -45 269 -327 -945 1762-274 1617274 204 -161 481 -606 -767 -3512154 -109Output150161
Implement Insertion Sort and print the index at which the ith element gets inserted [i>=1].Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines. The first line of each test case contains N - the size of the array. The next line contains N integers - elements of the array.Output FormatFor each test case, print the index at which the ith element gets inserted [i>=1], separated by space. Separate the output of different tests by a new line.Constraints1 <= T <= 1002 <= N <= 100-1000 <= ar[i] <= 1000ExampleInput48176 -272 -272 -45 269 -327 -945 1762-274 1617274 204 -161 481 -606 -767 -3512154 -109Output0 1 2 4 0 0 610 0 3 0 0 20
You are given an array of 0's and 1's. Sort the array in ascending order and print it.Note: Solve using two-pointer technique.Input FormatFirst line of input contains T - the number of test cases. Its followed by 2T lines, the first line contains N - the size of the array.The second line contains the elements of the array.Constraints1 <= T <= 10001 <= N <= 10000 <= A[i] <= 1Output FormatFor each test case, sort the array in ascending order and print it on a new line.Sample Input 0250 1 1 0 161 1 1 1 1 0Sample Output 00 0 1 1 10 1 1 1 1 1Explanation 0
Given an array of unique integer elements, print all the subsets of the given array in lexicographical order.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines, the first line contains N - the size of the array and the second line contains the elements of the array.Output FormatFor each test case, print the subsets of the given array in lexicographical order, separated by new line. Print an extra newline between output of different test cases.Constraints1 <= T <= 1001 <= N <= 100 <= A[i] <= 100ExampleInput335 15 3 257 96 43 15 8 23 Output3 3 5 3 5 15 3 15 5 5 15 15 57 57 96 96 3 3 8 3 8 15 3 8 15 23 3 8 23 3 15 3 15 23 3 23 8 8 15 8 15 23 8 23 15 15 23 23
You are given an array of integers. Sort them by frequency. See examples for more clarifications.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines, the first line contains N - the size of the array. The second line contains the elements of the array.Output FormatFor each test case, print the elements of the array sorted by frequency. In case 2 elements have the same frequency, print the smaller element first.Constraints1 <= T <= 1001 <= N <= 10000-1000 <= A[i] <= 1000ExampleInput264 -2 10 12 -8 48176 -272 -272 -45 269 -327 -945 176Output-8 -2 10 12 4 4-945 -327 -45 269 -272 -272 176 176
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.