ｑｓｏｒｔ ^(C/C++), ｓｏｒｔ ^(Java)

[機能]

　　与えられた配列内の要素をソートします．

　　Java の場合は，Arrays クラスの static 関数 sort を使用します．昇順に並べるのが基本ですが，インタフェース Comparator を利用して，C/C++ のように並べる順序を変更することも可能です．

[形式]

（ C/C++ の場合）

	#include <stdlib.h>

	void qsort(void *base, size_t num, size_t size,
	           int(*compare)(const void *elm1, const void *elm2))
		base : ソートする配列の先頭アドレス
		num : 配列の要素の数
		size : 各要素の大きさ（バイト単位）
		compare : 2 つの要素を比較する関数．この関数は，
			          compare(void *elm1, void *elm2)
		          の形式で与えられた 2 つの要素を比較し，次のような結果を返
		          す必要があります．その結果，配列は昇順にソートされます．
		          降順にソートしたいときは，正・負の関係を入れ換えます．
			          負 ： elm1 が elm2 より小さい
			          0  ： elm1 と elm2 が同じ
			          正 ： elm1 が elm2 より大きい

（ Java の場合： Arrays クラスの static メソッド）

	int sort(type[] base)
		type : byte, char, int, long, double, float, object
		

[使用例]

1. データの中から，main の引数として与えられた整数と文字列を探します^(C/C++)

   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>
   
   int compare_n(const void *, const void *);
   int compare_c(const void *, const void *);
   
   /********/
   /* main */
   /********/
   int main(int argc, char **argv)
   {
   	int i1, key_n, *res_n, data_n[10] = {10, 1, 45, 20, 0, -20, 15, 90, 5, 55};
   	char *key_c, **res_c, *data_c[5];
   
   	for (i1 = 0; i1 < 5; i1++)
   		data_c[i1] = new char [10];
   
   	data_c[0] = "fish";
   	data_c[1] = "dog";
   	data_c[2] = "tree";
   	data_c[3] = "human";
   	data_c[4] = "cat";
   /*
   		 探索キー
   */
   	key_n = atoi(argv[1]);
   	key_c = argv[2];
   /*
   		 整数の場合
   */
   					// ソート前の出力
   	printf("sort前   ");
   	for (i1 = 0; i1 < 10; i1++)
   		printf("%d ", data_n[i1]);
   	printf("\n");
   					// ソートとその後の出力
   	qsort(data_n, 10, sizeof(int), compare_n);
   
   	printf("sort後   ");
   	for (i1 = 0; i1 < 10; i1++)
   		printf("%d ", data_n[i1]);
   	printf("\n");
   					// 探索
   	res_n = (int *)bsearch(&key_n, data_n, 10, sizeof(int), compare_n);
   
   	if (res_n != NULL)
   		printf("   %d が見つかりました\n", *res_n);
   	else
   		printf("   %d は見つかりませんでした\n", key_n);
   /*
   		 文字列の場合
   */
   					// ソート前の出力
   	printf("sort前   ");
   	for (i1 = 0; i1 < 5; i1++)
   		printf("%s ", data_c[i1]);
   	printf("\n");
   					// ソートとその後の出力
   	qsort(data_c, 5, sizeof(char *), compare_c);
   
   	printf("sort後   ");
   	for (i1 = 0; i1 < 5; i1++)
   		printf("%s ", data_c[i1]);
   	printf("\n");
   					// 探索
   	res_c = (char **)bsearch(&key_c, data_c, 5, sizeof(char *), compare_c);
   
   	if (res_c != NULL)
   		printf("   %s が見つかりました\n", *res_c);
   	else
   		printf("   %s は見つかりませんでした\n", key_c);
   
   	return 0;
   }
   
   /********************/
   /* ２つの整数の比較 */
   /********************/
   int compare_n(const void *arg1, const void *arg2)
   {
   	int *a1 = (int *)arg1;
   	int *a2 = (int *)arg2;
   	return *a1 - *a2;
   }
   
   /**********************/
   /* ２つの文字列の比較 */
   /**********************/
   int compare_c(const void *chr1, const void *chr2)
   {
   	char **c1 = (char **) chr1;
   	char **c2 = (char **) chr2;
   	return strcmp(*c1, *c2);
   }
   
   （出力）　test 55 fish と入力した場合
   
   sort前   10 1 45 20 0 -20 15 90 5 55 
   sort後   -20 0 1 5 10 15 20 45 55 90 
      55 が見つかりました
   sort前   fish dog tree human cat 
   sort後   cat dog fish human tree 
      fish が見つかりました
   			

