Skip to content

Instantly share code, notes, and snippets.

@iamdylanngo
Last active November 13, 2019 07:16
Show Gist options
  • Save iamdylanngo/e8e92a27b33e13b4ab82c6d94935ff6b to your computer and use it in GitHub Desktop.
Save iamdylanngo/e8e92a27b33e13b4ab82c6d94935ff6b to your computer and use it in GitHub Desktop.
import java.util.Arrays;
public class Sorting {
public int[] countingSortOld(int arrs[], int k) {
int C[] = new int[k];
for (int i = 0; i < arrs.length; i++) {
C[arrs[i]]++;
}
int index = 0;
for (int i = 0; i < C.length; i++) {
while (C[i]-- != 0) {
arrs[index] = i;
index++;
}
}
for (int item : arrs) {
System.out.println(item);
}
return arrs;
}
public char[] countingSortOld(char arrs[], int k) {
int C[] = new int[k];
for (int i = 0; i < arrs.length; i++) {
C[arrs[i]]++;
}
int index = 0;
for (int i = 0; i < C.length; i++) {
while (C[i] != 0) {
arrs[index] = (char) i;
index++;
C[i]--;
}
}
for (char item : arrs) {
System.out.println("-" + item);
}
return arrs;
}
public int[] countingSort(int[] arrs, int k) {
int n = arrs.length;
int[] output = new int[n];
int[] count = new int[k];
for (int i = 0; i < n; i++) {
count[arrs[i]]++;
}
for (int i = 1; i <= k - 1; i++) {
count[i] += count[i - 1];
}
for (int arr : arrs) {
output[count[arr] - 1] = arr;
count[arr]--;
}
for (int i = 0; i < n; i++) {
arrs[i] = output[i];
}
for (int i = 0; i < arrs.length; i++) {
System.out.println("i: " + i + " v: " + arrs[i]);
}
return arrs;
}
public char[] countingSort(char[] arrs, int k) {
int n = arrs.length;
int[] output = new int[n];
int[] count = new int[k];
for (char arr : arrs) {
count[arr]++;
}
for (int i = 1; i <= k - 1; i++) {
count[i] += count[i - 1];
}
for (char arr : arrs) {
output[count[arr] - 1] = arr;
count[arr]--;
}
for (int i = 0; i < n; i++) {
arrs[i] = (char) output[i];
}
for (int i = 0; i < arrs.length; i++) {
System.out.println("i: " + i + " v: " + arrs[i]);
}
return arrs;
}
public void countingRadix(int[] arrs, int exp, int N) {
int[] output = new int[N];
int[] count = new int[10];
for (int i = 0; i < N; i++) count[(arrs[i] / exp) % 10]++;
for (int i = 1; i < 10; i++) count[i] += count[i - 1];
for (int i = N - 1; i >= 0; i--) {
output[count[(arrs[i] / exp) % 10] - 1] = arrs[i];
count[(arrs[i] / exp) % 10]--;
}
for (int i = 0; i < N; i++) arrs[i] = output[i];
}
public int[] radixSort(int arrs[]) {
int N = arrs.length;
int max = arrs[0];
for (int item : arrs) {
if (item > max)
max = item;
}
System.out.println("max: " + max);
for (int exp = 1; max / exp > 0; exp *= 10)
this.countingRadix(arrs, exp, N);
System.out.println("==============================");
System.out.println(Arrays.toString(arrs));
return arrs;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment