Simple Sorting and Searching Algorithms
Bubble Sort
In bubble sort we compare a adjacent pair of items and swap if they are in incorrect order until all the items are sorted out.Code:
public class BubbleSort{
public static void main(String args[]){
int []arr={99,34,23,54,32,10};
bubbleSort(arr);
System.out.println("\nSorted Array:");
printArray(arr);
bubbleSort(arr);
System.out.println("\nSorted Array:");
printArray(arr);
}
static void bubbleSort(int []arr){
int temp;
for(int k=arr.length;k>1;k--){
for(int k=arr.length;k>1;k--){
for(int i=0;i<arr.length;i++){
if(arr[i]>arr[i+1]){
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
printArray(arr);
printArray(arr);
}
}
static void printArray(int []arr){
for(int i:arr){
System.out.print(i+", ");
}
System.out.println();
System.out.println();
}
}Output:
34, 23, 54, 32, 10, 99,
23, 34, 32, 10, 54, 99,
23, 32, 10, 34, 54, 99,
23, 10, 32, 34, 54, 99,
10, 23, 32, 34, 54, 99,
Sorted Array:
10, 23, 32, 34, 54, 99,
Linear Search
In linear search we gonna take value by value sequentially until we find the item or until all the items are checked.Code:
public class LinearSearch{
public static void main(String args[]){
int []arr={99,34,23,54,32,10};
int searchItem=23;
linearSearch(arr,searchItem);
int searchItem=23;
linearSearch(arr,searchItem);
searchItem=100;
linearSearch(arr,searchItem);
linearSearch(arr,searchItem);
}
static void linearSearch(int []arr,int searchItem){
boolean isFound=false;
for(int i=0;i<arr.length;i++){
for(int i=0;i<arr.length;i++){
if(arr[i]==searchItem){
isFound=true;
System.out.println("Item Found");
break;
System.out.println("Item Found");
break;
}
}
if(isFound==false){
System.out.println("Item Not Found");
}
}
}Output:
Item Found
Item Not Found
Binary Search
To do binary search, the array must be sorted in ascending or descending order. In binary search we always compare the searching item with the middle item and if it is not the desired value then we gonna see whether the searching item is smaller than or larger than the middle item. accordingly we gonna take the sub array and repeat the same process until we found the item or until sub array consist with only one item.public class BinarySearch{
public static void main(String args[]){
int []arr={10,23,45,62,75,89};
int searchItem=23;
binarySearch(arr,searchItem);
binarySearch(arr,searchItem);
searchItem=100;
binarySearch(arr,searchItem);
binarySearch(arr,searchItem);
}
static void binarySearch(int []arr,int searchItem){
int fi=0;
int li=arr.length-1;
int mi=(fi+li)/2;
System.out.println(fi+" "+mi+" "+li);
boolean isFound=false;
int li=arr.length-1;
int mi=(fi+li)/2;
System.out.println(fi+" "+mi+" "+li);
boolean isFound=false;
while(fi<=li){
if(arr[mi]==searchItem){
System.out.println("Item Found");
isFound=true;
break;
isFound=true;
break;
}else if(arr[mi]<searchItem){
fi=mi+1;
}else{
li=mi-1;
}
mi=(fi+li)/2;
System.out.println(fi+" "+mi+" "+li);
mi=(fi+li)/2;
System.out.println(fi+" "+mi+" "+li);
}
if(isFound==false){
System.out.println("Item Not Found");
}
}
}Output:
0 2 5
0 0 1
1 1 1
Item Found
0 2 5
3 4 5
5 5 5
6 5 5
Item Not Found
Comments
Post a Comment