2. データの中から，main の引数として与えられた整数と文字列を探します^(Java)

   import java.io.*;
   import java.util.*;
   
   public class Test {
   
   	/********/
   	/* main */
   	/********/
   	public static void main (String args[]) throws ClassCastException
   	{
   		int i1, k_n, k_c, key_n, data_n [] = {10, 1, 45, 20, 0, -20, 15, 90, 5, 55};
   		String key_c, data_c[] = {"fish", "dog", "tree", "human", "cat"};
   	/*
   			 探索キー
   	*/
   		key_n = Integer.parseInt(args[0]);
   		key_c = args[1];
   	/*
   			 整数の場合
   	*/
   					// ソート前の出力
   		System.out.print("sort前   ");
   		for (i1 = 0; i1 < 10; i1++)
   			System.out.print(data_n[i1] + " ");
   		System.out.print("\n");
   					// ソートとその後の出力
   		Arrays.sort(data_n);
   
   		System.out.print("sort後   ");
   		for (i1 = 0; i1 < 10; i1++)
   			System.out.print(data_n[i1] + " ");
   		System.out.print("\n");
   					// 探索
   		k_n = Arrays.binarySearch(data_n, key_n);
   
   		if (k_n >= 0)
   			System.out.print("   " + data_n[k_n] + " が見つかりました\n");
   		else
   			System.out.print("   " + key_n + " は見つかりませんでした\n");
   	/*
   			 文字列の場合
   	*/
   					// ソート前の出力
   		System.out.print("sort前   ");
   		for (i1 = 0; i1 < 5; i1++)
   			System.out.print(data_c[i1] + " ");
   		System.out.print("\n");
   					// ソートとその後の出力
   		Arrays.sort(data_c);
   
   		System.out.print("sort後   ");
   		for (i1 = 0; i1 < 5; i1++)
   			System.out.print(data_c[i1] + " ");
   		System.out.print("\n");
   					// Comparatorを使用したソートとその後の出力（降順）
   		Arrays.sort(data_c, new Comp());
   
   		System.out.print("sort後（降順）   ");
   		for (i1 = 0; i1 < 5; i1++)
   			System.out.print(data_c[i1] + " ");
   		System.out.print("\n");
   					// 探索
   		k_c = Arrays.binarySearch(data_c, key_c);
   
   		if (k_c >= 0)
   			System.out.print("   " + data_c[k_c] + " が見つかりました\n");
   		else
   			System.out.print("   " + key_c + " は見つかりませんでした\n");
   	}
   }
   
   /**********************/
   /* ２つの文字列の比較 */
   /**********************/
   class Comp implements Comparator {
   	public int compare (Object arg1, Object arg2)
   	{
   		return arg2.toString().compareTo(arg1.toString());
   	}
   }
   
   （出力）　test 55 fish と入力した場合
   
   sort前   10 1 45 20 0 -20 15 90 5 55 
   sort後   -20 0 1 5 10 15 20 45 55 90 
      55 が見つかりました
   sort前   fish dog tree human cat 
   sort後   cat dog fish human tree 
   sort後（降順）   tree human fish dog cat 
      fish が見つかりました
   			

[参照]

bsearch