fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. //swap、2つの値を入れ替えるだけ（ソートで必須）
  5. void swap(int *x, int *y){
  6. 	int tmp = *x;
  7. 	*x = *y;
  8. 	*y = tmp;
  9. }
  10.  
  11. //reverse、配列を逆順にする（演習0）
  12. //前と後ろをswapしていくだけ。半分まででOK。
  13. void reverse(int *a, int n){
  14. 	for(int i = 0; i < n/2; i++){
  15. 		swap(&a[i], &a[n-1-i]);
  16. 	}
  17. }
  18.  
  19. //printA、配列を出力するだけ（確認用）
  20. void printA(int *a, int n){
  21. 	for(int i = 0; i < n; i++){
  22. 		printf("%d ", a[i]);
  23.  	}
  24. 	printf("\n");
  25. }
  26.  
  27. //バブルソート（BubbleSort）
  28. //隣同士を比べて逆ならswap。これをn回繰り返すだけ。
  29. //大きいのが後ろに“浮く”イメージ。
  30. //O(n^2) → 2重ループだから。
  31. void bubble_sort(int *a, int n){
  32. 	for(int i = 0; i < n-1; i++){ //後ろからi個は確定
  33. 		for(int j = 0; j < n-1-i; j++){ //隣同士を比較
  34. 			if(a[j] > a[j+1]){
  35. 				swap(&a[j], &a[j+1]);
  36. 			}
  37. 		}
  38. 	}
  39. }
  40.  
  41. //選択ソート（SelectionSort）
  42. //未整列の中から最小値を探して、先頭と入れ替えるだけ。
  43. //毎回「最小値の位置」を探す必要がある。
  44. //O(n^2) → 最小値探しがO(n)、それをn回。
  45. void selection_sort(int *a, int n){
  46. 	for(int i = 0; i < n-1; i++){
  47. 		int min_i = i; //ひとまずi番目を最小と仮定
  48. 		for(int j = i+1; j < n; j++){
  49. 			if(a[j] < a[min_i]){
  50. 				min_i = j;
  51. 			}
  52. 		}
  53. 		swap(&a[i], &a[min_i]); //見つけた最小値と入れ替え
  54. 	}
  55. }
  56.  
  57. //挿入ソート（InsertionSort）
  58. //手札を並べるイメージ。左側は整列済みとして扱う。
  59. //a[i] を一時保存して、適切な位置まで後ろにずらす。
  60. //ほぼ整列済みのデータには超強い。
  61. //O(n^2) → ずらす処理が最大n回、それをn回。
  62. void insertion_sort(int *a, int n){
  63. 	for(int i = 1; i < n; i++){
  64. 		int key = a[i]; //挿入したい値
  65. 		int j = i - 1;
  66. 		while(j >= 0 && a[j] > key){ //keyより大きいのを後ろへ
  67. 			a[j+1] = a[j];
  68. 			j--;
  69. 		}
  70. 	a[j+1] = key; //ここが挿入位置
  71. 	}
  72. }
  73.  
  74. int main(void){
  75. 	int n;
  76. 	scanf("%d", &n);
  77.  
  78. 	int *a = (int *)malloc(sizeof(int) * n);
  79. 	for(int i = 0; i < n; i++){
  80. 		scanf("%d", &a[i]);
  81. 	}
  82.  
  83. 	//ここで好きなソートを試す（コメント切り替え）
  84. 	//bubble_sort(a, n);
  85. 	//selection_sort(a, n);
  86. 	insertion_sort(a, n);
  87.  
  88. 	printA(a, n);
  89.  
  90. 	free(a);
  91.   	return 0;
  92. }
  93.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
8
21 55 5 13 8 2 34 3
stdout
copy 
2 3 5 8 13 21 34 55
https://ideone.com/sBqyzH
第四回復習用
language:
C (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!