Sorting in Java || Java + DSA course || Blog 9

In this Blog we will be learning about Bubble sort , Selection sort and Insertion sort.

We just sort arrays in ascending or descending order.

The main thing we are going to from sorting is the logic behind it.

Bubble Sort

In this sort we push the heaviest element at the end during each loop.

It checks itself with its front one to check if it is bigger than it, if it is , it swaps places with that particular number. If not then it doesn't change.

Lets start solving:

array  = 21, 16, 13, 5, 54

1st Loop:

21> 16 == True .It swaps places with 16.Array now is {16,21,13,5,54}

21>13 == True. It swaps with 13. Array now is {16,13, 21,5,54}

21> 5 == True. It  swaps with 5. Array now is {16,13,5, 21,54}

21>54 == False.Keep it as it is

 

Now, array is {16,13,5, 21,54} in first Loop

Here 54 is already sorted so you don't need to sort it in another loops

Lets run 2nd loop

 

2nd Loop:

16> 13 == True. swaps with 13. {13,16,5, 21,54}

16> 5 == True. swaps with 5. {13,5,16, 21,54}

16>21 == False

No need to do 21>54

Now 21 is also sorted.

The array here is  {13,5,16, 21,54}

Lets run 3rd loop:

 

3rd Loop:

13>5 == True. Swap. {5,13,16,21,54}

13>16 == False

16 is sorted

No need to do 16>21

Now array is  {5,13,16,21,54}

 

4th Loop:

5>13 == False 

No need for 13> 16 since 16 is already sorted.

After swaping heaviest ints at back, the remaining one will always be the lightest.

So the answer is  {5,13,16,21,54}

array.length was 5 ints. We ran 4 loops to sort it. So we will run loops till array.length-1 . 

Lets code it.

 

public class Main{

public static void printingArray(int arr[]){//prints array

for(int i = 0; i< arr.length;i++){//needs loop

System.out.print(arr[i] + " ");

}

System.out.println();

}

public static void main(String args[]){

int arr[] = {21, 16, 13, 5, 54};//array for bubble sort

for(int i=0; i<arr.length-1; i++){//runs arr.length-1 times the loop

for(int j=0; j<arr.length-i-1; j++){//stops checking the sorted heavy elements

if(arr[j] > arr[j+1]){//comparison

//actual swaping

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

//as similar as;a=1 b=2;

//simple swaping:c=b, b=a, a=c

}

}

}

printingArray(arr);//calling a function to print the array

}

}

Selection Sort

Indexes of array values are used widely in it.

It takes light element to the front. One swaps per iteration.

1st Loop;

Let smallest be 21;

21>16 = Yes.Change it to smallest.smallest = 16

16>13 = Yes.Change it to smallest.smallest = 13

13>5  = Change it to smallest.smallest = 5

5>54 = No. Keep it

 5 was the last changed smallest digit number here.

Swap it with index 0

Now array is {5, 16, 13, 21, 54}  

Loop 2:

Don't check with 5

Smallest = 16

16>13 = Yes. smallest = 13

13>21 =No

13>54 = No. Keep it

Now array {5, 13, 16,21, 54}

Don't check till 13

 

Loop 3:

smallest = 16

16>21 = no

16>54 = no

Now array {5, 13, 16,21, 54}. Here, 16 is sorted

 

Loop 4:

smallest =21

21>54 = no

Now array is in ascending order{5, 13, 16, 21, 54}

Lets code it:

public class Main{

public static void printingArray(int arr[]){//prints array

for(int i = 0; i< arr.length;i++){//needs loop

System.out.print(arr[i] + " ");

}

System.out.println();

}

public static void main(String args[]){

int arr[] = {21, 16, 13, 5, 54};//array for bubble sort

for(int i=0; i<arr.length-1; i++){//runs arr.length-1 times the loop

int smallest = i;//taking i index value as the smallest

for(int j=i+1; j<arr.length; j++){//checking after the sorted elements.

if(arr[smallest] > arr[j]){//comparison

smallest = j;//taking its index as smallest

}

}

//swaping

int temp = arr[smallest];

arr[smallest] = arr[i];

arr[i] = temp;

}

printingArray(arr);//calling a function to print the array

}}

Insertion Sort

It divides array into two parts as sorted and unsorted. Number at index 0  is taken as sorted. Each number in unsorted is compared and then shifted in sorted group .

array = { 21, 16, 13, 5, 54}

Loop 1:

Sorted part has 21.

21<16 = no

(making space)___,21. Since no number to compare with it shifts at space

16,21 is sorted 

 

Loop 2:

16,    21<13 = no

16, ___, 21<13. so 16<13 = no

___, 16,21<13. no number to compare. shift it there

13,16,21 are sorted

 

Loop 3:

13,16,     21<5 = no

13,16,___,21<5. 16<5 = no

13,___,16,21<5. 13>5 = no

___,13,16,21<5.no number to compare. shift there

5,13,16,21 are sorted

 

Loop 4:

5,13,16,    21<54 = yes

Done

Sorted array = 5,13,16,21,54

Lets code it:

public class Main{

public static void printingArray(int arr[]){

for(int i = 0; i< arr.length;i++){

System.out.print(arr[i] + " ");

}

System.out.println();

}

public static void main(String args[]){

int arr[] = {21, 16, 13, 5, 54};

for(int i=1; i<arr.length; i++){//index 0 is in sorted part, so unsorted starts from1

int current = arr[i];

int j = i-1;

while(j >=0 && current < arr[j] ){//j should be more or = 0 and if unsorted number is less than sorted

//value, make some sapce

arr[j+1] = arr[j];//making space

j--;//iterate backwards in sorted part

}

//placing it

arr[j+1] = current;

}

printingArray(arr);

}}

 ____________________________________________________________________________________

Checkout:https://javaanddsa.blogspot.com/

Did you like our blog 9??

Tell us in the comment section