Sorting Algorithms

Sorting is the process of arranging the elements of an array so that they can be placed either in ascending or descending order. For example, consider an array A = {A1, A2, A3, A4, ?? An }, the array is called to be in ascending order if element of A are arranged like A1 > A2 > A3 > A4 > A5 > ? > An .

Consider an array - 

int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 )

The Array sorted in ascending order will be given as;

A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }

There are many techniques by using which, sorting can be performed. In this section of the tutorial, we will discuss each method in detail.

---

 

Sorting Algorithms

Sorting algorithms are described in the following table -

SN	Algorithms
1	Bubble Sort
2	Insertion Sort
3	Selection Sort
4	Merge Sort
5	Quick Sort
6	Bucket Sort
7	Heap Sort
8	Radix Sort
9	Counting Sort
10	Comb Sort
11	Shell Sort

 

Bubble Sort

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are not in the intended order. Just like the movement of air bubbles in the water that rise up to the surface, each element of the array move to the end in each iteration. Therefore, it is called a bubble sort. 

import java.util.*; import java.lang.*; import java.io.*; class Codechef { public static void main (String[] args) throws java.lang.Exception { // your code goes here int[] a = {4,6,2,8,9,4,6}; // task is to sort in ascending and descending sortBubbleAsc(a); System.out.println(Arrays.toString(a)); sortBubbleDesc(a); System.out.println(Arrays.toString(a)); } public static void sortBubbleAsc(int[] a) { for(int i=0; i<a.length; i++) { for(int j=0; j<a.length-1-i; j++) { if(a[j]>a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } public static void sortBubbleDesc(int[] a) { for(int i=0; i<a.length; i++) { for(int j=0; j<a.length-1-i; j++) { if(a[j]<a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } }

1. Time Complexities

• Worst Case Complexity: O(n2)
  If we want to sort in ascending order and the array is in descending order then the worst case occurs.
• Best Case Complexity: O(n)
  If the array is already sorted, then there is no need for sorting.
• Average Case Complexity: O(n2)
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

2. Space Complexity

• Space complexity is O(1) because an extra variable is used for swapping.
• In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be O(2).

Bubble Sort

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are not in the intended order. Just like the movement of air bubbles in the water that rise up to the surface, each element of the array move to the end in each iteration. Therefore, it is called a bubble sort. 

import java.util.*; import java.lang.*; import java.io.*; class Codechef { public static void main (String[] args) throws java.lang.Exception { // your code goes here int[] a = {4,6,2,8,9,4,6}; // task is to sort in ascending and descending sortBubbleAsc(a); System.out.println(Arrays.toString(a)); sortBubbleDesc(a); System.out.println(Arrays.toString(a)); } public static void sortBubbleAsc(int[] a) { for(int i=0; i<a.length; i++) { for(int j=0; j<a.length-1-i; j++) { if(a[j]>a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } public static void sortBubbleDesc(int[] a) { for(int i=0; i<a.length; i++) { for(int j=0; j<a.length-1-i; j++) { if(a[j]<a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } }

1. Time Complexities

• Worst Case Complexity: O(n2)
  If we want to sort in ascending order and the array is in descending order then the worst case occurs.
• Best Case Complexity: O(n)
  If the array is already sorted, then there is no need for sorting.
• Average Case Complexity: O(n2)
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

2. Space Complexity

• Space complexity is O(1) because an extra variable is used for swapping.
• In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be O(2).

Bubble Sort

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are not in the intended order. Just like the movement of air bubbles in the water that rise up to the surface, each element of the array move to the end in each iteration. Therefore, it is called a bubble sort. 

import java.util.*; import java.lang.*; import java.io.*; class Codechef { public static void main (String[] args) throws java.lang.Exception { // your code goes here int[] a = {4,6,2,8,9,4,6}; // task is to sort in ascending and descending sortBubbleAsc(a); System.out.println(Arrays.toString(a)); sortBubbleDesc(a); System.out.println(Arrays.toString(a)); } public static void sortBubbleAsc(int[] a) { for(int i=0; i<a.length; i++) { for(int j=0; j<a.length-1-i; j++) { if(a[j]>a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } public static void sortBubbleDesc(int[] a) { for(int i=0; i<a.length; i++) { for(int j=0; j<a.length-1-i; j++) { if(a[j]<a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } }

1. Time Complexities

• Worst Case Complexity: O(n2)
  If we want to sort in ascending order and the array is in descending order then the worst case occurs.
• Best Case Complexity: O(n)
  If the array is already sorted, then there is no need for sorting.
• Average Case Complexity: O(n2)
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

2. Space Complexity

• Space complexity is O(1) because an extra variable is used for swapping.
• In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be O(2).