#include <stdio.h>
#include <time.h>
#include <sys/time.h>
#define len 10000
int a[len];
int b[len];
int m=len-1;
void makec(){
for(int i=0;i<len;i++){
a[i]=r;
b[i]=r;
}
}
void swap(int* a,int* b){
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}
void quickSort(left,right){
if(left>=right){
return;
}
int i=left+1;
int j=right;
while(1){
while(a[i]<=a[left]&&i<right){
i++;
}
while(a[j]>=a[left]&&j>left){
j--;
}
if(i>=j){
break;
}
swap(&a[i],&a[j]);
}
swap(&a[left],&a[j]);
quickSort(left,j-1);
quickSort(j+1,right);
}
void heap(){
int i,j;
for(i=(m-1)/2;i>=0;i--){
j=i;
heapDown(j);
}
}
void heapDown(int j){
if(2*j+2<=m&&b[j]<b[2*j+2]&&b[2*j+1]<b[2*j+2]){
swap(&b[j],&b[2*j+2]);
return heapDown(2*j+2);
}
else if(2*j+1<=m&&b[j]<b[2*j+1]){
swap(&b[j],&b[2*j+1]);
return heapDown(2*j+1);
}
}
void heapSort(){
while(m>=1){
heap();
swap(&b[0],&b[m]);
m--;
}
}
long getTime() {
struct timeval t;
gettimeofday(&t, NULL);
return time(NULL
)*1000 + t.
tv_usec/1000; }
main(){
makec();
long start1=getTime();
quickSort(0,len-1);
long end1=getTime();
long start2=getTime();
heapSort();
long end2=getTime();
printf("クイックソート:%06d\n",end1
-start1
); printf("ヒープソート:%06d\n",end2
-start2
); }
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDx0aW1lLmg+CiNpbmNsdWRlIDxzeXMvdGltZS5oPgojZGVmaW5lIGxlbiAxMDAwMAppbnQgYVtsZW5dOwppbnQgYltsZW5dOwppbnQgbT1sZW4tMTsKCnZvaWQgbWFrZWMoKXsKCWZvcihpbnQgaT0wO2k8bGVuO2krKyl7CgkJaW50IHI9cmFuZCgpJWxlbjsKCQlhW2ldPXI7CgkJYltpXT1yOwoJfQp9Cgp2b2lkIHN3YXAoaW50KiBhLGludCogYil7CglpbnQgdG1wOwoJdG1wPSphOwoJKmE9KmI7CgkqYj10bXA7Cn0KCnZvaWQgcXVpY2tTb3J0KGxlZnQscmlnaHQpewoJaWYobGVmdD49cmlnaHQpewoJCXJldHVybjsKCX0KCWludCBpPWxlZnQrMTsKCWludCBqPXJpZ2h0OwoJd2hpbGUoMSl7CgkJd2hpbGUoYVtpXTw9YVtsZWZ0XSYmaTxyaWdodCl7CgkJICAgIGkrKzsKCSAgICB9CgkgICAgd2hpbGUoYVtqXT49YVtsZWZ0XSYmaj5sZWZ0KXsKCQkgICAgai0tOwoJICAgIH0KCSAgICBpZihpPj1qKXsKCQkgICAgYnJlYWs7CgkgICAgfQoJICAgIHN3YXAoJmFbaV0sJmFbal0pOwoJfQoJc3dhcCgmYVtsZWZ0XSwmYVtqXSk7CglxdWlja1NvcnQobGVmdCxqLTEpOwoJcXVpY2tTb3J0KGorMSxyaWdodCk7Cn0KCnZvaWQgaGVhcCgpewoJaW50IGksajsKCWZvcihpPShtLTEpLzI7aT49MDtpLS0pewoJCWo9aTsKCQloZWFwRG93bihqKTsKCX0KfQoKdm9pZCBoZWFwRG93bihpbnQgail7CglpZigyKmorMjw9bSYmYltqXTxiWzIqaisyXSYmYlsyKmorMV08YlsyKmorMl0pewoJCXN3YXAoJmJbal0sJmJbMipqKzJdKTsKCQlyZXR1cm4gaGVhcERvd24oMipqKzIpOwoJfQoJZWxzZSBpZigyKmorMTw9bSYmYltqXTxiWzIqaisxXSl7CgkJc3dhcCgmYltqXSwmYlsyKmorMV0pOwoJCXJldHVybiBoZWFwRG93bigyKmorMSk7CQoJfQoJCn0KCnZvaWQgaGVhcFNvcnQoKXsKCXdoaWxlKG0+PTEpewoJCWhlYXAoKTsKCQlzd2FwKCZiWzBdLCZiW21dKTsKCQltLS07Cgl9Cn0KCmxvbmcgZ2V0VGltZSgpIHsgCiAgICBzdHJ1Y3QgdGltZXZhbCB0OyAKICAgIGdldHRpbWVvZmRheSgmdCwgTlVMTCk7IAogICAgbG9jYWx0aW1lKCZ0LnR2X3NlYyk7IAogICAgcmV0dXJuIHRpbWUoTlVMTCkqMTAwMCArIHQudHZfdXNlYy8xMDAwOwp9CgptYWluKCl7CgltYWtlYygpOwoJbG9uZyBzdGFydDE9Z2V0VGltZSgpOwoJcXVpY2tTb3J0KDAsbGVuLTEpOwoJbG9uZyBlbmQxPWdldFRpbWUoKTsKCWxvbmcgc3RhcnQyPWdldFRpbWUoKTsKCWhlYXBTb3J0KCk7Cglsb25nIGVuZDI9Z2V0VGltZSgpOwoJcHJpbnRmKCLjgq/jgqTjg4Pjgq/jgr3jg7zjg4jvvJolMDZkXG4iLGVuZDEtc3RhcnQxKTsKCXByaW50Zigi44OS44O844OX44K944O844OI77yaJTA2ZFxuIixlbmQyLXN0YXJ0Mik7Cn0K