Submission #35819

ソースコード

#include <cstdio>
#include <algorithm>
#include <stack>
#define rep(i,n) for(int i=0; i<(n); ++i)
using std::swap;
 
void insertion_sort(int[], int, int);
 
// shell-sort シェルソート
// 挿入ソートの強化版: O(N^1.25)
void sort(int a[], int n)
{
   std::stack<int> G;
   for (int h=1; h<n; h = 3*h + 1) {
      G.push(h);
   }
 
   while (!G.empty()) {
      insertion_sort(a, n, G.top());
      G.pop();
   }
 
   return;
}
 
void insertion_sort(int a[], int n, int g)
{
   for (int i=g; i < n; ++i) {
      int tmp = a[i];
      int j = i-g;
      while (j >= 0 && a[j] < tmp) {
         a[j+g] = a[j];
         j -= g;
      }
      a[j+g] = tmp;
   }
   return;
}
 
int main()
{
   int n;
   int a[102];
 
   scanf("%d", &n);
   rep(i, n)
      scanf("%d", a+i);
 
   sort(a, n);
 
   rep(i, n)
      printf("%d\n", a[i]);
 
   return (0);
}

ステータス

項目	データ
問題	0930 - 背の順
ユーザー名	Arumakan_ei1727
投稿日時	2018-05-16 19:15:48
言語	C++11
状態	Accepted
得点	1
ソースコード長	905 Byte
最大実行時間	28 ms
最大メモリ使用量	556 KB

セット

	セット	得点	Cases
1	ALL	1 / 1	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
rnd_1.txt	AC	19 ms	476 KB	1
rnd_2.txt	AC	28 ms	460 KB	1
rnd_3.txt	AC	18 ms	444 KB	1
rnd_4.txt	AC	21 ms	556 KB	1
rnd_5.txt	AC	18 ms	544 KB	1
sample.txt	AC	25 ms	528 KB	1