Day 20: HackerRank 30 Days Of Code Solution | Sorting

This post explains the HackerRank 30 Days of Code problem Sorting step by step: the problem statement, input and output format, constraints, a sample test case and a working solution in Java that you can study and run.

Day 20: Sorting
Hey CodingHumans today, we're discussing a simple sorting algorithm called Bubble Sort.

Sorting is the act of ordering elements. The ability of a program to organize and retrieve data quickly and efficiently is incredibly important in software development. Learning how to effectively sort and retrieve the data you're working with enables you to write better, faster algorithms.

Bubble Sort

This is a very simple sorting algorithm. Because it's also very inefficient, Bubble Sort is not practical for real-world use and is generally only discussed in an academic context. The basic theory behind BubbleSort is that you take an array of integers and iterate through it; for each element at some index whose value is greater than the element at the index following it (i.e., index ), you must swap the two values. The act of swapping these values causes the larger, unsorted values to float to the back (like a bubble) of the data structure until they land in the correct location.

Aim
Consider the following version of Bubble Sort:

Sorting Solution

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 lasElement 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.

Input Format

The first line contains an integer,n , denoting the number of elements in array a .
The second line contains n space-separated integers describing the respective values of a0,a1,a2...an-1.

Constraints

2<=n<=600
1<=ai <=2 x 10^6, 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:
1.[3,2,1] =>[2,3,1]
2.[2,3,1] =>[2,1,3]

3.[2,1,3] =>[1,2,3]
At this point the array is sorted and we print the necessary 3
lines of output shown above.

Sorting Solution in 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]);

        }
    }

If you have any doubts regarding this problem or need the solution in other programming languages then leave a comment down below .

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice