Skip to content

Instantly share code, notes, and snippets.

@nitko12
Created June 16, 2022 13:35
Show Gist options
  • Save nitko12/cdbfdf4474e77a33883457dd6e084e58 to your computer and use it in GitHub Desktop.
Save nitko12/cdbfdf4474e77a33883457dd6e084e58 to your computer and use it in GitHub Desktop.
Testing simple radix sort implementation against qsort
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
const int MAXN = 100000;
int buf1[64][MAXN], buf2[64][MAXN], cnt[64], cnt2[64];
long long used;
// za brojeve do 262144
void radix_sort(int *a, int *b)
{
int t;
long long used = 0;
for (int *i = a; i < b; ++i)
{
t = *i & 63;
buf1[t][cnt[t]++] = *i;
used |= 1LL << t;
}
// ispis 1
// for (int i = 63 - __builtin_clzll(used);
// used != 0;
// i = 63 - __builtin_clzll(used))
// {
// printf("%d\n", i);
// for (int j = 0; j < cnt[i]; ++j)
// printf(" %d\n", buf1[i][j]);
// used &= ~(1LL << i);
// }
memset(cnt2, 0, sizeof(cnt2)); // ne treba, ali nek stoji
long long used2 = 0;
for (int i = 63 - __builtin_clzll(used);
used != 0;
i = 63 - __builtin_clzll(used))
{
for (int j = 0; j < cnt[i]; ++j)
{
int t = (buf1[i][j] >> 6) & 63;
buf2[t][cnt2[t]++] = buf1[i][j];
used2 |= 1LL << t;
}
used &= ~(1LL << i);
}
// ispis 2
// for (int i = 63 - __builtin_clzll(used2);
// used2 != 0;
// i = 63 - __builtin_clzll(used2))
// {
// printf("%d\n", i);
// for (int j = 0; j < cnt2[i]; ++j)
// printf(" %d\n", buf2[i][j]);
// used2 &= ~(1LL << i);
// }
memset(cnt, 0, sizeof(cnt)); // TODO: ubrzati, mora biti način
used = 0;
for (int i = 63 - __builtin_clzll(used2);
used2 != 0;
i = 63 - __builtin_clzll(used2))
{
for (int j = 0; j < cnt2[i]; ++j)
{
int t = (buf2[i][j] >> 12) & 63;
buf1[t][cnt[t]++] = buf2[i][j];
used |= 1LL << t;
}
used2 &= ~(1LL << i);
}
--b;
for (int i = 63 - __builtin_clzll(used);
used != 0;
i = 63 - __builtin_clzll(used))
{
for (int j = 0; j < cnt[i]; ++j)
*b-- = buf1[i][j];
used &= ~(1LL << i);
}
}
int n;
int a[1000005], b[1000005];
int cmpfunc(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}
int main(int argc, char *argv[])
{
srand(time(NULL));
n = atoi(argv[1]);
for (int i = 0; i < n; ++i)
{
a[i] = rand() % 200000;
b[i] = a[i];
}
// for (int i = 0; i < 10; ++i)
// printf("%d ", a[i]);
// printf("\n");
clock_t begin, end;
double difference;
begin = clock();
radix_sort(a, a + n);
end = clock();
difference = (double)(end - begin) / CLOCKS_PER_SEC;
printf("radix: %lf\n", difference);
begin = clock();
qsort(b, n, sizeof(int), cmpfunc);
end = clock();
difference = (double)(end - begin) / CLOCKS_PER_SEC;
printf("qsort: %lf\n", difference);
for (int i = 1; i < n; ++i)
if (!(a[i - 1] <= a[i]))
printf("KRIVO %d\n", i);
// for (int i = 0; i < 10; ++i)
// printf("%d ", a[i]);
// printf("\n");
// for (int i = 0; i < 4; ++i)
// {
// printf("%d ", a[i]);
// }
// printf("\n");
return 0;
}
// plot here: https://imgur.com/Z0PqqUN
// import subprocess
// import matplotlib.pyplot as plt
// from tqdm import tqdm
// if __name__ == "__main__":
// radix, qsort = [], []
// for x in tqdm(range(100, 100005, 100)):
// test = subprocess.Popen(["./a.out", str(x)], stdout=subprocess.PIPE)
// output = str(test.communicate()[0]).replace("\\n", " ")
// radix.append(float(output.split()[1]))
// qsort.append(float(output.split()[3]))
// # print(output.split()[1],
// # output.split()[3])
// r = list(range(100, 100005, 100))
// plt.plot(r, radix, "-b", label="Radix")
// plt.plot(r, qsort, "-r", label="QSort")
// plt.ylabel('qsort vs radix')
// plt.legend(loc="upper left")
// plt.savefig("plot.png")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment