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
Question
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
Solution
Here is a Python solution for the problem:
def bubbleSort(arr):
n = len(arr)
swap_count = 0
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
swap_count += 1
return swap_count
T = int(input().strip())
for _ in range(T):
N = int(input().strip())
arr = list(map(int, input().strip().split()))
print(bubbleSort(arr))
This program works by defining a function bubbleSort that sorts an array using the Bubble Sort algorithm and counts the number of swaps made. The function iterates over each element in the array, and for each element, it iterates over the rest of the array. If it finds an element that is larger than the next one, it swaps them and increments the swap count.
The main part of
Similar Questions
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 size N, implement Bubble Sort.Input FormatThe first line of input contains an integer N - the size of an array. The second line contains the elements of the array.Output FormatFor each iteration of Bubble Sort, print the array elements.Constraints1 <= N <= 201 <= A[i] <= 103ExampleInput65 8 10 15 3 6Output5 8 10 3 6 155 8 3 6 10 155 3 6 8 10 153 5 6 8 10 153 5 6 8 10 15
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
If the array had been sorted in descending order initially, how many swaps would the Bubble Sort perform?
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.