Merge Sort - Sorting Algorithms
Merge sort is a divide and conquer algorithm where we divide the given array into two halves and then merge them assuming that the divided sub arrays are sorted.
In merge sort we keep dividing the array and its subarrays until there is only one element left in the subarray and an array with only one element is always sorted.
After an array is divided into two halves we use the merge function to merge both array in such a way that the merged array is sorted.
Thus there are two methods used one is used to divide the array and another one is used to merge the divided array. The real magic for array sorting happens in the merge method.
Let’s try to understand the the Merge sort with the help of an example -
Suppose we want to sort an array in ascending order - {12, 1,11,4,3,2,44,5,455,76,87,43,45, 55}
Step 1. Dividing into two halves or almost two halves -
Length of the array is 14 so we can divide it into two subarrays having 7 elements each.
{12, 1,11,4,3,2,44} and {5,455,76,87,43,45, 55}
Now these two subarrays can be divided further into two halves, because we cannot merge them until they are sorted.
So we will keep dividing them until we have subarray which has only one element because an array with one element is always sorted.
Now we can start merging the subarrays because now they are sorted.
Step 2. Merging the sorted sub arrays -
To merge the elements of two sorted arrays we will compare the corresponding elements of both the arrays and choose the smaller element and put it in the merged array.
Once all the elements of any one of the arrays are exhausted , we will then simply insert all the remaining elements of the another array in the merged array if there are any elements left in the sub array
Example -
Suppose we have two sorted subarrays - {1,22 33,41} - {7,66,89,90}
Compare 1 with 7, since 1< 7 put 7 in the merged array
Merged array - 1
Compare 22 with 7, since 7 < 22 , put 7 in the merged array
Merged array - 1, 7
Compare 22 with 66, since 22 < 66 , put 22 in the merged array
Merged array - 1, 7, 22
And so on..
Let’s write a Java program for Merge Sort using Recursion :
package algo.sorting;
public class MergeSort {
public static void main(String args[]) {
int[] arr = new int[] { 12, 1, 11, 4, 3, 2, 44, 5, 455, 76, 87, 43, 45,
55 };
System.out.println("Unsorted Array - ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
System.out.println("Sorted Array after Merge Sort - ");
sort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void sort(int[] arr, int l, int r) {
if (l < r) {
// int m = l + (r-l)/2;
int m = (l + r) / 2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public static void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int left[] = new int[n1];
int right[] = new int[n2];
for (int i = 0; i < n1; i++) {
left[i] = arr[l + i];
}
for (int i = 0; i < n2; i++) {
right[i] = arr[m + 1 + i];
}
int i = 0;
int j = 0;
int k = l;
while (i < n1 && j < n2) {
if (left[i] < right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = left[i];
i++;
k++;
}
while (j < n2) {
arr[k] = right[j];
j++;
k++;
}
}
}
Output -
Unsorted Array - 12 1 11 4 3 2 44 5 455 76 87 43 45 55 Sorted Array after Merge Sort - 1 2 3 4 5 11 12 43 44 45 55 76 87 455
Bubble Sort - Sorting Algorithms
In bubble sort we compare adjacent elements of the array and swap them to maintain the sorting order.
So if we are trying to sort the element in the ascending order then in each iteration the largest element is moved to the rightmost position of the unsorted part of the array.
Let’s try to understand bubble sort with the help of an example -
Suppose we want to sort an array in ascending order - {12, 11, 23, 1, 23, 65, 33, 25, 87, 57, 6 }
Compare 12 with 11 , since 11 < 12 - swap elements (11 with 12)
{11, 12, 23, 1, 23, 65, 33, 25, 87, 57, 6 }
Compare 12 with 23, since 12 < 23 - no swaping required
{11, 12, 23, 1, 23, 65, 33, 25, 87, 57, 6 }
Compare 23 with 1 , since 1 < 23, swap elements (1 with 23)
{11, 12, 1, 23, 23, 65, 33, 25, 87, 57, 6 }
...
This way after completing the first pass we will see that the largest element has been shifted to the rightmost position of the unsorted part of the array.
After first pass -
11 12 1 23 23 33 25 65 57 6 87
After 2nd pass -
11 1 12 23 23 25 33 57 6 65 87
After 3rd pass -
1 11 12 23 23 25 33 6 57 65 87
After n pass
1 6 11 12 23 23 25 33 57 65 87 - Sorted array
Let’s write a Java program for Bubble Sort :
package algo.sorting;
public class BubbleSort {
public static void main(String args[]) {
int[] arr = new int[] { 12, 11, 23, 1, 23, 65, 33, 25, 87, 57, 6 };
System.out.println("Unsorted Array - ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
arr = sort(arr);
System.out.println();
System.out.println("Sorted Array After Bubble Sort - ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static int[] sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j + 1] < arr[j]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
}
Output -
Unsorted Array - 12 11 23 1 23 65 33 25 87 57 6 Sorted Array After Bubble Sort - 1 6 11 12 23 23 25 33 57 65 87
Selection Sort - Sorting Algorithms
In selection sort algorithm the whole array is divided into two sub arrays one is sorted and another one is unsorted. We find (select) the minimum element form the unsorted sub array and swap it with the element at the starting index of the unsorted sub array. This way this elements becomes a part of the sorted sub array and size of sorted sub array increases by one and unsorted array decreases by one. We keep repeating this process until all the elements in unsorted sub array are exhausted.
Let’s try to understand Selection sort with the help of an example -
Suppose we want to sort an array - {11, 21, 22, 2, 14, 3, 22, 21, 99, 77}
Initially all the elements in the given array are considered in unsorted sub array.
So we will start from the very first element of the array and search the minimum element in this array which is 2 in this case.
Now we will swap the element '2' with the very first element of unsorted sub array which is element '11'.
After swapping the elements our new array will look something like this -
{2, 21, 22, 22, 14, 3, 22, 21, 99, 77}
Now we can see that whole array has been divided into two subarrays with one element (2) in sorted subarray and rest of the elements in the unsorted subarray.
In next iteration we will again find the minimum element in the unsorted sub array and swap it with the first element of the unsorted subarray which is 21. This will again increase the size of sorted sub array by one.
We will keep repeating this process for all the elements of unsorted sub array and in the end we will see that we are left with only one array which is sorted.
Let’s write a Java program for Selection Sort Algorithm :
package algo.sorting;
public class SelectionSort {
public static int[] sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
return arr;
}
public static void main(String args[]) {
int[] arr = { 11, 21, 11, 23, 1, 34, 221, 3, 455, 6 };
System.out.println("Unsorted Array -");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
arr = sort(arr);
System.out.println();
System.out.println("Sorted Array After Selection Sort -");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
Output -
Unsorted Array - 11 21 11 23 1 34 221 3 455 6 Sorted Array After Selection Sort - 1 3 6 11 11 21 23 34 221 455
Insertion Sort - Sorting Algorithms
Insertion sort algorithm - Sorting Algorithms
Insertion sort is a very simple sorting algorithm where we divide the whole array into two sub arrays. Out of these two sub arrays one is always sorted and another one is unsorted. In each iteration we take one element from the unsorted subarray and put it in the sorted sub array at the right place so that sorted sub array remains sorted even after inserting the new element in it.
Initially the length of sorted sub array will be 1 because an array with one element is always sorted and when we start placing the elements of unsorted sub array in the sorted sub array the length of sorted sub array will keep increasing and will reach the length of the entire array when all the elements are sorted.
Let’s try to understand Insertion sort with the help of an example -
Suppose we have an integer array - {11,2,11,3,21,2,34,2,5,6,76,77,8}
Suppose 11 is in the sorted array and rest of the elements are part of unsorted subarray.
Now we will start from index 1 and insert the element ‘2’ in the sorted subarray.
To insert the new element 2 in the sorted sub array at the correct position we will compare it with elements already in the sorted array and insert it at the correct position.
Because 2 is less than 11 so we will swap these two elements in the sorted sub array.
We will repeat the same procedure for all the elements in the unsorted sub array until the whole array is sorted.
Let’s take a look at the java code implementation for Insertion sort of this array -
package algo.sorting;
public class InsertionSort {
public static void main(String args[]) {
int[] arr = new int[] { 11, 2, 11, 3, 21, 2, 34, 2, 5, 6, 76, 77, 8 };
System.out.println("Unsorted Array - ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
arr = sort(arr);
System.out.println();
System.out.println("Sorted Array After Insertion Sort - ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static int[] sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
return arr;
}
}
Output -
Unsorted Array - 11 2 11 3 21 2 34 2 5 6 76 77 8 Sorted Array After Insertion Sort - 2 2 2 3 5 6 8 11 11 21 34 76 77