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);
}
}
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.
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;
}
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With