Algorithm
Problem Name: 30 days of code -
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:
Array is sorted in numSwaps swaps.
where numSwapsis 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.
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;
}
#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;
}
#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]);
}
}
#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])
}
#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]);
}
}
#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}`)
}
#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]))