09-ソート1ソート(25分)

11876 ワード
MOOCデータ構造
N個(長整数範囲)の整数を与え,小さいものから大きいものへのソート後の結果を出力することが要求される.
本問題は,種々の異なるソートアルゴリズムの種々のデータの場合の表現をテストすることを目的とする.各グループのテストデータの特徴は以下の通りである.
データ1:要素が1つしかありません.
データ2:11個の異なる整数で、基本的な正確性をテストします.
データ3:10^3個のランダム整数;
データ4:10^4個のランダム整数;
データ5:10^5個のランダム整数;
データ6:10^5シーケンス整数;
データ7:10^5個の逆シーケンス整数;
データ8:10^5個の基本秩序の整数;
データ9:10^5個のランダム正の整数で、各数字は1000を超えません.
入力形式:
1行目に正の整数N(≦10^5)を入力し、1行目にN個(長整数範囲)の整数を入力し、その間をスペースで区切ります.
出力フォーマット:
1行に小から大へ並べ替えた結果を出力し、数字間は1つのスペースで区切られ、行末に余分なスペースがあってはならない.
入力サンプル:11 4 981 10-17 0-20 29 50 8 43-5出力サンプル:-20-17-5 4 8 10 29 43 50 981
#include 
#include 
#define N 100000
#define Cutoff 10
#define Radix 10

void percdown(long *a, int n, int i);
void merge(long *a, long *tmp, int start, int end, int middle);
void msort(long *a, long *tmp, int start, int end);
void merge_pass(long *a, long *tmp, int n, int length);
void q_sort(long *a, int left, int right);

void bubble_sort(long *a, int n);
void insertion_sort(long *a, int n);
void selection_sort(long *a, int n);
void shell_sort(long *a, int n);
void shellsedgewick_sort(long *a, int n);
void heap_sort(long *a, int n);
void merge1_sort(long *a, int n);
void merge2_sort(long *a, int n);
void quick_sort(long *a, int n);
void radix_sort(long *a, int n);

int main() {
	int i, n;
	long a[N];
	scanf("%d", &n);
	for (i = 0;i < n;i++)
		scanf("%ld", &a[i]);
	radix_sort(a, n);
	printf("%ld", a[0]);
	for (i = 1;i < n;i++)
		printf(" %ld", a[i]);
	return 0;
}

// 
void bubble_sort(long *a, int n) {
	int i, j, flag;
	long temp;
	for (i = n - 1;i > 0;i--) {
		flag = 0;
		for (j = 0;j < i;j++) {
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				flag = 1;
			}
		}
		if (!flag) break;
	}
}

// 
void insertion_sort(long *a, int n) {
	int i, j;
	long temp;
	for (i = 1;i < n;i++) {
		temp = a[i];
		for (j = i; j > 0 && a[j - 1] > temp; j--) 
				a[j] = a[j - 1];
		a[j] = temp;
	}
}

// 
void selection_sort(long *a, int n) {
	int i, j, t;
	long temp;
	for (i = 0;i < n - 1;i++) {
		temp = a[i];
		t = i;
		for (j = i + 1;j < n;j++) {
			if (a[j] < temp) {
				temp = a[j];
				t = j;
			}	
		}
		a[t] = a[i];
		a[i] = temp;
	}
}

// - 
void shell_sort(long *a, int n) {
	int i, j, d;
	long temp;
	for (d = n / 2;d > 0;d /= 2) {
		for (i = d;i < n;i++) {
			temp = a[i];
			for (j = i;j >= d && a[j - d] > temp;j -= d)
				a[j] = a[j - d];
			a[j] = temp;
		}
	}
}

// -sedgewick 
void shellsedgewick_sort(long *a, int n) {
	int i, j, d, si;
	int Sedgewick[] = { 929, 505, 209, 109, 41, 19, 5, 1, 0 };
	long temp;
	for (si = 0;Sedgewick[si] >= n;si++)
		;
	for (;Sedgewick[si] > 0;si++) {
		d = Sedgewick[si];
		for (i = d;i < n;i++) {
			temp = a[i];
			for (j = i;j >= d && a[j - d] > temp;j -= d)
				a[j] = a[j - d];
			a[j] = temp;
		}
	}
}

// 
void heap_sort(long *a, int n) {
	int i;
	long temp;
	for (i = (n - 2) / 2; i >= 0; i--)
		percdown(a, n, i);
	for (i = n - 1;i > 0;i--) {
		temp = a[i];
		a[i] = a[0];
		a[0] = temp;
		percdown(a, i, 0);
	}
}

void percdown(long *a, int n, int i) {
	int child;
	long x = a[i];
	for (;i * 2 + 1 <= n - 1;i = child) {
		child = i * 2 + 1;
		if (child < n - 1 && a[child + 1] > a[child])
			child++;
		if (x >= a[child]) break;
		else a[i] = a[child];
	}
	a[i] = x;
}

// - 
void merge1_sort(long *a, int n) {
	long *tmp = (long*)malloc(n*sizeof(long));
	msort(a, tmp, 0, n - 1);
	free(tmp);
}

