Day 20: Sorting
Hey CodingHumans today, we're discussing a simple sorting algorithm called Bubble Sort.
Sorting
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:
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 Style
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 Style
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.
Recommended: Please try your approach on your integrated development environment (IDE) first, before moving on to the solution.
Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.
HAPPY CODING 😁
Solution
( 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 .
