Day 20 Sorting Hackerrank Solution in C++ & Java

Day 20 Sorting Hackerrank Solution in C++ and Java. Today, we're discussing a simple sorting algorithm called Bubble Sort. Check out the Tutorial tab for learning materials and an instructional video!

Consider the following version of Bubble Sort:

for (int i = 0; i < n; i++) {
    // Track the 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:

The 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, 4 the 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:

The array is sorted into 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 * 10^6, where 0 <= i < n.

Output Format

Print the following three lines of output:

The 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

1 2 3

Sample Output 0

The array is sorted in 0 swaps.

First Element: 1

Last Element: 3

Submit Your Solution Here: Click Here

Day 20 Sorting Hackerrank Solution in C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	/*Enter your code here. Read input from STDIN. Print output to STDOUT */
	int i, j, n, temp, count = 0, Swaps;
	cin >> n;
	int array[n];

	for (i = 0; i < n; i++)
	{
		cin >> array[i];
	}

	for (i = n - 1; i > 0; i--)
	{
		Swaps = 0;
		for (j = 0; j < i; j++)
		{
			if (array[j] > array[j + 1])
			{
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
				Swaps++;
				count++;
			}
		}

		if (Swaps == 0)
		{
			break;
		}
	}

	cout << "Array is sorted in " << count << " swaps.\n";
	cout << "First Element: " << array[0] << endl;
	cout << "Last Element: " << array[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]);
	}
}

Day 20 Sorting Explanation

This is a Simple case of sorting we have to sort the array and also count the total number of swaps and minimum and maximum elements of an array. This is an Advance Bubble Sort Example we also put one special condition. If the array is already sorted then no need to run an array or for saving time complexity if an array is already sorted then the running time complexity is O(n).

If an array is not sorted then we have to swap array elements and also count the swap and how many swaps are needed to sort an array. I strongly recommend checking some Sorting problems Like Bubble Sort, Selection Sort, and Insertion Sort for full clear doubts.