In this tutorial we are going to see some of the important sorting techniques.
1 : Bubble Sort
2 : Quick Sort
3 : Merge Sort
Bubble Sort :
Bubble sort or sinking sort is a sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
Algorithms : Bubble sort has worst-case and average complexity both O(n2), where n is the number of items being sorted.
Step 1: The 0th element is compared with the 1st element.If it is found greater than the 1st element ,they are swapped.
Step 2 : Then the 1st element is compared with the 2nd element.If it is found greater than the 1st element ,they are swapped.
Step 3 : In the same way all the elements are compared with their next element and they are swapped if required.This is the first iteration.On completing this iteration largest element is placed in the last position
Step 4 : Similarly in the second iteration the comparisons are made till last but one element and the second largest element is placed in the second last position.
Step 5 : After all iterations elements are sorted.
Complexity :
| Algorithm | Worst Case | Average Case | Best Case |
| Bubble Sort |  |
|
|
Question :
Given an array.Sort the array using bubble sort technique ?
Solution :
The problem is solved in iterative way.
Program :
|
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 36 37 |
package com.csrevisited.dsalgo.sort; public class BubbleSort { public static void main(String[] args) { int[] arr = { 3, 5, 1, 2, 7, 9, 6, 8, 10, 4 }; System.out.println("Array Before Sorting"); displayArray(arr); bubbleSort(arr); System.out.println(); System.out.println("Array After Sorting"); displayArray(arr); } private static void displayArray(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + "\t"); } } private static void bubbleSort(int[] arr) { int temp; for (int i = 0; i <= arr.length - 2; i++) { for (int j = 0; j <= arr.length - 2 - i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } } |
|
1 2 3 4 5 |
OutPut: Array Before Sorting 3 5 1 2 7 9 6 8 10 4 Array After Sorting 1 2 3 4 5 6 7 8 9 10 |