Reputation: 169
Sorting an Array of int using BubbleSort
Why is my printed out Array not sorted in the below code?
public class BubbleSort {
public void sortArray(int[] x) {//go through the array and sort from smallest to highest
for(int i=1; i<x.length; i++) {
int temp=0;
if(x[i-1] > x[i]) {
temp = x[i-1];
x[i-1] = x[i];
x[i] = temp;
}
}
}
public void printArray(int[] x) {
for(int i=0; i<x.length; i++)
System.out.print(x[i] + " ");
}
public static void main(String[] args) {
// TestBubbleSort
BubbleSort b = new BubbleSort();
int[] num = {5,4,3,2,1};
b.sortArray(num);
b.printArray(num);
}
}
Upvotes: 12
Views: 136012
Answers (16)
Reputation: 7828
Really not getting the bubble sort, which can be called a sinking sort more appropriately since it's actually sinking the bigger/heavier to the bottom as the majority of the answers presented. One of the most typicals will be
private static void sortZero(Comparable[] arr) {
boolean moreSinkingRequired = true;
while (moreSinkingRequired) {
moreSinkingRequired = false;
for (int j = 0; j < arr.length - 1; ++j) {
if (less(arr, j + 1, j)) {
exch(arr, j, j + 1);
moreSinkingRequired = true;
}
}
}
}
By the way, you have to traverse once more than actually required to stop earlier.
But as I see it bubbling as
private static void sortOne(Comparable[] arr) {
for (int i = 0; i < arr.length - 1; ++i) {
for (int j = arr.length - 1; j > i; --j) { // start from the bottom
if (less(arr, j, j - 1)) {
exch(arr, j - 1, j);
}
}
}
}
You have to know this method is actually better since it's tracking the end point for comparison by j > i with [0, i-1] already sorted.
We also can add earlier termination but it then becomes verbose as
private static void sortTwo(Comparable[] arr) {
boolean moreBubbleRequired = true;
for (int i = 0; i < arr.length - 1 && moreBubbleRequired; ++i) {
moreBubbleRequired = false;
for (int j = arr.length - 1; j > i; --j) {
if (less(arr, j, j - 1)) {
exch(arr, j - 1, j);
moreBubbleRequired = true;
}
}
}
}
The utils used to make the process terse are
public static boolean less(Comparable[] arr, int i, int j) {
return less(arr[i], arr[j]);
}
public static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
public static void exch(Comparable[] arr, int i, int j) {
Comparable t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
Upvotes: 0
Reputation: 445
public class Bubblesort{
public static int arr[];
public static void main(String args[]){
System.out.println("Enter number of element you have in array for performing bubblesort");
int numbofele = Integer.parseInt(args[0]);
System.out.println("numer of element entered is"+ "\n" + numbofele);
arr= new int[numbofele];
System.out.println("Enter Elements of array");
System.out.println("The given array is");
for(int i=0,j=1;i<numbofele;i++,j++){
arr[i]=Integer.parseInt(args[j]);
System.out.println(arr[i]);
}
boolean swapped = false;
System.out.println("The sorted array is");
for(int k=0;k<numbofele-1;k++){
for(int l=0;l+1<numbofele-k;l++){
if(arr[l]>arr[l+1]){
int temp = arr[l];
arr[l]= arr[l+1];
arr[l+1]=temp;
swapped=true;
}
}
if(!swapped){
for(int m=0;m<numbofele;m++){
System.out.println(arr[m]);
}
return;
}
}
for(int m=0;m<numbofele;m++){
System.out.println(arr[m]);
}
}
}
Upvotes: 0
Reputation: 897
Here is an example of bubbleSort, and Time Complexity is O(n).
int[] bubbleSort(int[] numbers) {
if(numbers == null || numbers.length == 1) {
return numbers;
}
boolean isSorted = false;
while(!isSorted) {
isSorted = true;
for(int i = 0; i < numbers.length - 1; i++) {
if(numbers[i] > numbers[i + 1]) {
int hold = numbers[i + 1];
numbers[i + 1] = numbers[i];
numbers[i] = hold;
isSorted = false;
}
}
}
return numbers;
}
Upvotes: 0
Reputation: 16465
Here we go
static String arrayToString(int[] array) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < array.length; i++) {
stringBuilder.append(array[i]).append(",");
}
return stringBuilder.deleteCharAt(stringBuilder.length()-1).toString();
}
public static void main(String... args){
int[] unsorted = {9,2,1,4,0};
System.out.println("Sorting an array of Length "+unsorted.length);
enhancedBubbleSort(unsorted);
//dumbBubbleSort(unsorted);
//bubbleSort(unsorted);
//enhancedBubbleSort(unsorted);
//enhancedBubbleSortBetterStructured(unsorted);
System.out.println("Sorted Array: "+arrayToString(unsorted));
}
// this is the dumbest BubbleSort
static int[] dumbBubbleSort(int[] array){
for (int i = 0; i<array.length-1 ; i++) {
for (int j = 0; j < array.length - 1; j++) {
if (array[j] > array[j + 1]) {
// Just swap
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
System.out.println("After "+(i+1)+" pass: "+arrayToString(array));
}
return array;
}
//this "-i" in array.length - 1-i brings some improvement.
// Then for making our bestcase scenario better ( o(n) , we will introduce isswapped flag) that's enhanced bubble sort
static int[] bubbleSort(int[] array){
for (int i = 0; i<array.length-1 ; i++) {
for (int j = 0; j < array.length - 1-i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
System.out.println("After "+(i+1)+" pass: "+arrayToString(array));
}
return array;
}
static int[] enhancedBubbleSort(int[] array){
int i=0;
while (true) {
boolean swapped = false;
for (int j = 0; j < array.length - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped =true;
}
}
i++;
System.out.println("After "+(i)+" pass: "+arrayToString(array));
if(!swapped){
// Last iteration (of outer loop) didnot result in any swaps. so stopping here
break;
}
}
return array;
}
static int[] enhancedBubbleSortBetterStructured(int[] array){
int i=0;
boolean swapped = true;
while (swapped) {
swapped = false;
for (int j = 0; j < array.length - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
i++;
System.out.println("After "+(i)+" pass: "+arrayToString(array));
}
return array;
}
Upvotes: 0
Reputation: 183
Bubble sort algorithm is a simplest way of sorting array elements.Most of another algorithms are more efficient than bubble sort algorithm..Worst case and average case time complexity is (n^2).Let's consider how to implement bubble sort algorithm.
class buble_sort{
public static void main(String a[]){
int[] num={7,9,2,4,5,6,3};
int i,j,tmp;
for(i=0;i<num.length;i++){
for(j=0;j<num.length-i;j++){
if(j==(num.length-1)){
break;
}
else{
if(num[j]>num[j+1]){
tmp=num[j];
num[j]=num[j+1];
num[j+1]=tmp;
}
}
}
}
for(i=0;i<num.length;i++){
System.out.print(num[i]+" ");
}
}
}
Upvotes: 0
Reputation: 11
I use this method for bubble sorting
public static int[] bubbleSort (int[] a) {
int n = a.length;
int j = 0;
boolean swap = true;
while (swap) {
swap = false;
for (int j = 1; j < n; j++) {
if (a[j-1] > a[j]) {
j = a[j-1];
a[j-1] = a[j];
a[j] = j;
swap = true;
}
}
n = n - 1;
}
return a;
}//end bubbleSort
Upvotes: 1
Reputation: 33
public static void BubbleSort(int[] array){
boolean swapped ;
do {
swapped = false;
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = true;
}
}
}while (swapped);
}
Upvotes: 0
Reputation: 87
java code
public void bubbleSort(int[] arr){
boolean isSwapped = true;
for(int i = arr.length - 1; isSwapped; i--){
isSwapped = false;
for(int j = 0; j < i; j++){
if(arr[j] > arr[j+1]}{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
isSwapped = true;
}
}
}
}
Upvotes: -1
Reputation: 2961
Standard Bubble Sort implementation in Java:
//Time complexity: O(n^2)
public static int[] bubbleSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr;
}
for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length - i; j++) {
if (arr[j - 1] > arr[j]) {
arr[j] = arr[j] + arr[j - 1];
arr[j - 1] = arr[j] - arr[j - 1];
arr[j] = arr[j] - arr[j - 1];
}
}
}
return arr;
}
Upvotes: -2
Reputation: 639
public class BubbleSort {
public void sorter(int[] arr, int x, int y){
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
public void sorter1(String[] arr, int x, int y){
String temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
public void sertedArr(int[] a, String[] b){
for(int j = 0; j < a.length - 1; j++){
for(int i = 0; i < a.length - 1; i++){
if(a[i] > a[i + 1]){
sorter(a, i, i + 1);
sorter1(b, i, i + 1);
}
}
}
for(int i = 0; i < a.length; i++){
System.out.print(a[i]);
}
System.out.println();
for(int i = 0; i < b.length; i++){
System.out.print(b[i]);
}
//
}
public static void main(String[] args){
int[] array = {3, 7, 4, 9, 5, 6};
String[] name = {"t", "a", "b", "m", "2", "3"};
BubbleSort bso = new BubbleSort();
bso.sertedArr(array, name);
}
}
Upvotes: -1
Reputation: 1
public class SortingArray {
public static void main(String[] args) {
int[] a={3,7,9,5,1,4,0,2,8,6};
int temp=0;
boolean isSwapped=true;
System.out.println(" before sorting the array: ");
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]);
}
System.out.println("");
do
{
isSwapped=false;
for(int i=0;i<a.length-1;i++)
{
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}while(isSwapped);
System.out.println("after sorting the array: ");
for(int array:a)
{
System.out.print(array);
}
}
}
Upvotes: -1
Reputation: 25221
You're only making one pass through your array! Bubble sort requires you to keep looping until you find that you are no longer doing any swapping; hence the running time of O(n^2).
Try this:
public void sortArray(int[] x) {
boolean swapped = true;
while (swapped) {
swapped = false;
for(int i=1; i<x.length; i++) {
int temp=0;
if(x[i-1] > x[i]) {
temp = x[i-1];
x[i-1] = x[i];
x[i] = temp;
swapped = true;
}
}
}
}
Once swapped == false at the end of a loop, you have made a whole pass without finding any instances where x[i-1] > x[i] and, hence, you know the array is sorted. Only then can you terminate the algorithm.
You can also replace the outer while loop with a for loop of n+1 iterations, which will guarantee that the array is in order; however, the while loop has the advantage of early termination in a better-than-worst-case scenario.
Upvotes: 13
Reputation: 784998
Bubble sort nested loops should be written like this:
int n = intArray.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(intArray[j-1] > intArray[j]){
//swap the elements!
temp = intArray[j-1];
intArray[j-1] = intArray[j];
intArray[j] = temp;
}
}
}
Upvotes: 0
Reputation: 382102
This isn't the bubble sort algorithm, you need to repeat until you have nothing to swap :
public void sortArray(int[] x) {//go through the array and sort from smallest to highest
for(;;) {
boolean s = false;
for(int i=1; i<x.length; i++) {
int temp=0;
if(x[i-1] > x[i]) {
temp = x[i-1];
x[i-1] = x[i];
x[i] = temp;
s = true;
}
}
if (!s) return;
}
}
Upvotes: 0
Reputation: 12169
Your sort logic is wrong. This is the pseudo-code for bubble sort:
for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] < a[j-1],
swap a[j,j-1]
swapped = true
→ invariant: a[1..i] in final position
break if not swapped
end
See this sorting web site for good tutorial on all the various sorting methods.
Upvotes: 2
Reputation: 49362
You need two loops to implement the Bubble Sort .
Sample code :
public static void bubbleSort(int[] numArray) {
int n = numArray.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (numArray[j - 1] > numArray[j]) {
temp = numArray[j - 1];
numArray[j - 1] = numArray[j];
numArray[j] = temp;
}
}
}
}
Upvotes: 45