mr->buf[mr->idx] = MAX_INT;
live_runs--;
}
else {
mr->length = bytes/sizeof(int);
mr->offset += bytes;
mr->idx = 0;
}
}
}
adjust(runs, num_runs, ls[0]);
}
bytes = write(output_fd, buffer, bp*4);
if (bytes != bp*4) {
printf("!!!!!! Write Error !!!!!!!!!\n");
exit(0);
}
close(output_fd);
}
long get_time_usecs()
{
struct timeva l time;
struct timezone tz;
memset(&tz, '\0', sizeof(struct timezone));
gettimeofday(&time, &tz);
long usecs = time.tv_sec*1000000 + time.tv_usec;
return usecs;
}
void swap(int *p, int *q)
{
int tmp;
tmp = *p;
*p = *q;
*q = tmp;
}
int partition(int *a, int s, int t)
{
int i, j; /* i用来遍历a[s]...a[t-1], j指向大于x部分的第一个元素 */
for (i = j = s; i < t; i++) {
if (a[i] < a[t]) {
swap(a+i, a+j);
j++;
}
}
swap(a+j, a+t);
return j;
}
void quick_sort(int *a, int s, int t)
{
int p;
if (s < t) {
p = partition(a, s, t);
quick_sort(a, s, p-1);
quick_sort(a, p+1, t);
}
}
void adjust(run_t ** runs, int n, int s)
{
int t, tmp;
t = (s+n)/2;
while (t > 0) {
if (s == -1) {
break;
}
if (ls[t] == -1 || runs[s]->buf[runs[s]->idx] > runs[ls[t]]->buf[runs[ls[t]]->idx]) {
s = ls[t];
ls[t] = tmp;
}
t >>= 1;
}
ls[0] = s;
}
void create_loser_tree(run_t **runs, int n)
{
int i;
for (i = 0; i < n; i++) {
ls[i] = -1;
}
for (i = n-1; i >= 0; i--) {
adjust(runs, n, i);
}
}
void usage()
{
printf("sort
printf("\tfilename: filename of file to be sorted\n");
printf("\tK-ways: how many ways to merge\n");
exit(1);
}
五 编译运行
gcc sort.c -o sort -g
./sort random.dat 64
以64路平衡归并对random.dat内的数据进行外部排序。在I5处理器，4G内存的硬件环境下，实验结果如下
文件大小 耗时
128M 14.72 秒
256M 30.89 秒
512M 71.65 秒
1G 169.18秒
六 读取二进制文件，查看排序结
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
int main(int argc, char **argv)
{
char *filename = argv[1];
int *buffer = (int *)malloc(1<<20);
struct stat sbuf;
int rv, data_size, i, bytes, fd;
fd = open(filename, O_RDONLY);
if (fd < 0) {
printf("%s not found!\n", filename);
exit(0);
}
rv = fstat(fd, &sbuf);
data_size = sbuf.st_size;
bytes = read(fd, buffer, data_size);
for (i = 0; i < bytes/4; i++) {
printf("%d ", buffer[i]);
if ((i+1) % 10 == 0) {
printf("\n");
}
}
printf("\n");
close(fd);
free(buffer);
return 0;
}