CS/자료구조
[자료구조 및 프로그래밍] 15. O(N²)정렬 방법 별 비교 횟수, 쓰기 횟수 비교
그림과 같이 100만개의 랜덤 성생된 정수가 있다. 이 정수를 각 정렬 방법으로 정렬해보려고 한다. (100만개를 N^2 시간에 정렬하면 시간이 오래 걸려서, 실제로는 100, 200, ..., 900 단위로만 정렬해 볼 것이다.) 정렬을 수행하면서, 비교는 몇번 일어나는지, 정렬을 하기 위해, 기존 배열에 (또는 새로 생성한 배열에) 데이터를 쓰는 행위를 몇번이나 하는지 횟수를 세보고자 한다. 이를 위해 먼저 100만개의 정수가 담긴 데이터를 ' ' 기준으로 끊어 배열에 저장한다. 그리고 각 정렬을 수행한다. 정렬은 사이즈가 100, 200, 300, ..., 900 인 상황을 매번 수행해보면서, 그 때의 비교횟수와 데이터 쓰기 횟수를 카운팅한다. 차례대로 정렬을 구현하고, 횟수를 카운팅한 결과를 출력..
