Sorting Big database : Sorting algorithms #3
Hey Guyz :), hoping that you are doing good in your coding journey. So Now all of you have learnt about sorting the small arrays. the algorithms we learnt were also made to sort our databases.
Take a quick revision : Sorting Algorithms
But what if my list contains a thousand of elements ?
Assume I use bubble sort for this, then it will be very inefficient for me to sort this big list, because of large amount of time and space complexity. Continues loop iterations and swapping will not only take more space in memory heap, but also increase time complexity.
Hence, to solve these large databases, we have two more sorting algorithms :
1) Merge Sort
2) Quick Sort
these sorting techniques use recursion to sort our lists. So, it's obvious that you should have a good knowledge and logical understanding of recursion.
if you want a full tutorial on Recursion, comment down 👇
Today we will learn about Merge sort, we will see :
> INTRODUCTION
> OVERVIEW
> STEP-BY-STEP IMPLEMENTATION
> CODE
> RECURSIVE APPROACH
> EXPLANATION FILE
INTRODUCTION
Merge Sort is a widely used sorting algorithm known for its stable performance and efficiency. It follows the divide-and-conquer paradigm, breaking down the sorting problem into smaller subproblems, solving them, and then merging the solutions back together to obtain the sorted result.
OVERVIEW
In merge sort, we basically divide the array into smaller arrays, Sort those smaller arrays. And then merge those into original but sorted array.
STEP-BY-STEP IMPLEMENTATION
i) Divide into two : take a middle element of the array, and divide the array into two parts to form two new smaller arrays. this can be done by copyOfRange method of Array class.
ii) Conquer smaller arrays : create a new method to sort those new smaller arrays into ascending descending order.
iii) merge smaller arrays : initialize a new array with its length equal to the sum of lengths of smaller arrays. merge smaller arrays into newly initialized array. this can be done by :
(i) compare the 0th index element of both smaller arrays.
(ii) insert the smaller element into new merged array.
(iii) repeat step 1 and 2.
iv) Return the sorted array : Now return the merged array, which is now sorted in ascending order.
CODE
public class MergeSort{
public static void main(String[] args) {
int[] arr = {98,87,76,65,54,43,32,21};
System.out.print(Arrays.toString(mergeSort(arr)));
}
static int[] mergeSort(int[] arr){
if(arr.length == 1){
return arr;
}
int mid = arr.length/2;
int[] left = mergeSort(Arrays.copyOfRange(arr,0,mid));
int[] right = mergeSort(Arrays.copyOfRange(arr,mid,arr.length));
return Merge(left,right);
}
private static int[] Merge(int[] first, int[] second) {
int[] mix = new int[first.length+second.length]; //merged array
int i=0;
int j=0;
int k=0;
while(i<first.length && j<second.length){
if(first[i] < second[j]){
mix[k] = first[i];
i++;
}else{
mix[k] = second[j];
j++;
}
k++;
}
while(i<first.length){ //if elements are left in first array, add them in merged array
mix[k] = first[i];
i++;
k++;
}
while(j<second.length){ //if elements are left in first array, add them in merged array
mix[k] = second[j];
j++;
k++;
}
return mix;
}
}
RECURSIVE APPROACH
(i) when Applying divide and conquer method, we are basically doing steps 1 and 2 again and again using recursion.
(ii) Dividing the original array into 2, then dividing the smaller arrays into 2 and so on.
(iii) Base condition : when only one element is left in the array, we are returning that array with only one element in it.
(iv) after that, we are left with smaller sorted arrays, compare the corresponding elements of both arrays. smaller one will be added to the merged array.
Important Points to remember :
i) Imagine we have arrays with unequal number of elements, after one array is completely emptied and the elements of that array are put into merged array. Then we will add the remaining elements of another array into merged array.
ii) we are not changing the original array, we are making a copy of the original array which is sorted.
EXPLANATION FILE
CONCLUSION
Merge Sort is a stable, comparison-based sorting algorithm that is widely used in practice due to its consistent performance and suitability for various data sizes. It's a great choice when a stable, efficient sorting algorithm is needed.
In next part, we will cover Quick Sort which would be our last sorting algorithm.
HAPPY CODING :)
Post a Comment