sort example

bblsort-eg.c

#include <stdio.h>
#include <stdlib.h> /* rand */
#include <assert.h>

int swp_calls=0;
void swap(int *s,int *d){
  int t=*s;
  *s=*d;
  *d=t;
  swp_calls++;
}

int cmp_calls=0;
int cmp(const void *p,const void *q){
  cmp_calls++;
  return *(int*)p-*(int*)q;
}

void bblsort(void *it,size_t n,size_t size,
  int(*cmp)(const void*,const void*)){
  int i,j;
  for(i=n-1;i>0;i--){
    for(j=0;j<i;j++){
      if(cmp(&((int*)it)[j],&((int*)it)[j+1])>0){
        swap(&((int*)it)[j],&((int*)it)[j+1]);
      }
    }
  }
}

int main(int argc,char* argv[]){
  int i,j,xor=0,it[100];
  int n=sizeof(it)/sizeof(int);
  int t=10000;
  for(i=0;i<t;i++){
    for(j=0;j<n;j++) {
      it[j]=rand();
      xor^=it[j];
    }
    bblsort(it,n,sizeof(int),cmp);
    for(j=1;j<n;j++) assert(it[j-1]<=it[j]);
  }
  printf("%16s: cmp=%6.1f, swp=%6.1f, xor=%08X\n",
    "bblsort",(double)cmp_calls/t,(double)swp_calls/t,xor);
  return 0;
}

bblsort-eg2.c

#include <stdio.h>
#include <stdlib.h> /* rand */
#include <assert.h>

int swp_calls=0;
void swap(int *s,int *d){
  int t=*s;
  *s=*d;
  *d=t;
  swp_calls++;
}

int cmp_calls=0;
int cmp(const void *p,const void *q){
  cmp_calls++;
  return *(int*)p-*(int*)q;
}

void bblsort(void *it,size_t n,size_t size,
  int(*cmp)(const void*,const void*)){
  int i,j,t;
  for(i=n-1;i>0;i=t,t=0){
    for(j=0;j<i;j++){
      if(cmp(&((int*)it)[j],&((int*)it)[j+1])>0){
        swap(&((int*)it)[j],&((int*)it)[j+1]);
        t=j;
      }
    }
  }
}

int main(int argc,char* argv[]){
  int i,j,xor=0,it[100];
  int n=sizeof(it)/sizeof(int);
  int t=10000;
  for(i=0;i<t;i++){
    for(j=0;j<n;j++) {
      it[j]=rand();
      xor^=it[j];
    }
    bblsort(it,n,sizeof(int),cmp);
    for(j=1;j<n;j++) assert(it[j-1]<=it[j]);
  }
  printf("%16s: cmp=%6.1f, swp=%6.1f, xor=%08X\n",
    "bblsort2",(double)cmp_calls/t,(double)swp_calls/t,xor);
  return 0;
}

qsort-eg.c

#include <stdio.h>
#include <stdlib.h> /* rand,qsort */
#include <assert.h>

int cmp_calls=0;
int cmp(const void *p, const void *q){
  cmp_calls++;
  return *(int*)p-*(int*)q;
}

int main(int argc,char* argv[]){
  int i,j,xor=0,it[100];
  int n=sizeof(it)/sizeof(int);
  int t=10000;
  for(i=0;i<t;i++){
    for(j=0;j<n;j++) {
      it[j]=rand();
      xor^=it[j];
    }
    qsort(it,n,sizeof(int),cmp);
    for(j=1;j<n;j++) assert(it[j-1]<=it[j]);
  }
  printf("%16s: cmp=%6.1f, swp=??????, xor=%08X\n",
    "qsort",(double)cmp_calls/t,xor);
  return 0;
}

qsort2-eg.c

#include <stdio.h>
#include <stdlib.h> /* rand */
#include <assert.h>

int swp_calls=0;
void swap(int *s,int *d){
  int t=*s;
  *s=*d;
  *d=t;
  swp_calls++;
}

int cmp_calls=0;
int cmp(const void *p,const void *q){
  cmp_calls++;
  return *(int*)p-*(int*)q;
}