void msort(long *a, long *tmp, int start, int end) {
	int middle;
	if (start < end) {
		middle = (start + end) / 2;
		msort(a, tmp, start, middle);
		msort(a, tmp, middle + 1, end);
		merge(a, tmp, start, end, middle);
	}
}

void merge(long *a, long *tmp, int start, int end, int middle) {
	int l, r, s;
	s = start;
	l = start;
	r = middle + 1;
	while (l <= middle && r <= end) {
		if (a[l] <= a[r]) tmp[s++] = a[l++];
		else tmp[s++] = a[r++];
	}
	while (l <= middle) tmp[s++] = a[l++];
	while (r <= end) tmp[s++] = a[r++];
	for (;start <= end;start++)
		a[start] = tmp[start];
}

// - 
void merge2_sort(long *a, int n) {
	int length = 1;
	long *tmp = (long*)malloc(n*sizeof(long));
	while (length < n) {
		merge_pass(a, tmp, n, length);
		length *= 2;
		merge_pass(tmp, a, n, length);
		length *= 2;
	}
	free(tmp);
}

void merge_pass(long *a, long *tmp, int n, int length) {
	int i, j;
	for (i = 0;i + 2 * length <= n;i += 2*length) 
		merge(a, tmp, i, i + 2 * length - 1, i + length - 1);
	if (i + length <= n)
		merge(a, tmp, i, n - 1, i + length - 1);
	else
		for (j = i;j < n;j++)
			tmp[j] = a[j];
}

// 
void quick_sort(long *a, int n) {
	q_sort(a, 0, n - 1);
}

void q_sort(long *a, int left, int right) {
	long pivot, temp;
	int i, j, center;

	if (right - left + 1 > Cutoff) {
		center = (left + right) / 2;
		if (a[center] < a[left]) {
			temp = a[center];a[center] = a[left];a[left] = temp;
		}
		if (a[right] < a[left]) {
			temp = a[right];a[right] = a[left];a[left] = temp;
		}
		if (a[right] < a[center]) {
			temp = a[right];a[right] = a[center];a[center] = temp;
		}
		temp = a[right - 1];a[right - 1] = a[center];a[center] = temp;
		pivot = a[right - 1];

		i = left;
		j = right - 1;
		for (;;) {
			while (a[++i] < pivot);
			while (a[--j] > pivot);
			if (i < j) {
				temp = a[i];a[i] = a[j];a[j] = temp;
			}
			else break;
		}
		temp = a[i];a[i] = a[right - 1];a[right - 1] = temp;

		q_sort(a, left, i - 1);
		q_sort(a, i + 1, right);
	}
	else
		insertion_sort(a + left, right - left + 1);
}

// - 
struct Node {
	int data;
	Node* next;
};
struct Bucket {
	Node *head, *tail;
};

void radix_sort(long *a, int n) {
	int d, di, i, flag;
	long t;
	Bucket b[Radix*2 - 1];//19  -9--1，0，1-9；
	Node *tmp, *p, *list = NULL;

	for (i = 0;i <= (Radix-1) * 2;i++)
		b[i].head = b[i].tail = NULL;
	for (i = n - 1;i >= 0;i--) {
		tmp = (Node*)malloc(sizeof(Node));
		tmp->data = a[i];
		tmp->next = list;
		list = tmp;
	}
	for (d = 1;;d++) {
		p = list;
		flag = 0;
		while (p) {
			t = p->data;
			for (i = 1;i <= d;i++) {
				di = t % Radix;t /= Radix;
			}
			if (di != 0) flag = 1;
			di += Radix-1;
			tmp = p;
			p = p->next;
			tmp->next = NULL;
			if (!b[di].head)
				b[di].head = b[di].tail = tmp;
			else {
				b[di].tail->next = tmp;
				b[di].tail = tmp;
			}
		}

		if (!flag) break;
		else {
			list = NULL;
			for (i = (Radix - 1) * 2;i >= 0;i--) {
				
				if (b[i].head) {
					b[i].tail->next = list;
					list = b[i].head;
					b[i].head = b[i].tail = NULL;
				}
			}
		}
	}

	for (i = 0;i < n;i++) {
		a[i] = b[Radix - 1].head->data;
		b[Radix - 1].head = b[Radix - 1].head->next;
	}
}

