C++で挿入ソートの問題であるAIZU ONLINE JUDGEのALDS_1_1_Aを解きました。


【目次】
問題概要
挿入ソートの実装




問題概要


N 個の要素を含む数列 A を昇順に並び替える挿入ソートのプログラムを作成してください。


入力例
6
5 2 4 6 1 3

出力例
5 2 4 6 1 3
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

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_Aより



挿入ソートの実装


#include <iostream>

using namespace std;

void insertSort(int* A, int n){
for(int i=0; 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;

// 結果出力
for(int i=0; i<n-1; ++i){
cout << A[i] << " ";
}
cout << A[n-1] << endl;
}
}

int main(void){
int n;
cin >> n;
int *nums = new int[n];
for (int i=0; i<n; ++i){
cin >> nums[i];
}
insertSort(nums, n);
return 0;
}