Sorting Algorithms unleashed : A step by step Approach #2
Howdy !!!, Hoping you are doing good in your coding journey. I am here again with the 2nd part of the series Sort Algorithms.
In this part, we will cover the remaining two sorting techniques :
1) Insertion sort
2) Cyclic Sort
Note : you should have a good knowledge and logical understanding of loops to perform these algorithms.
1. INSERTION SORT
> INTRODUCTION> OVERVIEW> STEP-BY-STEP APPROACH> CODE> EXPLANATION FILE
Introduction
talking about insertion sort, this sorting technique includes placing the element of the array at correct index. After every iteration, each element of the array is placed at correct index. giving us the sorted array at the end, lets see a little overview of this technique that how we are going to perform this sort.
Overview
like previous sorts, the core method is to swap two elements. After each pass, the elements on the left side of array will be sorted. This process continues iteration for each element in the array, gradually building a fully sorted array either in ascending or descending order.
Step-by-step Approach
Assume an array : {5,4,3,1,2}
(i) Start with the second element: Begin with the second element (index 1) of the array, considering it as the "j" using nested loops (Given in code).
Example :- when i=0, j will be 1.
(ii) Swap : if element at jth index is greater than element at ith index, swap the elements. otherwise, break the loop.
(iii) Array Traversal : traverse through the array using loops. After every pass, the left side of the array will be sorted.
Example :- after 1st pass, array will look like {4,5,3,1,2}
after 2nd pass, array will look like {4,3,5,1,2} --> {3,4,5,1,2}
(iv) Repeat : step 2 and 3 through the whole loop.
(v) Array is sorted : at the end of loop, the array will be sorted in Ascending or Descending order.
🖋️ Why the loop will break in step 2, if the ith element is not greater than jth element ?
Ans : after each pass, if the swap is not executing, then it means the current left side is already sorted. if swap will still happen, it will take extra time for sort.
Code
import java.util.*;
class InsertionSort {
static void sortAsc(int[] arr){
for(int i=0; i<arr.length-1;i++){
for(int j=i+1; j>0; j--){
if(arr[j] < arr[j-1]){
swapp(arr,j,j-1); //swap arr[j] with arr[j-1]
}else{
break;
}
}
}
System.out.print(Arrays.toString(arr));
}
static void sortDsc(int[] arr){
for(int i=arr.length-2; i>=0; i--){
for(int j=i+1; j>0; j--){
if(arr[j]>arr[j-1]){
swapp(arr,j,j-1);
}else{
break;
}
}
}
System.out.print(Arrays.toString(arr));
}
static void swapp(int[] arr,int first,int second){
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
public static void main(String args[]){
int[] arr1 = {9,5,8,6,1};
int[] arr2 = {5,3,4,1,2};
sortAsc(arr1);
System.out.println();
sortDsc(arr2);
}
}
Explanation file
2. CYCLIC SORT
> INTRODUCTION> OVERVIEW> STEP-BY-STEP APPROACH> CODE> EXPLANATION FILE
Introduction
Moving ahead to Cyclic sort, it is a little bit different and moreover enhanced technique to sort our data more efficiently. In this sort, the basic method of sorting will be swapping elements BUT in a totally different way. let's see an overview of this technique :-
Overview
LET AN ARRAY : {2,4,3,1,5,7,6}
Assume we have sorted the array, it will look like {1,2,3,4,5,7,6}. Starting from 0th index, the element is 1. At 1st index the element is 2 and so on. If we notice, the array is following a general relation between index and element.
(index of the element) = (element at that index) - 1
example : for 2nd index, the element is 3.
🖋️NOTE : we can only apply this sort, when the array have elements from 0 to N or 1 to N.
for 0 to N, the relation will be like index = element.
following this relation, we can sort the whole array by putting the element at its correct index.
let's see step by step, how we can do this :-
STEP-BY-STEP APPROACH
LET AN ARRAY : {3,5,4,1,2}
(i) Initialize the loop variable : define a variable i set to 0, we are gonna use in our loop to traverse the array.
(ii) Correct Index : find the correct index of the element at 0th index using the above relation.
Example : correct index of 3 will be
index = 3 - 1 ==> 2
(iii) Swap : check if the swap is needed, swap the element with the element at its correct index. otherwise move on to next pass and increment i variable.
Example : 3 should be at 2nd index,
after swap, the array will look like {3,5,3,1,2}.
(iv) Array is Sorted : after checking all the elements, placing them at their correct indices, we will get the sorted array at the end.
Code
class cycle{
static void swapp(int[] arr,int first,int second){
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
static void CycSort(int[] arr){
int i=0;
while(i<arr.length){
int correctIndex = arr[i]-1;
if(arr[correctIndex] != arr[i]){
swapp(arr,correctIndex,i);
}else{
i++;}
}
System.out.print(Arrays.toString(arr));
}
public static void main(String args[]){
int[] arr1 = {2,4,3,1,5,7,6};
CycSort(arr1);
}
}
Explanation File
Conclusion
Insertion sort and cyclic sort are made to reduce both time and space complexity of our code. both of the techniques. we've uncovered the power of these sorting algorithms, These foundational techniques, while not ideal for massive datasets, serve as invaluable building blocks for your programming journey. By mastering them, you're better equipped to tackle diverse coding challenges with confidence.
TO BE CONTINUED...
HAPPY CODING :)
Post a Comment