what are sorting algorithms in java
Before going to the sorting techniques in Java let us first understand what is the meaning of sorting Sorting is any process of arranging items systematically, ordering elements on the basis of some criteria like arranging elements of a set in ascending or descending order or arranging alphabets of any set in the same order or arranging the words of any set on the basis of length hope it is clear move forward to understand what are the techniques in java for sorting the elements of an array mainly we have three major sorting algorithms which are used most commonly are-
- Insertion sort
- Bubble sort
- Selection sort
we can do sorting either in ascending order or descending order but mostly we will perform sorting in ascending order definitely we will see only ascending order sorting here, In Insertion sort what actually happens is we consider the first element is already sorted and we start checking from the second element, we will check what is the position it will get in the sorted array and place that element at the correct position suppose below is an array of five elements we have to sort using insertion sort-
[5,4,3,2,1]
follow these steps sequentially to sort these elements using insertion sort-
1. here, we can consider 5 is the already sorted element from above discussion we will pick element 4 and search for it's right position in the sorted array which is [5](sorted array) put this element in the right position as shown-
[4,5,3,2,1]
2. now the sorted array becomes [4,5] pick the first element from unsorted array which consists of 3,2,1 is 3(first element) put this element at the right position in the sorted array as shown-
[3,4,5,2,1]
3. element 3 is placed at the correct position in the sorted array now pick the first element from the unsorted array which consists of 2,1 is 2(first element) put this element at the right position in the sorted array as shown-
[2,3,4,5,1]
4. element 2 is placed at the correct position in the sorted array now pick the first element from the unsorted array which consists of 1(only 1 is left) is 1(first element) put this element at the right position in the sorted array as shown-
[1,2,3,4,5]
As you can see that the array is successfully sorted now let's see the how to do this in the code-
Source code- public class Array05 {
//insertion sort
public static void main(String[] args)
{
int a[]= {5,4,3,2,1};
int l=a.length;
for(int i=1;i<l;i++)
{
int key=a[i];
int j=i-1;
while(j>=0 && a[j]>key)
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
for(int each:a) //for each loop for printing array
{
System.out.print(each+" ");
}
}
} Output:
sorted array is:
1 2 3 4 5
Imp.note- here, in this code at the last the array is printed by using for each loop if you want to know what is for each loop click on it and see.
Bubble sort- In bubble sort what actually happens is we compare the first two adjacent elements if first element is found to be greater than the second element we simply swaps both of them similarly after swapping the first two elements we check the 2nd and 3rd element if 2nd element>3rd element we swap it in and so on suppose below is an array of five elements we have to sort using bubble sort-
[5,4,3,2,1]
follow these steps sequentially to sort these elements using bubble sort-
1. first we check the first two elements [5,4] here, 5>4 we swap both elements after swapping the array we will get is-
[4,5,3,2,1]
2. now we check the 2nd and 3rd element [5,3] here, 5>3 we swap both elements after swapping the array we will get is-
[4,3,5,2,1]
3. now we check the 3rd and 4th element [5,2] here, 5>2 we swap both elements after swapping the array we will get is-
[4,3,2,5,1]
[4,3,2,1,5] 5. As you can see that 5 is the largest element among all and it has been placed at it's right position in the array this is called first pass in bubble sort.
6. Similarly you will now do the same procedure for the rest elements n-1 except the last element which is 5 now you have to run a loop on the elements [4,3,2,1] and apply the same procedure checking the adjacent elements like 4,3 and 3,2 so on what will happen in this way your second pass is completed and the second largest element will get it's right position in the sorted array similarly after the third and fourth pass 3rd largest and 4th largest element will get it's right position in the sorted array and last element will automatically gets sorted and whole of the array gets sorted in this way.
Imp.note- If your array has n elements then the total number of passes it will take to sort is n-1.
public class Arary04 {
//bubble sort
public static void main(String[] args)
{
int a[] = {5,4,3,2,1,9,8,7,6,5};
int l=a.length;
int c=1;
for(int i=0;i<l-1;i++)//algorithm section started
{
for(int j=0;j<l-1-i;j++)
{
if(a[j]>a[j+1])
{ //bubble sort algorithm
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
} // algorithm section ended
System.out.println(c+"pass completed"+"\n");
c++;
}
System.out.println("Array is sorted successfully in "+(l-1)+" passes");
for(int each:a)
{
System.out.print(each+" ");
}
}
}
Output:
1pass completed
2pass completed
3pass completed
4pass completed
5pass completed
6pass completed
7pass completed
8pass completed
9pass completed
Array is sorted successfully in 9 passes
1 2 3 4 5 5 6 7 8 9
Selection sort- In selection sort what actually happens is, select the minimum element of the array and swap it with the beginning element of the array, now see the array except the first element and again find the minimum element in the array and swap it with the beginning element in the unsorted array, which is now the array except the first element and again see the array except the first two elements and finds the minimum element and swap it with the beginning element of the unsorted array, which is the array except the first two elements, similarly in this way your array will be sorted let's take an example to understand it more clearly-
this is your array which we will sort by using the selection sorting technique-
[5,4,3,2,1]
Step 1.find the minimum element in the array which is here 1 and swap it with the beginning element which is here 5 after swapping, the array we will get is
[1,4,3,2,5]
Step 2. now find the minimum element in the below array
[4,3,2,5]
which is here 2, swap it with the beginning element in this array which is 4 after swapping, the array we will get is-
[2,3,4,5]
Step 2. now the arrays becomes-
[1,2,3,4,5]
now ignore the first two elements and select the minimum element from the array [3,4,5] which is 3 here swap it with the beginning element which is also 3 swap it okay now see the array ignoring the first three elements which are [1,2,3] and the remaining array is [4,5] select the minimum element from this array which is 4 here swap it with the beginning element which is also 4 here now again see the array excluding the first four elements which are swapped and the array left is [5] which automatically get sorted so in this way your all elements will be sorted from this technique it is considered as the easiest sorting algorithm after bubble sort.
let's see how to implement this in the code-
public class Arrays06 {
//selection sort
public static void main(String[] args)
{
int a[]= {5,4,3,2,1};
int l=a.length;
for(int i=0;i<l-1;i++) // algorithm section started
{
for(int j=i+1;j<l;j++)
{
int t=a[j];
a[j]=a[i];
a[i]=t;
}
} // algorithm section ended
System.out.println("the sorted array is ");
for(int each:a)
{
System.out.print(each+" ");
}
}
} Output:
the sorted array is
1 2 3 4 5 Imp.note- In this code we have used two for loops one is running from the beginning to the second last element and the other is running from the second element to the last element of the array.
Comments
Post a Comment
Hello, visitor your comments are so helpful for us so do not hesitate just write the comment we read all your comments so don't think your comment goes waste.