Algorithm


Problem Name: 30 days of code - Day 20: Sorting

Problem Link: https://www.hackerrank.com/challenges/30-sorting/problem?isFullScreen=true

Objective
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 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:

  1. Array is sorted in numSwaps swaps.
    where numSwapsis 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.

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

 

 

Constraints

  • 2 <= n <= 600
  • 1 <= a[i] <= 2 * 106, where 0 <= i <= n

Sample Input 0

3
1 2 3

Sample Output 0

Array is sorted in 0 swaps.
First Element: 1
Last Element: 3

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include<stdio.h>
int main(){

	int i, j, n, temp, swap=0; //Variable Declaration
	scanf("%d", &n);
	int arr[n]; //Array Declaration

	for(i = 0; i  <  n; i++){
		scanf("%d", &arr[i]); //Input Elements Into Array 
	}
	for(i = 0; i  <  n; i++){ 
		for(j = i+1; j  <  n; j++){
			if(arr[i] > arr[j]){
				temp = arr[i];
				arr[i] = arr[j]; //Sorting The Elements Of The Array
				arr[j] = temp;
				swap++;	
			}
		}
	}
    //Output
	printf("Array is sorted in %d swaps.\n", swap);
	printf("First Element: %d\n", arr[0]);
	printf("Last Element: %d\n", arr[n-1]);
	return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <iostream&fgt;
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i  <  n; i++) {
        cin >> arr[i];
    }

    int numSwaps = 0;
    for (int i = 0; i  <  n; i++) {
        for (int j = 0; j  <  n - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                numSwaps++;
            }
        }
        if (numSwaps == 0) break;
    }

    printf("Array is sorted in %i swaps.\n", numSwaps);
    printf("First Element: %i\n", arr[0]);
    printf("Last Element: %i\n", arr[arr.size() - 1]);

    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with C# Programming

Code - C# Programming


using System;

class Solution
{
    static void Main(String[] args)
    {
        var a = int.Parse(Console.ReadLine());
        var ar = Console.ReadLine().Split(' ');
        var arr = Array.ConvertAll(ar, int.Parse);

        int numSwaps = 0;
        for (int i = 0; i  <  a; i++)
        {
            for (int j = 0; j  <  a - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    numSwaps++;
                }
            }

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

        Console.WriteLine("Array is sorted in " + numSwaps + " swaps.");
        Console.WriteLine("First Element: " + arr[0]);
        Console.WriteLine("Last Element: " + arr[arr.Length - 1]);
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Golang Programming

Code - Golang Programming


package main

import "fmt"

func swap(x int, y int) (int, int) {
	return y, x
}

func main() {
	var n, numSwaps int
	fmt.Scan(&n)

	a := make([]int, n)

	for k := range a {
		fmt.Scan(&a[k])
	}

	for i := 0; i  <  n-1; i++ {
		for j := 0; j  <  n-i-1; j++ {
			if a[j] > a[j+1] {
				a[j], a[j+1] = swap(a[j], a[j+1])
				numSwaps++
			}
		}
		if numSwaps == 0 {
			break
		}
	}

	fmt.Printf("Array is sorted in %d swaps.\n", numSwaps)
	fmt.Printf("First Element: %d\n", a[0])
	fmt.Printf("Last Element: %d\n", a[n-1])
}
Copy The Code & Try With Live Editor

#5 Code Example with Java Programming

Code - Java Programming


import java.util.Scanner;

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 numSwaps = 0;
        for (int i = 0; i  <  n; i++) {
            for (int j = 0; j  <  n - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    numSwaps++;
                }
            }

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

        System.out.println("Array is sorted in " + numSwaps + " swaps.");
        System.out.println("First Element: " + arr[0]);
        System.out.println("Last Element: " + arr[arr.length - 1]);
    }
}
Copy The Code & Try With Live Editor

#6 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}



function main() {
    const n = parseInt(readLine().trim(), 10);

    const a = readLine().replace(/\s+$/g, '').split(' ').map(aTemp => parseInt(aTemp, 10));

    let total = 0
    
    for(let i = 0;i < a.length;i++){
        let swap = 0
        for(let j = 0;j <  a.length-1;j++){
            if(a[j]>a[j+1]){
                
                let temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
                
                total++
                swap++;
                
            }
        }
        if(!swap)break;
    }
    let last = a.pop()
    console.log(`Array is sorted in ${total} swaps.`)
    console.log(`First Element: ${a[0]}`)
    console.log(`Last Element: ${last}`)
}
Copy The Code & Try With Live Editor

#7 Code Example with Python Programming

Code - Python Programming


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]))

Copy The Code & Try With Live Editor

#8 Code Example with PHP Programming

Code - PHP Programming



Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Day 19: Interfaces solution in Hackerrank - Hacerrank solution C, C++, C#, java, Js, Python & PHP in 30 days of code
Next
[Solved] Day 21: Generics solution in Hackerrank - Hacerrank solution C, C++, C#, java, Js, Python & PHP in 30 days of code