Bubble Sort and Binary Search – Java
Just like that i was again brushing my core Java few days back and wrote bubble sort and binary search code in Java. Here i am sharing the code, please post your comments in case this can be further optimized:
Bubble Sort:
public static void main(String args[]) throws Exception{
int[] newArr = new int[]{21,33,2,56,34,11,7,35,27,87,233,108,26,12,6,90,365,243,666,67};
int n = newArr.length;
boolean doMore = true;
while (doMore){
n--;
doMore = false;
for (int i=0; i < n; i++) {
if (newArr[i] > newArr[i+1]) {
// exchange elements
int temp = newArr[i]; newArr[i] = newArr[i+1]; newArr[i+1] = temp;
doMore = true;
}
}
}
printArray(newArr);
}
public static void printArray(int[] arr){
System.out.println("===========START=============");
for (int n=0; n < arr.length;n++){
System.out.println("Arr[" + (n) + "] :" + arr[n]);
}
System.out.println("============END==============");
}
And once we have sorted array with us we can apply binary search on it, Let say we want to search 11, here is the program which will do the binary searching :
int x = 11;
int low = 0;
int high = newArr.length - 1;
int mid;
boolean breakLoop = true;
while(low <= high && breakLoop){
mid = (low + high) / 2;
if( newArr[mid] < x )
low = mid + 1;
else if(newArr[mid]> x )
high = mid - 1;
else{
System.out.println(mid);
breakLoop = false;
}
}
System.out.println("NOT_FOUND");
To further optimize this we can remove one comparison and do it like this:
int x = 11;
int low = 0;
int high = newArr.length - 1;
int mid;
while(low < high){
mid = low + (high -low) / 2;
if( newArr[mid] < x )
low = mid + 1;
else
high = mid ;
}
if ((low < newArr.length - 1) && (newArr[low] == x))
System.out.println(low);
else
System.out.println("NOT_FOUND");
Most Commented Posts
If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.
Optimization…
In the case of Bubble Sort… with every loop lower positions keep getting sorted. So your for loop can start ahead… it need not look into positions of array that are already sorted.
So.. your loop
for (int i=0; i < n; i++) {
may look like:
int noOfLoopsDone=0;
for (int i=noOfLoopsDone; i < n; i++) {
noOfLoopsDone++;