Sort an array of integers.
Sometimes such question can be asked in the interviews check your knowledge on various sorting algorithms or concepts.
But will be better to know the kind of integers present in that array, like here array may contain many duplicate numbers & those numbers can be any in range 0 to 2 or 1 to 1000 or 1 to 1000000.
And I am not sure what algorithm, interviewer has thought for its solution or what response is expected from you.
And I can think about following approaches -
a) If the number of unique integers is quite small like if range is 0 to 2, then you can start with 3 pointers marking the position of last 0 visited & second pointer to mark the position of last 1 visited & 3rd pointer will keep on traversing the array & will also be pointing the position of last 2 visited. In this way you can sort such array in log(n) time.
But it is not possible if unique integers are many.
b) If the number of unique integers is quite large like 1 to 1000 or 1 to 1000000 etc.
Then one from many sorting algorithm can be suggested i.e. counting sort, as read in books.
To explain easily generally at many place it will be shown where you will be creating any array whose each index will be representing the integer & the value will be the number of times that integer occurs in the array.
But it is fine only when either you are not having a huge range of sparse numbers or range of integers is small where space in such array will not be wasted.
So if the range is huge & integers are sparse then you have to customise this approach a bit, like shown on geeksforgeeks for the characters.
For integers, I am doing the same steps but bit differently -
But will be better to know the kind of integers present in that array, like here array may contain many duplicate numbers & those numbers can be any in range 0 to 2 or 1 to 1000 or 1 to 1000000.
And I am not sure what algorithm, interviewer has thought for its solution or what response is expected from you.
And I can think about following approaches -
a) If the number of unique integers is quite small like if range is 0 to 2, then you can start with 3 pointers marking the position of last 0 visited & second pointer to mark the position of last 1 visited & 3rd pointer will keep on traversing the array & will also be pointing the position of last 2 visited. In this way you can sort such array in log(n) time.
But it is not possible if unique integers are many.
b) If the number of unique integers is quite large like 1 to 1000 or 1 to 1000000 etc.
Then one from many sorting algorithm can be suggested i.e. counting sort, as read in books.
To explain easily generally at many place it will be shown where you will be creating any array whose each index will be representing the integer & the value will be the number of times that integer occurs in the array.
But it is fine only when either you are not having a huge range of sparse numbers or range of integers is small where space in such array will not be wasted.
So if the range is huge & integers are sparse then you have to customise this approach a bit, like shown on geeksforgeeks for the characters.
For integers, I am doing the same steps but bit differently -
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
public class CountSort {
public static void main(String[] args) {
int[] array = {0,1,2,0,1,2,2,1,0,1,0,2,1,0,0,1,2,0,1,2,1,2,100,200,100,200,101,200,200};
array = sort(array);
for(int i : array)
System.out.println(i);
}
private static int[] sort(int[] array) {
int len = array.length;
ArrayList<Integer> uniques = new ArrayList<>();
HashMap<Integer, Integer> counts = new HashMap<>();
for(int i : array) {
Integer a = null;
if((a=counts.get(i)) == null) {
uniques.add(i);
counts.put(i, 1);
} else {
counts.put(i, a+1);
}
}
Collections.sort(uniques);
int next= 0;
for(int i = 0; i < len;) {
int num = uniques.get(next);
int c = counts.get(num);
while(c > 0) {
array[i] = num;
i++;
c--;
}
next++;
}
return array;
}
}
import java.util.Collections;
import java.util.HashMap;
public class CountSort {
public static void main(String[] args) {
int[] array = {0,1,2,0,1,2,2,1,0,1,0,2,1,0,0,1,2,0,1,2,1,2,100,200,100,200,101,200,200};
array = sort(array);
for(int i : array)
System.out.println(i);
}
private static int[] sort(int[] array) {
int len = array.length;
ArrayList<Integer> uniques = new ArrayList<>();
HashMap<Integer, Integer> counts = new HashMap<>();
for(int i : array) {
Integer a = null;
if((a=counts.get(i)) == null) {
uniques.add(i);
counts.put(i, 1);
} else {
counts.put(i, a+1);
}
}
Collections.sort(uniques);
int next= 0;
for(int i = 0; i < len;) {
int num = uniques.get(next);
int c = counts.get(num);
while(c > 0) {
array[i] = num;
i++;
c--;
}
next++;
}
return array;
}
}
So I think its time complexity will be = nlog(n)
