Day 20: Sorting HackerRank Solution

Day 20: Sorting HackerRank Solution
Source : https://www.hackerrank.com/challenges/30-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;    }}

Task
Given an array, , of size distinct elements, sort the array in ascending order using the Bubble Sort algorithm above. Once sorted, print the following lines:

1. Array is sorted in numSwaps swaps.
   where is the number of swaps that took place.
2. First Element: firstElement
   where is the first element in the sorted array.
3. Last Element: lastElement
   where 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, , denoting the number of elements in array .
The second line contains space-separated integers describing the respective values of .

Constraints

• , where .

Output Format

Print the following three lines of output:

1. Array is sorted in numSwaps swaps.
   where is the number of swaps that took place.
2. First Element: firstElement
   where is the first element in the sorted array.
3. Last Element: lastElement
   where is the last element in the sorted array.

Sample Input 0

31 2 3

Sample Output 0

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

Explanation 0

The array is already sorted, so swaps take place and we print the necessary lines of output shown above.

Sample Input 1

33 2 1

Sample Output 1

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

Explanation 1

The array is not sorted, so we perform the following swaps:

At this point the array is sorted and we print the necessary lines of output shown above.

Source : https://www.hackerrank.com/challenges/30-sorting

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	public class Solution {
	private static int swaps = 0;
	public static void main(String[] args) {
	/* Save input */
	Scanner scan = new Scanner(System.in);
	int size = scan.nextInt();
	int [] array = new int[size];
	for (int i = 0; i < size; i++) {
	array[i] = scan.nextInt();
	}
	scan.close();
	bubbleSort(array);
	System.out.println("Array is sorted in " + swaps + " swaps.");
	System.out.println("First Element: " + array[0]);
	System.out.println("Last Element: " + array[array.length - 1]);
	}
	private static void bubbleSort(int [] array) {
	if (array == null) {
	return;
	}
	boolean swapped = true;
	int endOffset = 0; // optimizes code
	while (swapped) {
	swapped = false;
	for (int i = 1; i < array.length - endOffset; i++) {
	if (array[i-1] > array[i]){
	swap(array, i-1, i);
	swapped = true;
	}
	}
	endOffset++;
	}
	}
	/* Standard swap. Also updates our "swaps" variable */
	private static void swap(int [] array, int i, int j) {
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
	swaps++;
	}
	}