Algorithm

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

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


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 &

#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 &

#3 Code Example with C# Programming

Code - C# Programming


using System;

class Solution
{
static void Main(String[] args)
{
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 &

#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 &

#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 &

#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();
});

return inputString[currentLine++];
}

function main() {

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 &

#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 &

#8 Code Example with PHP Programming

Code - PHP Programming




Copy The Code &