テスト結果は以下の通りです.
 
 
 
 
1バブルソート
テストポイント1
答えは正しい
1/1
1
1
テストポイント2
答えは正しい
10/10
1
1
テストポイント3
答えは正しい
2/2
3
1
テストポイント4
答えは正しい
2/2
260
1
テストポイント5
実行タイムアウト
0/2
0
0
テストポイント6
答えは正しい
2/2
39
2
テストポイント7
実行タイムアウト
0/2
0
0
テストポイント8
答えは正しい
2/2
668
2
テストポイント9
実行タイムアウト
0/2
0
0
2ソートの挿入
テストポイント
結果
ポイント/満点
時間使用(ms)
メモリ(MB)
テストポイント1
答えは正しい
1/1
2
1
テストポイント2
答えは正しい
10/10
1
1
テストポイント3
答えは正しい
2/2
2
1
テストポイント4
答えは正しい
2/2
24
1
テストポイント5
答えは正しい
2/2
3719
2
テストポイント6
答えは正しい
2/2
38
2
テストポイント7
答えは正しい
2/2
7592
2
テストポイント8
答えは正しい
2/2
55
2
テストポイント9
答えは正しい
2/2
3649
2
3ソートの選択
パイロット1
答えは正しい
1/1
2
1
テストポイント2
答えは正しい
10/10
2
1
テストポイント3
答えは正しい
2/2
3
1
テストポイント4
答えは正しい
2/2
59
1
テストポイント5
答えは正しい
2/2
9151
2
テストポイント6
答えは正しい
2/2
8199
2
テストポイント7
答えは正しい
2/2
8539
2
テストポイント8
答えは正しい
2/2
9357
2
テストポイント9
答えは正しい
2/2
9145
2
4ヒルソート
ヒル増分
テストポイント1
答えは正しい
1/1
4
1
テストポイント2
答えは正しい
10/10
1
1
テストポイント3
答えは正しい
2/2
2
1
テストポイント4
答えは正しい
2/2
7
1
テストポイント5
答えは正しい
2/2
57
2
テストポイント6
答えは正しい
2/2
44
2
テストポイント7
答えは正しい
2/2
44
2
テストポイント8
答えは正しい
2/2
42
2
テストポイント9
答えは正しい
2/2
51
2
sedgewickインクリメント
テストポイント1
答えは正しい
1/1
1
1
テストポイント2
答えは正しい
10/10
12
1
テストポイント3
答えは正しい
2/2
2
1
テストポイント4
答えは正しい
2/2
6
1
テストポイント5
答えは正しい
2/2
62
2
テストポイント6
答えは正しい
2/2
41
2
テストポイント7
答えは正しい
2/2
52
2
テストポイント8
答えは正しい
2/2
40
2
テストポイント9
答えは正しい
2/2
51
2
5ヒープソート
テストポイント1
答えは正しい
1/1
1
1
テストポイント2
答えは正しい
10/10
2
1
テストポイント3
答えは正しい
2/2
3
1
テストポイント4
答えは正しい
2/2
6
1
テストポイント5
答えは正しい
2/2
54
2
テストポイント6
答えは正しい
2/2
47
2
テストポイント7
答えは正しい
2/2
48
2
テストポイント8
答えは正しい
2/2
47
2
テストポイント9
答えは正しい
2/2
50
2
6集計ソート
テストポイント1
答えは正しい
1/1
1
1
テストポイント2
答えは正しい
10/10
1
1
テストポイント3
答えは正しい
2/2
2
1
テストポイント4
答えは正しい
2/2
6
1
テストポイント5
答えは正しい
2/2
53
2
テストポイント6
答えは正しい
2/2
45
2
テストポイント7
答えは正しい
2/2
56
2
テストポイント8
答えは正しい
2/2
44
2
テストポイント9
答えは正しい
2/2
49
2
7クイックソート
テストポイント1
答えは正しい
1/1
2
1
テストポイント2
答えは正しい
10/10
2
1
テストポイント3
答えは正しい
2/2
2
1
テストポイント4
答えは正しい
2/2
6
1
テストポイント5
答えは正しい
2/2
47
2
テストポイント6
答えは正しい
2/2
40
2
テストポイント7
答えは正しい
2/2
43
2
テストポイント8
答えは正しい
2/2
41
2
テストポイント9
答えは正しい
2/2
44
2
8基数ソート
テストポイント1
答えは正しい
1/1
14
1
テストポイント2
答えは正しい
10/10
2
1
テストポイント3
答えは正しい
2/2
4
1
テストポイント4
答えは正しい
2/2
16
1
テストポイント5
答えは正しい
2/2
80
5
テストポイント6
答えは正しい
2/2
57
5
テストポイント7
答えは正しい
2/2
63
5
テストポイント8
答えは正しい
2/2
55
5
テストポイント9
答えは正しい
2/2
86
5
9 qsort 
#include
テストポイント1
答えは正しい
1/1
1
1
テストポイント2
答えは正しい
10/10
1
1
テストポイント3
答えは正しい
2/2
3
1
テストポイント4
答えは正しい
2/2
6
1
テストポイント5
答えは正しい
2/2
57
2
テストポイント6
答えは正しい
2/2
44
2
テストポイント7
答えは正しい
2/2
46
2
テストポイント8
答えは正しい
2/2
44
2
テストポイント9
答えは正しい
2/2
51
2
10 sort
#include
テストポイント1
答えは正しい
1/1
2
1
テストポイント2
答えは正しい
10/10
2
1
テストポイント3
答えは正しい
2/2
3
1
テストポイント4
答えは正しい
2/2
6
1
テストポイント5
答えは正しい
2/2
47
2
テストポイント6
答えは正しい
2/2
43
2
テストポイント7
答えは正しい
2/2
49
2
テストポイント8
答えは正しい
2/2
44
2
テストポイント9
答えは正しい
2/2
42
2
logrotateメカニズムとモニタリングとの結合テスト
質問F:数独ゲーム