how to do sorting in linear time ?explain.
Doubt related sorting
In general, sorting can’t be done in linear time but it is not necessary that you use traditional sorting algorithms here because the array contains only 0s, 1s and 2s. Do you want me to tell you the logic or do you want to try on your own?
But ma’am , in challenge of array there is a question of array sorting in linear time?
Yes, but it is mentioned in the question that array contains only 0s, 1s and 2s. In such a case, it is possible to sort the array in linear time. For example, one approach could be keeping three variables count0, count1 and count2. You can traverse the array once and get count of all 3 types of elements in O(n). Then you can have a separate loop to create a new sorted array. Hence the complexity would be O(n)
package challengearray; import java.util.Scanner; public class sortinlineartime { public static void main(String[] args) { // TODO Auto-generated method stub Scanner s = new Scanner (System.in); int n= s.nextInt(); int [] a = new int [n]; int count=0,count1=0,count2=0; for(int i=0;i<a.length;i++) { a[i]=s.nextInt(); } for(int i=0;i<a.length;i++) { if(a[i]==0) {count++; } else if(a[i]==1) { count1++; } else if(a[i]==2) { count2++; } } for(int i=1;i<=count;i++) { System.out.print(“0”); System.out.println(); } for(int i=1;i<=count1;i++) { System.out.print(“1”); System.out.println(); } for(int i=1;i<=count2;i++) { System.out.print(“2”); System.out.println(); } } }
ma’am is this code is correct ?
I have save the code but how to share link i don’t know .please tell me?
Just copy the link from the address bar and share it here after saving
Yes, your code is correct. You can submit it.
And please mark the doubt as resolved if you have no further queries! 
ma’am ,is there any other way to do this question?
Yes, there is. This is a very famous problem known as the Dutch National Flag problem and another algorithm to solve this problem goes as follows:
The solution to this algorithm will require 3 pointers to iterate throughout the array, swapping the necessary elements.
(1) Create a low pointer at the beginning of the array and a high pointer at the end of the array.
(2) Create a mid pointer that starts at the beginning of the array and iterates through each element.
(3) If the element at arr[mid] is a 2, then swap arr[mid] and arr[high] and decrease the high pointer by 1.
(4) If the element at arr[mid] is a 0, then swap arr[mid] and arr[low] and increase the low and mid pointers by 1.
(5) If the element at arr[mid] is a 1, don’t swap anything and just increase the mid pointer by 1.
This algorithm stops once the mid pointer passes the high pointer.
You can try to implement this algorithm and let me know if anything is unclear!
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
ma’am i got this algorithm.