# Day 20: Sorting | 30 Days Of Code | HackerRank Solution

Hello coders, today we are going to solve Day 20: Sorting HackerRank Solution in C++, Java and Python.

## 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;
}
}``````

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:

1. `Array is sorted in numSwaps swaps.`
where numSwaps is the number of swaps that took place.
2. `First Element: firstElement`
where firstElement is the first element in the sorted array.
3. `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:

1. `Array is sorted in numSwaps swaps.`
where numSwaps is the number of swaps that took place.
2. `First Element: firstElement`
where firstElement is the first element in the sorted array.
3. `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.

1. [3, 2, 1] = [2, 3, 1]
2. [2, 3, 1] = [2, 1, 3]
3. [2, 1, 3] = [1 , 2, 3]

After 3 swaps, the array is sorted.

## Solution – Day 20: Sorting

### C++

```#include <bits/stdc++.h>

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 swap=0;
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
int temp = a[j];
a[j]=a[j+1];
a[j+1]=temp;
swap++;
}
}
}
cout<<"Array is sorted in "<<swap<<" swaps."<<endl;
cout<<"First Element: "<<a[0]<<endl;
cout<<"Last Element: "<<a[n-1]<<endl;
return 0;
}```

### Java

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i]=in.nextInt();
}
int temp=0;
int swapCount=0;
for(int i=0;i<n;i++){
for(int j=0;j<n-1;j++){
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
swapCount++;
}

}
if(swapCount==0){
break;
}
}
System.out.println("Array is sorted in "+swapCount+" swaps.");
System.out.println("First Element: "+arr[0]);
System.out.println("Last Element: "+arr[arr.length-1]);

}
}```

### Python

```n = int(input())
arr = [int(x) for x in input().split(" ")]

num_swaps = 0

for i in range(n):
for j in range(n - 1):
if arr[j] > arr[j + 1]:
tmp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = tmp
num_swaps += 1

if num_swaps == 0:
break

print("Array is sorted in " + str(num_swaps) + " swaps.")
print("First Element: " + str(arr[0]))
print("Last Element: " + str(arr[len(arr) - 1]))
```

Disclaimer: The above Problem (Day 20: Sorting) is generated by Hacker Rank but the Solution in Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.