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

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

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

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