1.
/*
2.
Java Bubble Sort Example
3.
This Java bubble sort example shows how to sort an array
of int using bubble
4.
sort algorithm. Bubble sort is the simplest sorting
algorithm.
5.
*/
6.
7.
public class BubbleSort {
8.
9.
public static void main(String[] args) {
10.
11.
//create an int array we want to sort
using bubble sort algorithm
12.
int intArray[] = new int[]{5,90,35,45,150,3};
13.
14.
//print array before sorting using
bubble sort algorithm
15.
System.out.println("Array
Before Bubble Sort");
16.
for(int i=0; i < intArray.length; i++){
17.
System.out.print(intArray[i] + " ");
18.
}
19.
20.
//sort an array using bubble sort
algorithm
21.
bubbleSort(intArray);
22.
23.
System.out.println("");
24.
25.
//print array after sorting using bubble
sort algorithm
26.
System.out.println("Array
After Bubble Sort");
27.
for(int i=0; i < intArray.length; i++){
28.
System.out.print(intArray[i] + " ");
29.
}
30.
31. }
32.
33. private static void bubbleSort(int[] intArray) {
34.
35.
/*
36.
* In bubble sort, we basically traverse the array
from first
37.
* to array_length - 1 position and compare the
element with the next one.
38.
* Element is swapped with the next element if the
next element is greater.
39.
*
40.
* Bubble sort steps are as follows.
41.
*
42.
* 1. Compare array[0] & array[1]
43.
* 2. If array[0] > array [1] swap it.
44.
* 3. Compare array[1] & array[2]
45.
* 4. If array[1] > array[2] swap it.
46.
* ...
47.
* 5. Compare array[n-1] & array[n]
48.
* 6. if [n-1] > array[n] then swap it.
49.
*
50.
* After this step we will have largest element at
the last index.
51.
*
52.
* Repeat the same steps for array[1] to array[n-1]
53.
*
54.
*/
55.
56.
int n = intArray.length;
57.
int temp = 0;
58.
59.
for(int i=0; i < n; i++){
60.
for(int j=1; j < (n-i); j++){
61.
62.
if(intArray[j-1] > intArray[j]){
63.
//swap the elements!
64.
temp = intArray[j-1];
65.
intArray[j-1] = intArray[j];
66.
intArray[j] = temp;
67.
}
68.
69.
}
70.
}
71.
72. }
73. }
74.
75. /*
76. Output of the Bubble Sort Example would
be
77.
78. Array Before Bubble Sort
79. 5 90 35 45 150 3
80. Array After Bubble Sort
81. 3 5 35 45 90 150
82.
83. */
1.
/*
2.
Java Bubble Sort Example
3.
This Java bubble sort example shows how to sort an array
of int using bubble
4.
sort algorithm. Bubble sort is the simplest sorting
algorithm.
5.
*/
6.
7.
public class BubbleSort {
8.
9.
public static void main(String[] args) {
10.
11.
//create an int array we want to sort
using bubble sort algorithm
12.
int intArray[] = new int[]{5,90,35,45,150,3};
13.
14.
//print array before sorting using
bubble sort algorithm
15.
System.out.println("Array
Before Bubble Sort");
16.
for(int i=0; i < intArray.length; i++){
17.
System.out.print(intArray[i] + " ");
18.
}
19.
20.
//sort an array using bubble sort
algorithm
21.
bubbleSort(intArray);
22.
23.
System.out.println("");
24.
25.
//print array after sorting using bubble
sort algorithm
26.
System.out.println("Array
After Bubble Sort");
27.
for(int i=0; i < intArray.length; i++){
28.
System.out.print(intArray[i] + " ");
29.
}
30.
31. }
32.
33. private static void bubbleSort(int[] intArray) {
34.
35.
/*
36.
* In bubble sort, we basically traverse the array
from first
37.
* to array_length - 1 position and compare the
element with the next one.
38.
* Element is swapped with the next element if the
next element is greater.
39.
*
40.
* Bubble sort steps are as follows.
41.
*
42.
* 1. Compare array[0] & array[1]
43.
* 2. If array[0] > array [1] swap it.
44.
* 3. Compare array[1] & array[2]
45.
* 4. If array[1] > array[2] swap it.
46.
* ...
47.
* 5. Compare array[n-1] & array[n]
48.
* 6. if [n-1] > array[n] then swap it.
49.
*
50.
* After this step we will have largest element at
the last index.
51.
*
52.
* Repeat the same steps for array[1] to array[n-1]
53.
*
54.
*/
55.
56.
int n = intArray.length;
57.
int temp = 0;
58.
59.
for(int i=0; i < n; i++){
60.
for(int j=1; j < (n-i); j++){
61.
62.
if(intArray[j-1] > intArray[j]){
63.
//swap the elements!
64.
temp = intArray[j-1];
65.
intArray[j-1] = intArray[j];
66.
intArray[j] = temp;
67.
}
68.
69.
}
70.
}
71.
72. }
73. }
74.
75. /*
76. Output of the Bubble Sort Example would
be
77.
78. Array Before Bubble Sort
79. 5 90 35 45 150 3
80. Array After Bubble Sort
81. 3 5 35 45 90 150
82.
83. */
Bubble Sort -- fixed number of passes
This
version of bubble sort makes a fixed number of passes (length of the array -
1). Each inner loop is one shorter than the previous one.
public
static void bubbleSort1(int[] x) {
int n = x.length;
for (int pass=1; pass < n; pass++)
{ // count how many times
// This next loop becomes shorter and
shorter
for (int i=0; i < n-pass; i++) {
if (x[i] > x[i+1]) {
// exchange elements
int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp;
}
}
}
}
Bubble Sort -- stop when no exchanges
This
version of bubble sort continues making passes over the array as long as there
were any exchanges. If the array is already sorted, this sort will stop after
only one pass.
public
static void bubbleSort2(int[] x) {
boolean doMore = true;
while (doMore) {
doMore = false; // assume this is last pass over array
for (int i=0; i<x.length-1; i++) {
if (x[i] > x[i+1]) {
// exchange elements
int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp;
doMore = true; // after an exchange, must look again
}
}
}
}
Bubble Sort -- stop when no exchanges, shorter range
each time
This
version of bubble sort combines ideas from the previous versions. It stops when
there are no more exchanges, and it also sorts a smaller range each time.
public
static void bubbleSort3(int[] x) {
int n = x.length;
boolean doMore = true;
while (doMore) {
n--;
doMore = false; // assume this is our last pass over the
array
for (int i=0; i<n; i++) {
if (x[i] > x[i+1]) {
// exchange elements
int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp;
doMore = true; // after an exchange, must look again
}
}
}
}//end
method bubbleSort3
Bubble Sort -- Sort only necessary range
After
a pass on bubble sort, it's only necessary to sort from just below the first
exchange to just after the last exchange, because everything that wasn't
exchanged must be in the correct order. This version of bubble sort remembers
the lowest and highest locations where there was an exchange, and sorts only
that part of the array. Although it is a little more complicated, it is more
efficient than the other bubble sorts.
public
static void bubbleSort4(int[] x) {
int newLowest = 0; // index of first comparison
int newHighest = x.length-1; // index of last comparison
while (newLowest < newHighest) {
int highest = newHighest;
int lowest = newLowest;
newLowest = x.length; // start higher than any legal index
for (int i=lowest; i<highest; i++) {
if (x[i] > x[i+1]) {
// exchange elements
int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp;
if (i<newLowest) {
newLowest = i-1;
if (newLowest < 0) {
newLowest = 0;
}
} else if (i>newHighest) {
newHighest = i+1;
}
}
}
}
}//end
method bubbleSort4
Tidak ada komentar:
Posting Komentar