Introduction
In today's article we discuss what sorting is and discuss the bubble sort in detail with an example in Java.
What is Sorting
Sorting is the process of putting a list or a group of items in a specific order. Some common sorting criteria are: alphabetical or numerical. Sorting can also be done in ascending order (A-Z) or descending order (Z-A). Sorting refers to ordering data in an increasing or decreasing fashion according to some linear relationship among the data items. Sorting can be done on names, numbers and records. That is, sorting greatly improves the efficiency of searching.
Importance of Sorting
To look up the word in a dictionary: This data are in a sorted manner. You do a few quick searches until you find the page, and then finally scan the page for the word. Now imagine the words are not sorted. Now you need more time to search the data because the time to search the unsorted data would be prohibitive, and you'd be right!
You could apply the same principle to many other types of data in the real world, such as finding names in books on the shelves of a library or the phone book.
Sorting are of various types. Some of the main sorting algorithms are:
- Insertion sort
- Merge Sort
- Quick Sort
- Shell Sort
- Radix Sort
- Heap Sort
- Bucket Sort
- Selection sort
- Bubble sort
Bubble Sort
Bubble sort is one of the classic sorting algorithms for sorting, taught in various computer and engineering courses. In the Bubble sort algorithm we sort an unsorted array by starting from the first element and comparing with adjacent elements. If the former is greater than the latter then we swap and by doing this we get the largest number at the end after the first iteration. So in order to sort n elements you require n-1 iterations and nearly n-1 comparisons. To recap, here is the logic for a bubble sort sorting algorithm. Because of its algorithmic nature and simplicity its often used in various Java and C exercises. Since algorithmic questions are always a tricky question and not easy to code, I have seen many developers fumble if asked to code it on the spot. That's why its advisable to do logical and algorithmic programming when learning programming and OOP to get this skill of converting logic into code.
The following procedure shows how the data is sorted in a Bubble Sort:
1. start comparing i[0] to i[1]
2. if i[0] > i[1] then swap numbers
3. compare i[1] to i[2] and repeat until you have compared the last pair
4. This is referred to as one pass and at the end of the first pass the largest number is at the last
5. repeat this comparison again starting from i[0] but this time proceed until the second to the last pair only
Example
public class BubbleSortEx
{
public static void main(String a[])
{
//Numbers which are to be sorted
int n[] = {124,23,43,12,177,25,2,1,67};
//Displays the numbers before sorting
System.out.print("Before sorting, numbers are ");
for(int i = 0; i < n.length; i++)
{
System.out.print(n[i]+" ");
}
System.out.println();
//Sorting in ascending order using bubble sort
initializebubbleSort(n);
//Displaying the numbers after sorting
System.out.print("After sorting, numbers are ");
for(int i = 0; i < n.length; i++)
{
System.out.print(n[i]+" ");
}
}
//This method sorts the input array in asecnding order
public static void initializebubbleSort( int n[])
{
int temp,i,j;
for(i = 0; i < n.length; i++)
{
for(j = 1; j < (n.length -i); j++)
{
//if n[j-1] > n[j], swap the elements
if(n[j-1] > n[j])
{
temp = n[j-1];
n[j-1]=n[j];
n[j]=temp;
}
}
}
}
}
Output
![bubblesort.jpg]()