AIZU ONLINE JUDGE ALDS1_1_A - 今日から始める競技プロ日記
はじめに
螺旋本の問題をゆっくり解いていく。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (7件) を見る
今日はALDS1_1_Aの挿入ソートの実装（p. 54）。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_A
3.2 挿入ソート（p. 54）
挿入ソートの疑似コードが与えられるので、自分で実装する
挿入ソートについてなんとなく書く
挿入ソートはかなり直感的なソート。 人が日常の中で何となくやっているソートだと思う。
数列Aが与えれれる。
5 2 4 6 1 3
挿入ソートでは、ソート済みの部分列と、 まだソートされていない部分列に分けてソートを行う。
まずは先頭の5をソート済みとする。
それ以外は未ソートとする。
（ソート済み） 5 | 2 4 6 1 3 （未ソート）
次に未ソートの部分列の中で、 一番左の値をソート済みの部分列の中で適切な場所に挿入する。
つまり、2を挿入する。
2は5よりも小さいので5の前に挿入する。
（ソート済み） 2 5 | 4 6 1 3 （未ソート）
これを繰り返す。
（ソート済み） 2 4 5 | 6 1 3 （未ソート）
（ソート済み） 2 4 5 6 | 1 3 （未ソート）
（ソート済み） 1 2 4 5 6 | 3 （未ソート）
（ソート済み） 1 2 3 4 5 6 | （未ソート）
挿入ソートの計算量
- 最悪：
O(N^2)（厳密には(N^2-N)/2とのこと） - 最良：
O(N)
降順に並んでいる数列を昇順に並べ替えようとするとO(N^2)。
昇順に並んでいる数列を昇順に並べ替えようとするとO(N)。
コード
#include <bits/stdc++.h>
using namespace std;
// ソート対象の配列を出力
void printA(vector<int> A, int N)
{
for(int i = 0; i < N; i++)
{
if(i == N-1) cout << A[i] << endl;
else cout << A[i] << " ";
}
}
// 挿入ソート
vector<int> insertionSort(vector<int> A, int N)
{
for(int i = 1; i < N; i++)
{
int v = A[i];
int j = i-1;
while(j >= 0 && A[j] > v)
{
A[j+1] = A[j];
j--;
}
A[j+1] = v;
printA(A, N); // ステップごとの状態を出力
}
return A;
}
int main()
{
// 入力
int N;
cin >> N;
vector<int> A(N);
for(int i = 0; i < N; i++) cin >> A[i];
// 初期状態の配列を出力
printA(A, N);
// 挿入ソートを実行
A = insertionSort(A, N);
return 0;
}
おわりに
挿入ソートをなんとなく理解できた
