This code is about algorithms and datastructures. This code runs perfectly and i just have some questions on it because it seems like i don't understand two points. So my questions for that is:
public class CountingSort {
public static void main(String[] args) {
int[] m1 = { 1, 17, 3, 1, 4, 9, 4, 4 };
System.out.println("unsorted:");
output(m1);
int min1 = rangeMin(m1);
int max1 = rangeMax(m1);
countingSort(m1, min1, max1);
System.out.println("sorted:");
output(m1);
int[] m2 = { -1, 13, 3, -1, -4, 9, -4, 4 };
System.out.println("unsorted:");
output(m2);
int min2 = rangeMin(m2);
int max2 = rangeMax(m2);
countingSort(m2, min2, max2);
System.out.println("sorted:");
output(m2);
}
public static void output(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ", ");
}
System.out.println();
}
public static int rangeMin(int[] a) {
int minimum = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] < minimum)
minimum = a[i];
}
return minimum;
}
public static int rangeMax(int[] array) {
int maximum = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > maximum)
maximum = array[i];
}
return maximum;
}
public static void countingSort(int[] array, int rangeMin, int rangeMax) {
int[] countingArray = new int[rangeMax - rangeMin + 1];
for (int i : array) {
countingArray[i - rangeMin]++;
}
int c = 0;
for (int i = rangeMin; i <= rangeMax; i++) {
while (countingArray[i - rangeMin] > 0) {
array[c] = i;
c++;
countingArray[i - rangeMin]--;
}
}
}
}
CountingSort
has O(n)
time and space complexity. You iterate (i.e. use for loop
) twice.
public class CountingSort {
public static void main(String... args) {
proceed(1, 17, 3, 1, 4, 9, 4, 4);
System.out.println("---");
proceed(-1, 13, 3, -1, -4, 9, -4, 4);
}
public static void proceed(int... arr) {
System.out.print("unsorted: ");
print(arr);
countingSort(arr);
System.out.print("sorted: ");
print(arr);
}
public static void print(int... arr) {
System.out.println(Arrays.stream(arr)
.mapToObj(i -> String.format("%2d", i))
.collect(Collectors.joining(",")));
}
public static void countingSort(int... arr) {
int min = Arrays.stream(arr).min().orElse(0);
int max = Arrays.stream(arr).max().orElse(0);
// contains amount of number in the unsorted array
// count[0] - amount of min numbers
// count[count.length - 1] - amount of max numbers
int[] count = new int[max - min + 1];
for (int i : arr)
count[i - min]++;
// fill source array with amount of numbers
for (int i = 0, j = 0; i < count.length; i++)
for (int k = 0; k < count[i]; k++, j++)
arr[j] = min + i;
}
}