qsortソート
電力:クイックソート・インスタンスを使用してソート
使用法:void qsort(void*base,int nelem,int width,int(*fcmp);
パラメータ:1ソート対象配列ヘッダアドレス2配列中のソート対象要素数3各要素の占有空間サイズ4は関数のポインタを指し、ソートの順序を決定する
一、intタイプ配列の並べ替え
二、charタイプ配列の並べ替え(intタイプと同じ)
三、doubleタイプ配列のソート(特に注意)
四、構造体の一級並べ替え
五、構造体の二次並べ替え
例題1:nyist 240(明ちゃんの調査統計)テーマリンク:http://acm.nyist.net/JudgeOnline/problem.php?pid=240
六、文字列を並べ替える
七、計算幾何学で凸包を求めるcmp(略、前の博文に凸包テンプレートがある)
使用法:void qsort(void*base,int nelem,int width,int(*fcmp);
パラメータ:1ソート対象配列ヘッダアドレス2配列中のソート対象要素数3各要素の占有空間サイズ4は関数のポインタを指し、ソートの順序を決定する
一、intタイプ配列の並べ替え
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{ return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);
二、charタイプ配列の並べ替え(intタイプと同じ)
char word[100];
Sample:
int cmp( const void *a , const void *b )
{ return *(char *)a - *(int *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
三、doubleタイプ配列のソート(特に注意)
double in[100];
int cmp( const void *a , const void *b )
{ return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp);
四、構造体の一級並べ替え
struct In
{ double data;
int other;
}s[100];
// data , data ,
int cmp( const void *a ,const void *B)
{ return (*(In *)a)->data > (*(In *)B)->data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);
五、構造体の二次並べ替え
struct In
{ int x;
int y;
}s[100];
// x , x y
int cmp( const void *a , const void *b )
{ struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);
例題1:nyist 240(明ちゃんの調査統計)テーマリンク:http://acm.nyist.net/JudgeOnline/problem.php?pid=240
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define max 100005
struct paim
{ int gd;
int xh;
int cs;
int pm;
};
/*
bool comp(paim x,paim y) //sort
{ if(x.gd!=y.gd) return x.gd>y.gd;
if(x.gd==y.gd&&x.cs!=y.cs) return x.cs<y.cs;
if(x.gd==y.gd&&x.cs==y.cs&&x.xh!=y.xh) return x.xh<y.xh;
}
*/
int comp( const void *a , const void *b )
{ struct paim *c=(paim *)a;
struct paim *d=(paim *)b;
if(c->gd!=d->gd) return d->gd-c->gd;
if(c->gd==d->gd&&c->cs!=d->cs) return c->cs-d->cs;
if(c->gd==d->gd&&c->cs==d->cs&&c->xh!=d->xh) return c->xh-d->xh;
}
int main()
{ int n,m,y,t,num=0,i,j,k;
cin>>n>>m;
paim a[max];
for(i=1;i<=n;i++)
{ scanf("%d",&y);
for(j=1;j<=y;j++)
{ scanf("%d",&t);
a[num].gd=t;
a[num].xh=j;
a[num].cs=i;
num++;
}
}
//sort(a,a+num,comp);
qsort(a,num,sizeof(a[0]),comp);
a[0].pm=1;
for(i=1;i<num;i++)
{ if(a[i].gd!=a[i-1].gd) a[i].pm=a[i-1].pm+1;
else a[i].pm=a[i-1].pm;
}
for(i=0;i<m;i++)
{ scanf("%d",&k);
for(j=0;j<num;j++)
{ if(a[j].pm==k) cout<<a[j].cs<<" "<<a[j].xh<<endl;
else if(a[j].pm>k) break;
}
}
return 0;
}
六、文字列を並べ替える
struct In
{ int data;
char str[100];
}s[100];
// str
int cmp ( const void *a , const void *b )
{ return strcmp( (*(In *)a)->str , (*(In *)B)->str );
}
qsort(s,100,sizeof(s[0]),cmp);
七、計算幾何学で凸包を求めるcmp(略、前の博文に凸包テンプレートがある)