ランキング関数プログラム

［ 簡単な説明 ］

非ソートのデータ配列中から、昇順に数えた場合の該当ランキングデータを抽出する関数です。
アルゴリズムはクイックソートを使用していますが、ソートするわけではないので、スタックは不要です。

各関数は、引数として、配列名、配列サイズ、ランキングを与えます。戻り値が該当データです。

int rank_i( )
double rank_d( )
uchar *rank_c( )
プログラム・ソース（"sort3.c"）　　　　　　　　　　　　　　　　　　　　　　　　　　　　　top （トップに戻る） 
/*		sort3.c		選択(n個のデータの k+1 番目を抽出する)	*/
#include <stdio.h>
#include <stdlib.h>
#include "sort.h"

int rank_i(int aa[], int n, int k)
{
	int *a, *ak, *i, *j, *left, *right, x, t;

	a = (int *)malloc(n * sizeof(int));
	if(a == NULL)
	{
		fprintf(stderr, "Error : out of memory  in rank_i()\n");
		return -1;
	}
	i = a + n - 1;
	j = aa + n - 1;
	while(i >= a)	*i-- = *j--;

	right = (left = a) + n - 1;
	ak = a + k;
	do
	{
		x = *ak;
		i = left;
		j = right;
		for( ; ; )
		{
			while(*i < x)	i++;
			while(x < *j)	j--;
			if(i > j)	break;
			t = *i;
			*i++ = *j;
			*j-- = t;
		}
		if(j < ak)	left = i;
		if(ak < i)	right = j;
	} while(left < right);
	free(a);
	return *ak;
}

double rank_d(double aa[], int n, int k)
{
	double *a, x, t;
	int i, j, left, right;

	a = (double *)malloc(n * sizeof(double));
	if(a == NULL)
	{
		fprintf(stderr, "Error : out of memory  in rank_d()\n");
		return -1;
	}
	for(i = 0; i < n; i++)	a[i] = aa[i];

	left = 0;
	right = n - 1;
	do
	{
		x = a[k];
		i = left;
		j = right;
		for( ; ; )
		{
			while(a[i] < x)	i++;
			while(x < a[j])	j--;
			if(i > j)	break;
			t = a[i];
			a[i++] = a[j];
			a[j--] = t;
		}
		if(j < k)	left = i;
		if(k < i)	right = j;
	} while(left < right);
	x = a[k];
	free(a);
	return x;
}

uchar *rank_c(uchar *aa[], int n, int k)
{
	uchar **a, **ak, **i, **j, **left, **right, *x, *t;

	a = (uchar **)malloc(n * sizeof(uchar *));
	if(a == NULL)
	{
		fprintf(stderr, "Error : out of memory  in rank_c()\n");
		return NULL;
	}
	i = a + n - 1;
	j = aa + n - 1;
	while(i >= a)
	{
		x = *i-- = (uchar *)
			malloc((strlen(*j) + 1) * sizeof(uchar));
		if(x == NULL)
		{
			fprintf(stderr, "Error : out of memory  in rank_c()\n");
			return NULL;
		}
		t = *j--;
		while((*x++ = *t++) != '\0')
			;
	}

	right = (left = a) + n - 1;
	ak = a + k;
	do
	{
		x = *ak;
		i = left;
		j = right;
		for( ; ; )
		{
			while(strcmp(*i, x) < 0)	i++;
			while(strcmp(x, *j) < 0)	j--;
			if(i > j)	break;
			t = *i;
			*i++ = *j;
			*j-- = t;
		}
		if(j < ak)	left = i;
		if(ak < i)	right = j;
	} while(left < right);
	i = a + n - 1;
	while(i >= a)	free(i--);
	free(a);
	return *ak;
}