Sorting is one of the major required feature for any application during implementation of any business logic.
There are different types of sorting in place based on performance, speed, cost of operation.
One of simplest and easy algorithm is Bubble Sort Algorithm which is an easy one to understand/implement for any quick implementation.
Sorting a List of items [10, 5, 8, 6 , 4] needs each item to be compared with another item in the list.
Bubble Sort Algorithm:
- Take the 1st position number and compare with all the items in the list. (If other number less than 1st Position number, swap the position of numbers)
- Iterate the above step, n times.,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
import java.util.*; public class TutorialFlow { public static void main(String args[]) { BubbleSort bsort = new BubbleSort(); int items[] = {10, 5, 8, 6, 4}; bsort.sort(items); System.out.println("Bubble Sorted List of Items:"); bsort.display(items); } } class BubbleSort { public void sort(int items[]) { int n = items.length; for (int i = 0; i<n-1; i++) for (int j = 0; j<n-i-1; j++) if (items[j] > items[j + 1]) { int temp = items[j]; items[j] = items[j + 1]; items[j + 1] = temp; } } public void display(int items[]) { System.out.println("**************"); for (int i = 0; i < items.length; ++i) { System.out.print(items[i] + " "); } System.out.println("\r\n**************"); } } |
Result:
1 2 3 4 |
Bubble Sorted List of Items: ************** 4 5 6 8 10 ************** |
Time Complexity -> O(N2)
Bubble Sort Comparison Explained with the Example
Take the above List of items.
Since the length of items is 5, there will be 5 iteration for each element to compare with each of the number in the list.
[10, 5, 8, 6, 4]
- First Position Number comparing Iteration:
- Take the number in the first position(10) and compare with all the other numbers [5, 8, 6, 4], if greater then swap it.
- For example, when comparing, 10>5 , then swap the numbers and list will be like below.
- [10, 5, 8, 6, 4] —-> [5, 10, 8, 6, 4] , 10 and 5 is compared… swapped since 10>5.
- Now 5 becomes first position number., so start compare with further numbers one by one.
- [5, 10, 8, 6, 4] —-> [5, 10, 8, 6, 4] , 5 and 8 is compared.. no swap.,
- [5, 10, 8, 6, 4] —-> [5, 10, 8, 6, 4] , 5 and 6 is compared.. no swap.,
- [5, 10, 8, 6, 4] —-> [4, 10, 8, 6, 5] , 5 and 4 is compared.. swapped since 5 > 4.,
Repeat the above step n times, so that lowest value numbers will be moved to the left of the List.