C++ Insertion Sort 및 성능 테스트

삽입 정렬

1. 테스트용 랜덤 배열 생성법

ex) 1~100까지 난수를 생성하려면 

최소 + std::rand() % (최대 - 최소 + 1)

#include <cstdlib>

std::srand(5323);

const int SIZE = 15000;

vector<int> test;
for (int count = 0; count < SIZE; ++count)
{
    test.push_back(-SIZE + std::rand() % (SIZE - (-SIZE) + 1));
}

 

2. Insertion Sort 삽입 정렬

vector<int> insertionSort(vector<int> &array)
{
  for (int i = 1; i < array.size(); i++)
  {
    int j = i;
    while (j > 0 && array[j] < array[j - 1])
    {
      swap(array[j], array[j - 1]);
      j--;
    }
  }
  return array;
}

 

3. 메인 함수

랜덤 배열 생성 후, 실행 시간 체크

#include <chrono>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <iterator>

int main()
{
  std::srand(5323);

  const int SIZE = 15000;

  vector<int> test;
  for (int count = 0; count < SIZE; ++count)
  {
    test.push_back(-SIZE + std::rand() % (SIZE - (-SIZE) + 1));
  }

  auto start = std::chrono::high_resolution_clock::now();
  insertionSort(test);  // ref
  auto end = std::chrono::high_resolution_clock::now();

  auto duration1 =
      std::chrono::duration_cast&lt;std::chrono::milliseconds>(end - start);

  // array print
  std::copy(std::begin(test), std::end(test), std::ostream_iterator&lt;int>(std::cout, " "));

  std::cout << "\n";

  std::cout
      << duration1.count() << "ms" << std::endl;
}

 

4. 속도

비교 대상은 안되지만,

Python: 약 6초, C++: 약 1초