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
Using SQL JOINS
+----+--------------+-------+---------------+------+ | ID | ITEM_ORDERED | PRICE | PURCHASE_DATE | C_ID | +----+--------------+-------+---------------+------+ | 1 | APPLE WATCH | 35000 | 2018-05-15 | 1 | | 2 | IPHONE | 55000 | 2018-05-25 | 2 | | 3 | IPHONE | 55000 | 2018-05-25 | 5 | | 4 | IPHONE | 55000 | 2018-05-25 | 3 | | 5 | MACBOOK | 59000 | 2018-05-25 | 4 | | 6 | MACBOOK | 59000 | 2018-05-25 | 1 | | 7 | MACBOOK | 59000 | 2018-05-25 | 6 | +----+--------------+-------+---------------+------+ 7 rows in set (0.00 sec)
mysql> SELECT * FROM CUSTOMER; +----+--------+---------+------+-----------+---------------------+ | ID | FNAME | LNAME | AGE | COUNTRY | CREATION_DATE | +----+--------+---------+------+-----------+---------------------+ | 1 | AKSHAY | KUMAR | 12 | INDIA | 2018-05-23 00:16:35 | | 2 | JONTY | RHODES | 40 | CHINA | 2018-05-18 12:21:12 | | 3 | JOHNY | DEPP | 45 | INDIA | 2018-05-23 00:16:35 | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | 2018-05-18 12:21:12 | | 5 | JESSIE | JACKSON | 22 | CANADA | 2018-05-23 00:16:35 | | 6 | NICOLE | KIDMAN | 50 | USA | 2018-05-18 12:21:12 | +----+--------+---------+------+-----------+---------------------+ 6 rows in set (0.00 sec)Now from above two tables we cannot get much information about the purchase unless we see both the tables together ans try to consolidate the data. So in order to get data from both these tables based on some common data we use SQL JOINS
SQL JOINS syntax with example -
Suppose we want to get the details of orders made by customers we can use the following SQL statement -SELECT C.*, O.* FROM CUSTOMER AS C INNER JOIN ORDERS AS O ON C.ID = O.C_ID;
+----+--------+---------+------+-----------+---------------------+----+--------------+-------+---------------+------+ | ID | FNAME | LNAME | AGE | COUNTRY | CREATION_DATE | ID | ITEM_ORDERED | PRICE | PURCHASE_DATE | C_ID | +----+--------+---------+------+-----------+---------------------+----+--------------+-------+---------------+------+ | 1 | AKSHAY | KUMAR | 12 | INDIA | 2018-05-23 00:16:35 | 1 | APPLE WATCH | 35000 | 2018-05-15 | 1 | | 1 | AKSHAY | KUMAR | 12 | INDIA | 2018-05-23 00:16:35 | 6 | MACBOOK | 59000 | 2018-05-25 | 1 | | 2 | JONTY | RHODES | 40 | CHINA | 2018-05-18 12:21:12 | 2 | IPHONE | 55000 | 2018-05-25 | 2 | | 3 | JOHNY | DEPP | 45 | INDIA | 2018-05-23 00:16:35 | 4 | IPHONE | 55000 | 2018-05-25 | 3 | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | 2018-05-18 12:21:12 | 5 | MACBOOK | 59000 | 2018-05-25 | 4 | | 5 | JESSIE | JACKSON | 22 | CANADA | 2018-05-23 00:16:35 | 3 | IPHONE | 55000 | 2018-05-25 | 5 | | 6 | NICOLE | KIDMAN | 50 | USA | 2018-05-18 12:21:12 | 7 | MACBOOK | 59000 | 2018-05-25 | 6 | +----+--------+---------+------+-----------+---------------------+----+--------------+-------+---------------+------+ 7 rows in set (0.06 sec)Here we can see that we have merged the rows of both CUSTOMERS and ORDERS tables and got the details of ORDERS made by each customer in a single table form.
You can notice that in the above example we have used INNER join, similarly there some other kind of joins that are used to combine the tables data in different scenarios.
SQL type of JOINS and their usage -
MySQl supports the following joins -1. INNER JOIN
2. LEFT JOIN
3. RIGHT JOIN
4. CROSS JOIN
MySQl does not support OUTER JOIN. We will learn about these joins and their usages in next tutorials.
Using SQL ALIAS
mysql> SELECT * FROM CUSTOMER; +----+--------+---------+------+-----------+---------------------+ | ID | FNAME | LNAME | AGE | COUNTRY | CREATION_DATE | +----+--------+---------+------+-----------+---------------------+ | 1 | AKSHAY | KUMAR | 12 | INDIA | 2018-05-23 00:16:35 | | 2 | JONTY | RHODES | 40 | CHINA | 2018-05-18 12:21:12 | | 3 | JOHNY | DEPP | 45 | INDIA | 2018-05-23 00:16:35 | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | 2018-05-18 12:21:12 | | 5 | JESSIE | JACKSON | 22 | CANADA | 2018-05-23 00:16:35 | | 6 | NICOLE | KIDMAN | 50 | USA | 2018-05-18 12:21:12 | +----+--------+---------+------+-----------+---------------------+ 6 rows in set (0.00 sec)
SQL ALIAS syntax for columns names and example -
SELECT FNAME AS FIRST_NAME, LNAME AS LAST_NAME FROM CUSTOMER;
mysql> SELECT FNAME AS FIRST +------------+-----------+ | FIRST_NAME | LAST_NAME | +------------+-----------+ | AKSHAY | KUMAR | | JONTY | RHODES | | JOHNY | DEPP | | JESSIE | PINKMAN | | JESSIE | JACKSON | | NICOLE | KIDMAN | +------------+-----------+ 6 rows in set (0.00 sec)Using above query we have named FNAME column as FIRST_NAME and LNAME column as LAST_NAME. These names are temporary and exists only for the duration of the query.
Using MySQl ALIAS names separated with spaces -
To use space separated ALIAS names like FIRST NAME we need to use quotes around the alias name.SELECT FNAME AS 'FIRST NAME', LNAME AS 'LAST NAME' FROM CUSTOMER;
+------------+-----------+ | FIRST NAME | LAST NAME | +------------+-----------+ | AKSHAY | KUMAR | | JONTY | RHODES | | JOHNY | DEPP | | JESSIE | PINKMAN | | JESSIE | JACKSON | | NICOLE | KIDMAN | +------------+-----------+ 6 rows in set (0.00 sec)
SQL ALIAS from table names syntax and example -
SELECT C.FNAME, C.AGE FROM CUSTOMER AS C;
+--------+------+ | FNAME | AGE | +--------+------+ | AKSHAY | 12 | | JONTY | 40 | | JOHNY | 45 | | JESSIE | 25 | | JESSIE | 22 | | NICOLE | 50 | +--------+------+ 6 rows in set (0.00 sec)In above example you won't see much use of using ALIAS but it would be very helpful when we will use more than one table in a single query which we will see in our next few tutorials specially while using JOINS.
Using SQL BETWEEN operator
mysql> SELECT * FROM CUSTOMER; +----+--------+---------+------+-----------+---------------------+ | ID | FNAME | LNAME | AGE | COUNTRY | CREATION_DATE | +----+--------+---------+------+-----------+---------------------+ | 1 | AKSHAY | KUMAR | 12 | INDIA | 2018-05-23 00:16:35 | | 2 | JONTY | RHODES | 40 | CHINA | 2018-05-18 12:21:12 | | 3 | JOHNY | DEPP | 45 | INDIA | 2018-05-23 00:16:35 | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | 2018-05-18 12:21:12 | | 5 | JESSIE | JACKSON | 22 | CANADA | 2018-05-23 00:16:35 | | 6 | NICOLE | KIDMAN | 50 | USA | 2018-05-18 12:21:12 | +----+--------+---------+------+-----------+---------------------+
SQL BETWEEN operator syntax and example -
Suppose we want to get the customers with age between 18 to 40, we can use the following statement.SELECT * FROM CUSTOMER WHERE AGE BETWEEN 18 AND 40;
mysql> SELECT * FROM CUSTOMER; +----+--------+---------+------+-----------+---------------------+ | ID | FNAME | LNAME | AGE | COUNTRY | CREATION_DATE | +----+--------+---------+------+-----------+---------------------+ | 2 | JONTY | RHODES | 40 | CHINA | 2018-05-18 12:21:12 | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | 2018-05-18 12:21:12 | | 5 | JESSIE | JACKSON | 22 | CANADA | 2018-05-23 00:16:35 | +----+--------+---------+------+-----------+---------------------+ 3 rows in set (0.00 sec)Here we can see that we have got customers with age between 18 and 40. (inclusive 18 and 40 as mentioned earlier).
SQL BETWEEN operator syntax and example for dates -
To get customers with creation date between 18 and 23 May (inclusive these dates).Using SQL IN operator
mysql> SELECT * FROM CUSTOMER; +----+--------+---------+------+-----------+ | ID | FNAME | LNAME | AGE | COUNTRY | +----+--------+---------+------+-----------+ | 1 | AKSHAY | KUMAR | 12 | INDIA | | 2 | JONTY | RHODES | 40 | CHINA | | 3 | JOHNY | DEPP | 45 | INDIA | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | | 5 | JESSIE | JACKSON | 22 | CANADA | | 6 | NICOLE | KIDMAN | 50 | USA | +----+--------+---------+------+-----------+ 6 rows in set (0.00 sec)
SQL IN operator syntax with example -
Suppose we want to get the rows where country is INDIA, USA and CANADA, we can use it in two ways -1. Using multiple OR with WHERE clause
SELECT * FROM CUSTOMER WHERE COUNTRY = 'INDIA' OR COUNTRY = 'USA' OR COUNTRY = 'CANADA';1. Using IN operator with WHERE clause
SELECT * FROM CUSTOMER WHERE COUNTRY IN ('INDIA', 'USA', 'CANADA');
And we will get the same results, but IN operator is a little handy in such scenarios.
+----+--------+---------+------+---------+ | ID | FNAME | LNAME | AGE | COUNTRY | +----+--------+---------+------+---------+ | 1 | AKSHAY | KUMAR | 12 | INDIA | | 3 | JOHNY | DEPP | 45 | INDIA | | 5 | JESSIE | JACKSON | 22 | CANADA | | 6 | NICOLE | KIDMAN | 50 | USA | +----+--------+---------+------+---------+ 4 rows in set (0.00 sec)Also remember that using IN operator we can set restriction only for one column with one IN for setting restrictions on some other columns we will have to use OR operator again.
Using SQL LIKE operator
This LIKE operator is used with some WILDCARDS.
% - (Percentage sign)It is used to represent zero, one or multiple characters.
_ - (underscore) It is used to represent single character.
SQL LIKE operator syntax and example -
Suppose we want to get the rows with FNAME starting with 'J', we can use the following statement -SELECT * FROM CUSTOMER WHERE FNAME LIKE 'J%';
+----+--------+---------+------+-----------+ | ID | FNAME | LNAME | AGE | COUNTRY | +----+--------+---------+------+-----------+ | 2 | JONTY | RHODES | 40 | CHINA | | 3 | JOHNY | DEPP | 45 | INDIA | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | | 5 | JESSIE | JACKSON | 22 | CANADA | +----+--------+---------+------+-----------+ 4 rows in set (0.00 sec)Similarly we use LIKE operator with these wildcards in different ways.
Using SQL LIMIT in MySql
+----+--------+---------+------+-----------+ | ID | FNAME | LNAME | AGE | COUNTRY | +----+--------+---------+------+-----------+ | 1 | AKSHAY | KUMAR | 12 | INDIA | | 2 | JONTY | RHODES | 40 | CHINA | | 3 | JOHNY | DEPP | 45 | INDIA | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | | 5 | JESSIE | JACKSON | 22 | CANADA | | 6 | NICOLE | KIDMAN | 50 | USA | +----+--------+---------+------+-----------+ 6 rows in set (0.00 sec)
MySQL LIMIT syntax and example -
Suppose from the above table we just want to get the top 4 results, we can use the following given statement -SELECT * FROM CUSTOMER LIMIT 4;
+----+--------+---------+------+-----------+ | ID | FNAME | LNAME | AGE | COUNTRY | +----+--------+---------+------+-----------+ | 1 | AKSHAY | KUMAR | 12 | INDIA | | 2 | JONTY | RHODES | 40 | CHINA | | 3 | JOHNY | DEPP | 45 | INDIA | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | +----+--------+---------+------+-----------+ 4 rows in set (0.00 sec)We can see that we have got just first 4 rows for the given query.
MySQL LIMIT with offset value syntax and example -
Suppose we don't want to get top some values but we want to get 3 values from second row, we can set offset 1 and then we will get values from 2nd row.SELECT * FROM CUSTOMER LIMIT 1,3;
+----+--------+---------+------+-----------+ | ID | FNAME | LNAME | AGE | COUNTRY | +----+--------+---------+------+-----------+ | 2 | JONTY | RHODES | 40 | CHINA | | 3 | JOHNY | DEPP | 45 | INDIA | | 4 | JESSIE | PINKMAN | 25 | AUSTRALIA | +----+--------+---------+------+-----------+ 3 rows in set (0.00 sec)Here we can see that we have got 3 values starting from 2nd row and we have left 1 row from the top.