Data Structure – Bubble Sort

for sorting an array using bubble sort you can use this. you can copy paste the code and run them, see the output and compare how different they are working.


/**
*
* @author Unknown_
*/
public class BubbleSort {

public static int[] myArray = new int[]{10, 2, 5, 20, 90, 12, 31, 5};

/**
* basic sorting -- check as much as you can to make sure it has sorted everything in array.
* @param myArray
*/
public void sort(int[] myArray) {

if (myArray.length == 0) {
return;
}

int counter = myArray.length;
while (counter != 0) {
int tmp = 0;
for (int index = 0; index + 1 < myArray.length; index++) { tmp = 0; if (myArray[index] >= myArray[index + 1]) {
tmp = myArray[index];
myArray[index] = myArray[index + 1];
myArray[index + 1] = tmp;

}
showContent(myArray);
}
counter--;
}

}

/**
* enhanced
*
* @param myArray
*/
public void sort2(int[] myArray) {

if (myArray.length == 0) {
return;
}

int tmp = 0;
for (int j = myArray.length; j > 0; j--) {

for (int i = 0; i + 1 < j; i++) { tmp = 0; if (myArray[i] >= myArray[i + 1]) {
tmp = myArray[i];
myArray[i] = myArray[i + 1];
myArray[i + 1] = tmp;

}
System.out.printf("i = %d , j= %d ", i, j);
showContent(myArray);
}
}
}

/**
* resetting array content to what it was.
*/
public static void resetData() {
myArray = new int[]{10, 2, 5, 20, 90, 12, 31, 5};
}

/**
* showing content of array
* @param arr
*/
public void showContent(int[] arr) {

System.out.print("[ ");
for (int i : arr) {
System.out.printf("%d, ", i);
}
System.out.println(" ]");
}

public static void main(String[] args) {
BubbleSort bs = new BubbleSort();

bs.showContent(BubbleSort.myArray);
bs.sort(BubbleSort.myArray);
bs.showContent(BubbleSort.myArray);

bs.resetData();

System.out.println("---------Sort2-------");
bs.showContent(BubbleSort.myArray);
System.out.println("====== starting ====");
bs.sort2(BubbleSort.myArray);
System.out.println("====== finished ====");
bs.showContent(BubbleSort.myArray);

}

}

and its output became something like this …

run:
[ 10, 2, 5, 20, 90, 12, 31, 5,  ]
[ 2, 10, 5, 20, 90, 12, 31, 5,  ]
[ 2, 5, 10, 20, 90, 12, 31, 5,  ]
[ 2, 5, 10, 20, 90, 12, 31, 5,  ]
[ 2, 5, 10, 20, 90, 12, 31, 5,  ]
[ 2, 5, 10, 20, 12, 90, 31, 5,  ]
[ 2, 5, 10, 20, 12, 31, 90, 5,  ]
[ 2, 5, 10, 20, 12, 31, 5, 90,  ]
[ 2, 5, 10, 20, 12, 31, 5, 90,  ]
[ 2, 5, 10, 20, 12, 31, 5, 90,  ]
[ 2, 5, 10, 20, 12, 31, 5, 90,  ]
[ 2, 5, 10, 12, 20, 31, 5, 90,  ]
[ 2, 5, 10, 12, 20, 31, 5, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
---------Sort2-------
[ 10, 2, 5, 20, 90, 12, 31, 5,  ]
====== starting ====
i = 0 , j= 8 [ 2, 10, 5, 20, 90, 12, 31, 5,  ]
i = 1 , j= 8 [ 2, 5, 10, 20, 90, 12, 31, 5,  ]
i = 2 , j= 8 [ 2, 5, 10, 20, 90, 12, 31, 5,  ]
i = 3 , j= 8 [ 2, 5, 10, 20, 90, 12, 31, 5,  ]
i = 4 , j= 8 [ 2, 5, 10, 20, 12, 90, 31, 5,  ]
i = 5 , j= 8 [ 2, 5, 10, 20, 12, 31, 90, 5,  ]
i = 6 , j= 8 [ 2, 5, 10, 20, 12, 31, 5, 90,  ]
i = 0 , j= 7 [ 2, 5, 10, 20, 12, 31, 5, 90,  ]
i = 1 , j= 7 [ 2, 5, 10, 20, 12, 31, 5, 90,  ]
i = 2 , j= 7 [ 2, 5, 10, 20, 12, 31, 5, 90,  ]
i = 3 , j= 7 [ 2, 5, 10, 12, 20, 31, 5, 90,  ]
i = 4 , j= 7 [ 2, 5, 10, 12, 20, 31, 5, 90,  ]
i = 5 , j= 7 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 0 , j= 6 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 1 , j= 6 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 2 , j= 6 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 3 , j= 6 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 4 , j= 6 [ 2, 5, 10, 12, 5, 20, 31, 90,  ]
i = 0 , j= 5 [ 2, 5, 10, 12, 5, 20, 31, 90,  ]
i = 1 , j= 5 [ 2, 5, 10, 12, 5, 20, 31, 90,  ]
i = 2 , j= 5 [ 2, 5, 10, 12, 5, 20, 31, 90,  ]
i = 3 , j= 5 [ 2, 5, 10, 5, 12, 20, 31, 90,  ]
i = 0 , j= 4 [ 2, 5, 10, 5, 12, 20, 31, 90,  ]
i = 1 , j= 4 [ 2, 5, 10, 5, 12, 20, 31, 90,  ]
i = 2 , j= 4 [ 2, 5, 5, 10, 12, 20, 31, 90,  ]
i = 0 , j= 3 [ 2, 5, 5, 10, 12, 20, 31, 90,  ]
i = 1 , j= 3 [ 2, 5, 5, 10, 12, 20, 31, 90,  ]
i = 0 , j= 2 [ 2, 5, 5, 10, 12, 20, 31, 90,  ]
====== finished ====
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
BUILD SUCCESSFUL (total time: 0 seconds)

order of complexity is

O(N^2) in the worst case and average case scenario.

O(n) when the array is pre-sorted even in a large number of data.

it doesn’t use  any additional memory and everything will happen in place.

it needs many iterations through the array (Named it PASS) to finish the sorting. in my first algorithm you can find this PASS checking by WHILE loop and in the second algorithm it’s the outer FOR loop.

Advertisements

One thought on “Data Structure – Bubble Sort

  1. Pingback: Data Structure – Sorting Algorithms in Java | Navid's Thoughts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s