void q_sort(void *it,size_t n,size_t size,
  int(*cmp)(const void*,const void*)){
  int i=0,j=n-1,p=((int*)it)[0];
  assert(n>1);
  while(i<j){
    for(;i<j;j--)
      if(cmp(&p,&((int*)it)[j])>0)break;
    if(i==j)break;
    swap(&((int*)it)[i],&((int*)it)[j]);
    for(++i;i<j;i++)
      if(cmp(&p,&((int*)it)[i])<=0)break;
  }
  if(i>1)q_sort(it,i,size,cmp);
  if(i==0){i++;}
  if(n-i>1)q_sort(&((int*)it)[i],n-i,size,cmp);
}

int main(int argc,char* argv[]){
  int i,j,xor=0,it[100];
  int n=sizeof(it)/sizeof(int);
  int t=10000;
  for(i=0;i<t;i++){
    for(j=0;j<n;j++) {
      it[j]=rand();
      xor^=it[j];
    }
    q_sort(it,n,sizeof(int),cmp);
    for(j=1;j<n;j++) assert(it[j-1]<=it[j]);
  }
  printf("%16s: cmp=%6.1f, swp=%6.1f, xor=%08X\n",
    "qsort2",(double)cmp_calls/t,(double)swp_calls/t,xor);
  return 0;
}

qsort3-eg.c

#include <stdio.h>
#include <stdlib.h> /* rand */
#include <assert.h>

int swp_calls=0;
void swap(int *s,int *d){
  int t=*s;
  *s=*d;
  *d=t;
  swp_calls++;
}

int cmp_calls=0;
int cmp(const void *p,const void *q){
  cmp_calls++;
  return *(int*)p-*(int*)q;
}

void q_sort(void *it,size_t n,size_t size,
  int(*cmp)(const void*,const void*)){
  int i=0,j=n-1,p=((int*)it)[n/2];
  assert(n>1);
  for(;;){
    for(;cmp(&((int*)it)[i],&p)<0;i++);
    for(;cmp(&((int*)it)[j],&p)>0;j--);
    if(i>=j)break;
    swap(&((int*)it)[i],&((int*)it)[j]);
    i++;
    j--;
  }
  j++;
  if(i>1)q_sort(it,i,size,cmp);
  if(n-j>1)q_sort(&((int*)it)[j],n-j,size,cmp);
}

int main(int argc,char* argv[]){
  int i,j,xor=0,it[100];
  int n=sizeof(it)/sizeof(int);
  int t=10000;
  for(i=0;i<t;i++){
    for(j=0;j<n;j++) {
      it[j]=rand();
      xor^=it[j];
    }
    q_sort(it,n,sizeof(int),cmp);
    for(j=1;j<n;j++) assert(it[j-1]<=it[j]);
  }
  printf("%16s: cmp=%6.1f, swp=%6.1f, xor=%08X\n",
    "qsort3",(double)cmp_calls/t,(double)swp_calls/t,xor);
  return 0;
}

selsort-eg.c

#include <stdio.h>
#include <stdlib.h> /* rand */
#include <assert.h>

int swp_calls=0;
void swap(int *s,int *d){
  int t=*s;
  *s=*d;
  *d=t;
  swp_calls++;
}

int cmp_calls=0;
int cmp(const void *p,const void *q){
  cmp_calls++;
  return *(int*)p-*(int*)q;
}

void selsort(void *it,size_t n,size_t size,
  int(*cmp)(const void*,const void*)){
  int i,j;
  for(i=0;i<n;i++){
    int min=i;
    for(j=i+1;j<n;j++){
      if(cmp(&((int*)it)[min],&((int*)it)[j])>0){
        min=j;
      }
    }
    if(min!=i){
      swap(&((int*)it)[i],&((int*)it)[min]);
    }
  }
}

int main(int argc,char* argv[]){
  int i,j,xor=0,it[100];
  int n=sizeof(it)/sizeof(int);
  int t=10000;
  for(i=0;i<t;i++){
    for(j=0;j<n;j++){
      it[j]=rand();
      xor^=it[j];
    }
    selsort(it,n,sizeof(int),cmp);
    for(j=1;j<n;j++) assert(it[j-1]<=it[j]);
  }
  printf("%16s: cmp=%6.1f, swp=%6.1f, xor=%08X\n",
    "selsort",(double)cmp_calls/t,(double)swp_calls/t,xor);
  return 0;
}