Sorting Algorithms unleashed : A step by step Approach #1
Hello coders !!, Imagine having an array of numbers in your Java program, all jumbled up like a mixed-up puzzle. How do you arrange them in order? That's where sorting algorithms swoop in. In this beginner-friendly tutorial, we'll unravel the magic behind these algorithms, step by step, as we turn disorder into harmony in your code.
Earlier, we discussed about search algorithms, in which we learnt about linear search and binary search.
Have a look and take a quick revision : https://codingatess.blogspot.com/search/label/search%20algorithms?&max-results=10
So now you know how to find any element in an array or string, its time to go a level up :) , searches includes finding the element in sorted lists, though we have linear search for unsorted lists, but then the main issue arises, TIME COMPLEXITY.
To resolve this issue, Today we will learn to sort these lists to reduce the time and space complexity of our code. SO LET'S START !!!
Sort Algorithms includes 4 types :-
1. Bubble sort
2. Selection sort
3. Insertion sort
4. Cyclic sort
Out of these 4, today we will learn about Bubble sort and Selection sort.
Note : you should have good logical understanding of LOOPS to perform and understand these algorithms.
1. BUBBLE SORT
> INTRODUCTION
> OVERVIEW
> STEP-BY-STEP APPROACH
> CODE
> EXPLANATION FILE
Introduction
Bubble Sort is often the first stop. It might not be the fastest one, but its simplicity makes it an excellent introduction to the concept of sorting. Also, it is the easiest one among four of them.
Overview
At its core, Bubble Sort is all about comparing and swapping adjacent elements until the entire array is sorted. Imagine a bubble rising through a liquid, gradually pushing the larger bubbles to the surface. Similarly, in Bubble Sort, the larger elements get indexed to their correct positions in the array over multiple passes.
Step-by-Step Approach
imagine an Array, nums = {33,78,65,34,11}
(i) Comparison of Adjacent Elements: Begin by comparing the first two array elements . If the first is greater, swap them.
example : 33 < 78, then don't swap
78 > 65, swap
(ii) Traversal Through the Array: Proceed to the next element pair, continuing comparisons and swaps. Repeat until reaching the array's end.
example : after 1st pass, the array looks like this {33,78,65,34,11}
after 2nd pass, the array should look like this {33,65,78,34,11}
(iii) Completion of One Pass: After each pass, the largest element finds its way to the last position. now, the array should be sorted in Ascending order.
(iv) Array is sorted : now the array is sorted in Ascending order. Similarly, we can sort the array in descending order by modifying some changes in code.
Code
import java.util.*;
class bubblesort{
static void sortDescending(int[] arr){ // sort array in Descending order
for(int i=0; i < arr.length; i++){
for(int j=1; j<arr.length-i; j++){
if(arr[j] > arr[j-1]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
System.out.print(Arrays.toString(arr)); //this will print the array in the form [...]
System.out.println();
}
static void sortAscending(int[] arr){ // sort array in ascending order
for(int i=arr.length-1; i >=0; i--) {
for (int j = arr.length - 2; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.print(Arrays.toString(arr)); //this will print the array in the form [...]
}
public static void main(String args[]){
int[] arr1 = {33,78,65,34,11};
int[] arr2 = {34,76,85,29,23};
System.out.println("Descending order");
sortDescending(arr1);
System.out.println("Ascending order");
sortAscending(arr2);
}
}
Explanation file
2. SELECTION SORT
> INTRODUCTION
> OVERVIEW
> STEP-BY-STEP APPROACH
> CODE
> EXPLANATION FILE
Introduction
moving to selection sort, this sorting method technique includes a more efficient way to sort the array in desired order. lets take a look on the same...
Overview
Selection Sort works by dividing the array into two portions: sorted and unsorted. In each iteration, it finds the index of last element in the unsorted part of array and swaps the element with the correct index. This gradually builds the sorted portion of the array.
Step-By-Step Approach
Assume an array nums = {5,9,6,3,1}
(i) Last Element Index : find the index of last element of the unsorted part of the array i.e. initially the index of last element.
example : here, last element is 1 having index 4.
(ii) Max Element Index : find the index of element having maximum value among all the elements of the array.
example : here, element with max. value is 9 having index 1.
(iii) Swap : swap the Maximum element Index with Last element index.
example : 9 and 1 will be swapped. now the array should look like this, {5,1,6,3,9}
(iv) Repeat step 1, 2 and 3 : after each pass, the largest element will be swapped with last index element of the unsorted part of the array.
example : after 1st pass, the array will look like this {5,1,6,3,9}
after 2nd pass, the array will look like this {5,1,3,6,9}
(v) Array is sorted : now the array is sorted in Ascending order. Similarly, we can sort the array in descending order by modifying some changes in code.
CODE
import java.util.*;
class SelectionSort {
static void selectsortDsc(int[] arr){ //sort array in Descending order
for(int i=0; i<arr.length; i++) {
int FirstElementIndex = i; //index of First Element after each step
int MaxIndex = MaxIndex(arr,i,arr.length-1); // index of maximum value, in the remaining unsorted array
swapp(arr,MaxIndex,FirstElementIndex);
}
System.out.print(Arrays.toString(arr));
}
static void selectsortAsc(int[] arr){ //sort array in Ascending order
for(int i=0; i<arr.length; i++){
int LastElementIndex = arr.length-i-1; //index of last Element after each step
int MaxIndex = MaxIndex(arr,0,LastElementIndex); // index of maximum value, in the remaining unsorted array
swapp(arr,MaxIndex,LastElementIndex);
}
System.out.print(Arrays.toString(arr));
}
static int MaxIndex(int[] arr,int start,int end){
int MaxInd = start;
for(int i=start; i<=end; i++){
if(arr[MaxInd] < arr[i]){
MaxInd = i;
}
}
return MaxInd;
}
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 = {5,9,6,3,1};
System.out.println("Ascending order");
selectsortAsc(arr1);
System.out.println();
System.out.println("Descending order");
selectsortDsc(arr1);
}
}
Explanation file
CONCLUSION
Bubble Sort and selection sort are not the most efficient sorting algorithm, Though mastering them will not only familiarize you with sorting principles but also train you for tackling advanced coding challenges with confidence. they may be not the best choice if you are sorting a large database, but they gives a good kick start when you are about to start sort algorithms.
TO BE CONTINUED...
In the next part, we will learn about Insertion sort and cyclic sort. they are more efficient and faster than bubble and selection sort.
we will also discuss about the pros and cons of using/not using bubble sort and selection sort. why there's a need for insertion and cyclic sort, although the result is same in all of them.
HAPPY CODING :)
Post a Comment