Java Program To Perform Bubble Sort on String
- July 10, 2020
- by
Java Program To Perform Bubble Sort on String
In this Java Program, we perform bubble sort on the string.
Bubble Sort is the simple sorting algorithm. In which, each adjacent pair of the elements is compared and swapped if they are not in the correct order. This algorithm is not suitable for large datasets as its average and worst case complexity are of Ο(n2) ,where n is the number of times.
Algorithm :
begin BubbleSort(list)
for all elements of list
if list [i] > list [i + 1]
swap (list [i], list [i+1])
end if
end for
return list
end BubbleSort
Example:
Let us take an array of unsorted element. As the algorithm takes Ο(n2), we keep it short and simple.
The algorithm will move in rounds.
Round 1 :
52, 65 , 24 , 31 , 10
The algorithm will start with the comparison of first two elements by comparing which one is greater.
52, 65 , 24 , 31 , 10
In the above case, 52 is smaller than 65, so it is already in a sorted locations. So the algorithm will sort next two numbers i.e. 65 and 24.
52, 65 , 24 , 31 , 10
In the above case, 24 is smaller than 65, so it will be swapped to enter into the correct location.
52, 24 , 65 , 31 , 10
Now the algorithm will move forward and compare the elements 65 and 31
52, 24 , 65 , 31 , 10
As the element 31 is smaller than 65 it will be swapped.
52, 24 , 31 , 65 , 10
Now the algorithm will move forward and compare the elements 65 and 10
52, 24 , 31 , 65 , 10
As the element 10 is smaller than 65 it will be swapped.
52, 24 , 31 , 10 , 65
As all the elements are sorted in the array, the algorithm will move to round 2 till it reaches the correct order locations of each element.
Round 2 :
From Round 1 we have the sorted array as:
52, 24 , 31 , 10, 65
In the above case, 24 is smaller than 52, so it will be swapped to enter into the correct location.
24, 52 , 31 , 10 , 65
Now the algorithm will move forward and compare the elements 52 and 31
24, 52 , 31 , 10 , 65
As the element 31 is smaller than 52 it will be swapped.
24, 31 , 52 , 10 , 65
Now the algorithm will move forward and compare the elements 52 and 10
24, 31 , 52 , 10 , 65
As the element 10 is smaller than 52 it will be swapped.
24, 31 , 10 , 52 , 65
As the element 52 is smaller than 65 it will not be swapped as they are already in their correct position.
24, 31 , 10 , 52 , 65
Yet the array from round 2 is not completely sorted, hence it will move into round 3.
Round 3 :
24, 31 , 10 , 52 , 65
In the above case, 24 is smaller than 31, so it will not be swapped as they are already in their correct position.
24, 31 , 10 , 52 , 65
Now the algorithm will move forward and compare the elements 31 and 10
24, 31 , 10 , 52 , 65
As the element 10 is smaller than 31 it will be swapped.
24, 10 , 31 , 52 , 65
Now the algorithm will move forward and compare the elements 31 and 52
24, 10 , 31 , 52 , 65
As the element 31 is smaller than 52 it will not be swapped as they are already in their correct position.
24, 10 , 31 , 52 , 65
Now the algorithm will move forward and compare the elements 52 and 65
24, 10 , 31 , 52 , 65
As the element 52 is smaller than 65 it will not be swapped as they are already in their correct position.
24, 10 , 31 , 52 , 65
Yet the array from round 3 is not completely sorted, hence it will move into round 4.
Round 4 :
24, 10 , 31 , 52 , 65
In the above case, 10 is smaller than 24, so it will be swapped.
24, 10 , 31 , 52 , 65
Now the algorithm will stop as all the elements are in their sorted positions.
10, 24 , 31 , 52 , 65
Hence in this way we sort the elements by using bubble sort.
Step 1 : Create an array named str[] and store the values in it.
Step 2 : Create another variable temp
Step 3 : Print "Strings in sorted order" by using System.out.println method
Step 4 : Apply for loop of j , initialize j to 0, j should be smaller than str.length and increment j.
Step 5 : Apply for loop of i, initialize i = j + 1, i should be smaller than str.length and increment i.
Step 6 : Compare the adjacent strings. If str[i].compareTo(str[j]) is smaller than 0, then store str[j] in temp, store str[i] in str[j], and store temp in str[i].
Step 7 : Print str[i]
Program :
public class BubbleSort
{
public static void main(String[] args)
{
String str[] = { "Rekha", "Mamta", "Trupti", "Sandhya"};
String temp;
System.out.println("Strings in sorted order:");
for(int j = 0; j < str.length; j++)
{
for(int i = j + 1; i < str.length; i++)
{
//comparing adjacent strings
if(str[i].compareTo(str[j]) < 0)
{
temp = str[j];
str[j] = str [i];
str[i] = temp;
}
}
System.out.println(str[j]);
}
}
}
Output :
Strings in sorted order:
Mamta
Rekha
Sandhya
Trupti
For execution of the same do visit my YouTube Channel :
0 comments:
Post a Comment