Bubble Sort<\/em>.<\/p>\n\n\n\nConsider the following version of Bubble Sort:<\/p>\n\n\n\n
for (int i = 0; i < n; i++) {\n \/\/ Track number of elements swapped during a single array traversal\n int numberOfSwaps = 0;\n \n for (int j = 0; j < n - 1; j++) {\n \/\/ Swap adjacent elements if they are in decreasing order\n if (a[j] > a[j + 1]) {\n swap(a[j], a[j + 1]);\n numberOfSwaps++;\n }\n }\n \n \/\/ If no elements were swapped during a traversal, array is sorted\n if (numberOfSwaps == 0) {\n break;\n }\n}<\/code><\/pre>\n\n\n\n<\/span>Task<\/strong><\/span><\/h2>\n\n\n\nGiven an array, a<\/strong><\/em>, of size n<\/em><\/strong> distinct elements, sort the array in ascending<\/em> order using the Bubble Sort<\/em> algorithm above. Once sorted, print the following 3<\/strong> lines:<\/p>\n\n\n\nArray is sorted in numSwaps swaps.<\/code>
where numSwaps<\/em><\/strong> is the number of swaps that took place.<\/li>First Element: firstElement<\/code>
where firstElement<\/strong><\/em> is the first<\/em> element in the sorted array.<\/li>Last Element: lastElement<\/code>
where lastElement<\/strong><\/em> is the last<\/em> element in the sorted array.<\/li><\/ol>\n\n\n\nHint:<\/strong> To complete this challenge, you will need to add a variable that keeps a running tally of all<\/em> swaps that occur during execution.<\/p>\n\n\n\nExample<\/strong>
a<\/em> = [4, 3, 1, 2]<\/strong><\/p>\n\n\n\noriginal a: 4 3 1 2\nround 1 a: 3 1 2 4 swaps this round: 3\nround 2 a: 1 2 3 4 swaps this round: 2\nround 3 a: 1 2 3 4 swaps this round: 0<\/code><\/pre>\n\n\n\nIn the first round, the 4<\/strong> is swapped at each of the 3<\/strong> comparisons, ending in the last position. In the second round, the 3<\/strong> is swapped at 2<\/strong> of the 3<\/strong> comparisons. Finally, in the third round, no swaps are made so the iterations stop. The output is the following:<\/p>\n\n\n\nArray is sorted in 5 swaps.\nFirst Element: 1\nLast Element: 4<\/code><\/pre>\n\n\n\n<\/span>Input Format<\/strong><\/span><\/h2>\n\n\n\nThe first line contains an integer, n<\/em><\/strong>, the number of elements in array a<\/em><\/strong>.
The second line contains n<\/em><\/strong> space-separated integers that describe a<\/em>[0], a<\/em>[1], . . .a<\/em>[n<\/em> – 1]<\/strong>.<\/p>\n\n\n\n<\/span>Constraints<\/strong><\/span><\/h2>\n\n\n\n- 2 <= n<\/em> <= 600<\/strong><\/li>
- 1 <= a<\/em>[i<\/em>] <= 2 x106<\/sup>, <\/strong>where 0 <= i<\/em> < n<\/em> <\/strong><\/li><\/ul>\n\n\n\n
<\/span>Output Format<\/strong><\/span><\/h2>\n\n\n\nPrint the following three lines of output:<\/p>\n\n\n\n
Array is sorted in numSwaps swaps.<\/code>
where numSwaps<\/strong><\/em> is the number of swaps that took place.<\/li>First Element: firstElement<\/code>
where firstElement<\/strong><\/em> is the first<\/em> element in the sorted array.<\/li>Last Element: lastElement<\/code>
where lastElement<\/strong><\/em> is the last<\/em> element in the sorted array.<\/li><\/ol>\n\n\n\nSample Input 0<\/strong><\/p>\n\n\n\n3\n1 2 3<\/code><\/pre>\n\n\n\nSample Output 0<\/strong><\/p>\n\n\n\nArray is sorted in 0 swaps.\nFirst Element: 1\nLast Element: 3<\/pre>\n\n\n\nExplanation 0<\/strong><\/p>\n\n\n\nThe array is already sorted, so 0<\/strong> swaps take place and we print the necessary 3<\/strong> lines of output shown above.<\/p>\n\n\n\nSample Input 1<\/strong><\/p>\n\n\n\n3\n3 2 1<\/code><\/pre>\n\n\n\nSample Output 1<\/strong><\/p>\n\n\n\nArray is sorted in 3 swaps.\nFirst Element: 1\nLast Element: 3<\/code><\/pre>\n\n\n\nExplanation 1<\/strong><\/p>\n\n\n\nThe array a<\/em> = [3, 2, 1]<\/strong> is not sorted<\/em>, so we perform the following 3<\/strong> swaps. Each line shows a<\/em><\/strong> after each single element is swapped.<\/p>\n\n\n\n- [3, 2, 1] = [2, 3, 1]<\/strong><\/li>
- [2, 3, 1] =<\/strong> [2, 1, 3]<\/strong><\/li>
- [2, 1, 3] = [1 , 2, 3]<\/strong><\/li><\/ol>\n\n\n\n
After 3<\/strong> swaps, the array is sorted.<\/p>\n\n\n\n<\/span>Solution – Day 20: Sorting<\/strong><\/span><\/h2>\n\n\n\n<\/span>C++<\/strong><\/span><\/h3>\n\n\n\n#include <bits\/stdc++.h>\n\n\nusing namespace std;\n\nint main() {\n int n;\n cin >> n;\n vector<int> a(n);\n for(int a_i = 0; a_i < n; a_i++){\n cin >> a[a_i];\n }\n \/\/ Write Your Code Here\n int swap=0;\n for(int i=0;i<n;i++){\n for(int j=0;j<n-i-1;j++){\n if(a[j]>a[j+1]){\n int temp = a[j];\n a[j]=a[j+1];\n a[j+1]=temp;\n swap++;\n }\n }\n }\n cout<<\"Array is sorted in \"<<swap<<\" swaps.\"<<endl;\n cout<<\"First Element: \"<<a[0]<<endl;\n cout<<\"Last Element: \"<<a[n-1]<<endl;\n return 0;\n}<\/pre>\n\n\n\n