Created
October 27, 2016 04:07
-
-
Save feliperazeek/8feb499216851612ed9de2def805aaae to your computer and use it in GitHub Desktop.
HackerRank - Cracking the Code Interview - Sorting: Bubble Sort (https://www.hackerrank.com/challenges/ctci-bubble-sort)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.*; | |
import java.util.*; | |
public class Solution { | |
private static void work(int[] a) { | |
int swaps = 0; | |
int n = a.length; | |
if (n == 0) return; | |
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, j + 1); | |
numberOfSwaps++; | |
swaps++; | |
} | |
} | |
// If no elements were swapped during a traversal, array is sorted | |
if (numberOfSwaps == 0) { | |
break; | |
} | |
} | |
System.out.println("Array is sorted in " + swaps + " swaps."); | |
System.out.println("First Element: " + a[0]); | |
System.out.println("Last Element: " + a[n - 1]); | |
} | |
private static void swap(int[] a, int from, int to) { | |
int newFrom = a[to]; | |
int newTo = a[from]; | |
a[from] = newFrom; | |
a[to] = newTo; | |
} | |
public static void main(String[] args) { | |
Scanner in = new Scanner(System.in); | |
int n = in.nextInt(); | |
int a[] = new int[n]; | |
for(int a_i=0; a_i < n; a_i++){ | |
a[a_i] = in.nextInt(); | |
} | |
work(a); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment