Today we are going to solve HackerRank Day 20 : Sorting 30 days of code solution 30 days of code solution in C, C++, Java, Python & Javascript.
Objective
Today, we’re discussing a simple sorting algorithm called Bubble Sort.
Consider the following version of Bubble Sort:
for (int i = 0; i < n; i++) {
// Track number of elements swapped during a single array traversal
int numberOfSwaps = 0;
for (int j = 0; j < n - 1; j++) {
// Swap adjacent elements if they are in decreasing order
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
numberOfSwaps++;
}
}
// If no elements were swapped during a traversal, array is sorted
if (numberOfSwaps == 0) {
break;
}
}
Task
Given an array, a, of size n distinct elements, sort the array in ascending order using the Bubble Sort algorithm above. Once sorted, print the following 3 lines:
Array is sorted in numSwaps swaps.
where numSwaps is the number of swaps that took place.First Element: firstElement
where firstElement is the first element in the sorted array.Last Element: lastElement
where lastElement is the last element in the sorted array.
Hint: To complete this challenge, you will need to add a variable that keeps a running tally of all swaps that occur during execution.
Example
a = [4, 3, 1, 2]
original a: 4 3 1 2
round 1 a: 3 1 2 4 swaps this round: 3
round 2 a: 1 2 3 4 swaps this round: 2
round 3 a: 1 2 3 4 swaps this round: 0
In the first round, the 4 is swapped at each of the 3 comparisons, ending in the last position. In the second round, the 3 is swapped at 2 of the 3 comparisons. Finally, in the third round, no swaps are made so the iterations stop. The output is the following:
Array is sorted in 5 swaps.
First Element: 1
Last Element: 4
Input Format
The first line contains an integer, n, the number of elements in array a.
The second line contains n space-separated integers that describe a[0], a[1], . . .a[n – 1].
Constraints
- 2 <= n <= 600
- 1 <= a[i] <= 2 x106, where 0 <= i < n
Output Format
Print the following three lines of output:
Array is sorted in numSwaps swaps.
where numSwaps is the number of swaps that took place.First Element: firstElement
where firstElement is the first element in the sorted array.Last Element: lastElement
where lastElement is the last element in the sorted array.
Sample Input 0
3
1 2 3
Sample Output 0
Array is sorted in 0 swaps.
First Element: 1
Last Element: 3
Explanation 0
The array is already sorted, so 0 swaps take place and we print the necessary 3 lines of output shown above.
Sample Input 1
3
3 2 1
Sample Output 1
Array is sorted in 3 swaps.
First Element: 1
Last Element: 3
Explanation 1
The array a = [3, 2, 1] is not sorted, so we perform the following 3 swaps. Each line shows a after each single element is swapped.
- [3, 2, 1] = [2, 3, 1]
- [2, 3, 1] = [2, 1, 3]
- [2, 1, 3] = [1 , 2, 3]
After 3 swaps, the array is sorted.
HackerRank Day 20 : Sorting 30 days of code solution
Sorting HackerRank Solution in C
//CODINGWITHNICK #include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> int main(){ int n; scanf("%d",&n); int *a = malloc(sizeof(int) * n); for(int a_i = 0; a_i < n; a_i++){ scanf("%d",&a[a_i]); } int total = 0; for (int i = 0; i < n; i++) { int s = 0; for (int j = 0; j < n-1; j++) { if (a[j] > a[j+1]) { int t = a[j]; a[j] = a[j+1]; a[j+1] = t; s++; total++; } } if (s == 0) break; } printf("Array is sorted in %d swaps.\n", total); printf("First Element: %d\n", a[0]); printf("Last Element: %d\n", a[n-1]); return 0; }
Sorting HackerRank Solution in C++
//Write your code here //CODINGWITHNICK using namespace std; int main(){ int n; cin >> n; vector<int> a(n); for(int a_i = 0;a_i < n;a_i++){ cin >> a[a_i]; } int sw = 0; for (int i = 0; i < n; i++) { int numberOfSwaps = 0; for (int j = 0; j < n - 1; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); numberOfSwaps++; } } sw += numberOfSwaps; if (numberOfSwaps == 0) { break; } } cout << "Array is sorted in " << sw << " swaps." << endl; cout << "First Element: " << a[0] << endl; cout << "Last Element: " << a[n-1] << endl; return 0; }
Sorting HackerRank Solution in Java
import java.io.*; import java.util.*; public class Solution { public static int bubbleSort(int[] a, int n){ int numSwaps = 0; for (int i = 0; i < n; i++) { int numberOfSwaps = 0; for (int j = 0; j < n - 1; j++) { if (a[j] > a[j + 1]) { //swap(a[j], a[j + 1]); int temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; numberOfSwaps++; numSwaps++; } } if (numberOfSwaps == 0) { break; } } return numSwaps; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = sc.nextInt(); sc.close(); int numSwaps = bubbleSort(a, n); System.out.println("Array is sorted in " + numSwaps + " swaps."); System.out.println("First Element: " + a[0]); System.out.println("Last Element: " + a[n-1]); } }
Sorting HackerRank Solution in Python 3
#Write your code here #CODINGWITHNICK #!/bin/python3 import sys n = int(input().strip()) a = list(map(int, input().strip().split(' '))) nofswap = 0 for i in range(0,n-1): for i in range(0,n-1): if a[i]>a[i+1]: a[i],a[i+1] = a[i+1],a[i] nofswap +=1 print("Array is sorted in", nofswap, "swaps.") print("First Element:",a[0]) print("Last Element:",a[-1])
Sorting HackerRank Solution in JavaScript
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
/////////////// ignore above this line ////////////////////
function main() {
var n = parseInt(readLine());
a = readLine().split(' ');
a = a.map(Number);
var totalNum = 0
for (var i = 0; i < a.length; i++) {
var numberOfSwaps = 0
for (var j = 0; j < a.length -1; j++) {
if (a[j] > a[j + 1]) {
var temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
numberOfSwaps++;
}
}
totalNum += numberOfSwaps;
if (numberOfSwaps == 0) {
break;
}
}
console.log('Array is sorted in '+totalNum+ ' swaps.')
console.log('First Element: '+a[0]);
console.log('Last Element: '+a[a.length-1]);
}
NEXT : HackerRank Day 21 : Generics 30 days of code solution
30 Days of Code HackerRank Solutions List – Day 0 to Day 29
Read More –
- How To Create Responsive Image Gallery Using Html & Css
- Create a Quiz App using HTML CSS & JavaScript
- Product Landing Page Using Html Css Bootstrap
- Home Page With Image Gallery Website Using Html Css Js Bootstrap4
- How create an Complete Responsive Ecommerce Website Using Html Css Js & Bootstrap