うるさい

プログラミング演習で、Enterキーをこれでもかというほど大きな音を立てて打つ人。


「自分は着々と進んでるぜ」アピールだろうか。


気持ちは分からなくもない。自分も中学生のときそうだったから。

でも、大学生にもなってそんなことするのはやめれ。




今日はヒープソートプログラムを組んだ。

使いたい方はご自由にどうぞ。

#include <stdio.h>
#include <stdlib.h>

struct records{
  int code;
  int score;
};

void heapsort(int n,struct records *array);
void showdata(struct records *array,int n);
void swap(struct records *a,struct records *b);
void makeheap(int n,struct records *array);

int x=0;

int main(void)
{
  int i,n;
  struct records *array;

  scanf("%d ",&n);

  array=(struct records *)malloc(n*sizeof(struct records));
  if(!array){
    printf("もぉー。たっくんのいじわるぅ。もったいぶらないでぇー。¥n");
    exit(1);
  }

  for(i=0;i<n;i++)
    scanf("%d %d",&array[i].code,&array[i].score);

  /*showdata(array,n);*/

  heapsort(n,array);

  printf("要素数：%d  比較回数：%d¥n",n,x);

  showdata(array,n);

  return 0;
}

void heapsort(int n,struct records *array)
{
  for(;n;n--){
    makeheap(n,array);
    swap(&array[0],&array[n-1]);
  }
}

void showdata(struct records *array,int n)
{
  int i;

  for(i=n-1;i+1;i--){
    if(i)
      if(array[i].score==array[i-1].score && array[i].code>array[i-1].code)
        swap(&array[i],&array[i-1]);
    printf("%dn%dnn",array[i].code,array[i].score);
  }
  printf("¥n");
}

void swap(struct records *a,struct records *b)
{
  struct records buffer;

  buffer=*a;
  *a=*b;
  *b=buffer;
}

void makeheap(int n,struct records *array)
{
  int a=n/2,max;

  while(a){
    max=a;

    if(2*a<=n && array[max-1].score<array[2*a-1].score){
      max=2*a;
      x++;
    }
    if(2*a+1<=n && array[max-1].score<array[2*a].score){
      max=2*a+1;
      x++;
    }

    if(max==a)
        a--;
    else
      if(max==2*a){
        swap(&array[a-1],&array[2*a-1]);
        a*=2;
      }
      else
        if(max==2*a+1){
          swap(&array[a-1],&array[2*a]);
          a=2*a+1;
        }
  }
}