#!/usr/local/bin/tcc -run
#include <stdio.h>
#include <stdlib.h>

#define NUM 20

void quick_sort(int *arr, int left, int right); // クイックソート
int what_kind(int *arr, int size); //ソートされている配列の要素の種類を調べる
int** get2darray( int size); //二次元配列を確保する
void checkarray3(int *arr, int size, int **count); //要素の個数を調べる
void quick_sort2d(int **arr, int left, int right); //二次元配列のクイックソート

int main(void) {
	int arr[NUM] = { 22, 22, 21, 33, 21, 22, 45, 88, 72, 53, 99, 60, 12, 45, 53, 99, 99, 88, 53, 12 };
	int **count;
	int i, kind;

	quick_sort(arr, 0, NUM - 1); //配列ソートする

	kind = what_kind(arr, NUM); //配列の要素の種類を調べる
	count = get2darray(kind); //結果を格納する配列を確保

	checkarray3(arr, NUM, count); //要素を数え結果を配列に格納
	quick_sort2d(count, 0, kind - 1); //個数が多い順にソートする

	for (i = 0; i<kind; i++){ //結果を出力		
		printf("%d : %d個", count[i][0],count[i][1]);
	}
	return 0;
}



void quick_sort(int *arr, int left, int right){ // クイックソート
	int i, last;
	int tmp;

	if (left >= right)
		return;

	last = left;
	for (i = left + 1; i <= right; i++){
		if (arr[i] < arr[left]){
			last++;
			tmp = arr[last];
			arr[last] = arr[i];
			arr[i] = tmp;
		}
	}

	tmp = arr[left];
	arr[left] = arr[last];
	arr[last] = tmp;

	quick_sort(arr, left, last - 1);
	quick_sort(arr, last + 1, right);
}

int what_kind(int *arr, int size){ //ソートされている配列の要素の種類を調べる
	int i, kind = 1, tmp;
	tmp = arr[0];

	for (i = 0; i<size; i++){
		if (tmp != arr[i]){
			tmp = arr[i];
			kind++;
		}
	}
	return kind;
}

int** get2darray( int size){ //二次元配列を確保する
	int i;
	int **arr;
	arr = (int **)malloc(sizeof(int *)*size); 
	if (arr == NULL){
		exit(EXIT_FAILURE);
	}
	for (i = 0; i<size; i++){
		arr[i] = (int *)malloc(sizeof(int) * 2);
		if (arr == NULL){
			exit(EXIT_FAILURE);
		}
	}
	return arr;
}

void checkarray3(int *arr, int size, int **count){ //要素の個数を調べる
	int tmp, cnt = 0, i, j;

	

	tmp = arr[0];
	j = 0;
	for (i = 0; i<size; i++){
		if (tmp == arr[i]){ //同じ数だったらカウントを進める
			cnt++;
		}
		else{ //違う数だったらcountに格納しtmpを更新
			count[j][0] = tmp;
			count[j][1] = cnt;
			tmp = arr[i];
			cnt = 1;
			j++;
		}
	}
	count[j][0] = tmp;
	count[j][1] = cnt;

}

void quick_sort2d(int **arr, int left, int right){ //二次元配列のクイックソート
	int i, j, last, tmp;

	if (left >= right)
		return;

	last = left;
	for (i = left + 1; i <= right; i++){
		if (arr[i][1] > arr[left][1]){
			last++;
			for (j = 0; j < 2; j++){
				tmp = arr[last][j];
					arr[last][j] = arr[i][j];
				arr[i][j] = tmp;
			}
		}
	}
	for (j = 0; j < 2; j++){
		tmp = arr[left][j];
		arr[left][j] = arr[last][j];
		arr[last][j] = tmp;
	}

	quick_sort2d(arr, left, last - 1);
	quick_sort2d(arr, last + 1, right);
}