public class SortArrayContaining012Only {
public static void main(String[] args) {
int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
int arr_size = arr.length;
sort012(arr, arr_size);
System.out.println("Sorting done");
}
private static void sort012(int a[], int arr_size) {
int lo = 0;
int hi = arr_size - 1;
int mid = 0;
while (mid <= hi) {
switch (a[mid]) {
// swap lo and mid
case 0:
int temp = a[mid];
a[mid] = a[lo];
a[lo] = temp;
lo++;
mid++;
break;
case 1:
mid++;
break;
// swap mid and high
case 2:
temp = a[mid];
a[mid] = a[hi];
a[hi] = temp;
hi--;
break;
}
}
}
}
Tuesday, June 10, 2014
Sort array containing only 0, 1 & 2 in Complexity O(n)
Java Implementation -
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment