【알고리즘】 1-1강. 정렬 알고리즘 실험

1-1강. 정렬 알고리즘 실험

 

추천글 : 【알고리즘】 1강. 정렬 알고리즘  

---

1. 개요 [본문]

2. 정렬 알고리즘 실험 [본문]

3. 실험을 수행한 컴퓨터의 사양 [본문]

---

 

1. 개요 : 파이썬 프로그램 실행을 위하여 3.8 버전으로 jupyter notebook을 사용 [목차]

 

 

2. 정렬 알고리즘 실험 : 이 문제를 푸는 데 있어서 데이터의 범위는 0 ~ input_size-1를 고려 [목차]

⑴ 정렬 알고리즘의 구현

① bubble sort 알고리즘

○ best case : swap이 최소로 일어나는 [1, 2, 3, ··· ]과 같은 경우

○ worst case : swap이 최대로 일어나는 [9, 8, 7, ··· ]과 같은 경우

 

 

② insert sort 알고리즘

○ best case : i-2번째 원소만 체크하는 [1, 2, 3, ··· ]과 같은 경우

○ worst case : 0부터 i-2번째 원소를 모두 체크하는 [9, 8, 7, ··· ]과 같은 경우

 

 

③ selection sort 알고리즘

○ best case : swap이 일어나는 [1, 2, 3, ··· ]과 같은 경우

○ worst case : swap이 최대로 일어나는 [9, 8, 7, 6, ··· ]과 같은 경우

 

 

④ merge sort 알고리즘

○ best case : 첫 번째 while문을 가장 빨리 통과하는 [1, 2, 3, ··· ], [9, 8, 7, ··· ] 등

○ worst case : 두 번째 코드 참고

○ https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur

○ https://nate9389.tistory.com/130

○ merge sort의 worst-case는 예를 들면, 최초에는 연속된 숫자열이 있을 때 홀수와 짝수를 분리하게 됨

○ 이를 확장을 하면 f([0, 1, 2, 3, 4, 5, 6, 7]) = (f([0, 2, 4, 6]), f([1, 3, 5, 7]))이 되고, f([0, 2, 4, 6]) = (f([0, 4]), f([2, 6]))과 같이 되는데 이는 재귀적으로 충분히 구현 가능한 알고리즘

 

 

⑤ quick sort (non-in-place) 알고리즘

○ best case : 나누어지는 족족 반씩 분할되는 경우. 두 번째 코드를 참고

○ https://stackoverflow.com/questions/32556521/java-quicksort-best-case-array-generation

○ https://nate9389.tistory.com/130 

○ 단, 첫 번째 링크에서 약간의 오류가 있어 수정함

○ 재귀적으로 best-case를 생성하는 함수 f를 정의할 수 있음

○ 즉, f([1, 2, 3, 4, 5, 6, 7, 8, 9]) = (5, f([1, 2, 3, 4]), f([6, 7, 8, 9]))이고, f([1, 2, 3, 4]) = (3, f([1, 2]), f([4]))인 식

○ worst case : 나누어지는 족족 한쪽으로만 몰리는 [1, 2, 3, ··· ]과 같은 경우

 

 

○ quick sort는 worst case에서 memory limit을 초과하는 문제, 재귀함수 호출 횟수 제한을 초과하는 문제 발생

○ 이로 인해 worst case에서의 merge sort 구현에 있어서 quick_sort 부분을 크게 수정

○ 즉, 재귀적으로 qs를 호출하는 부분을 지우고 오른쪽 부분에 대한 partition을 수행하는 식으로 코드를 수정

 

 

⑥ counting sort 알고리즘

○ 알고리즘을 보면 best case와 worst case가 뚜렷하게 나오는 건 아님

○ 다만, c라는 배열의 크기에 따른 자료 입출력 속도가 중요할 것으로 보임

○ best case : 배열 l에 오직 한 가지의 원소만 있는 경우

○ worst case : 배열 l의 어느 두 원소도 동일하지 않은 경우정

○ 이를 위해 1 ~ input_size까지의 수를 랜덤하게 배정

○ m = input_size로 둠

 

 

⑦ radix 알고리즘

○ best case : 모든 숫자가 동일한 경우

○ worst case : 각 자릿수의 종류가 최대한 다양한 경우

○ digit의 개수에 의한 영향을 최소화하고 오로지 input_size에 의한 영향을 보기 위하여 1,000,000 + 1, ··· , 1000,000 + input_size와 같이 나타내어 digit의 개수를 7로 통일

 

 

⑵ 각 알고리즘의 best case에서의 실행시간 비교

 

 

⑶ 각 알고리즘의 average case에서의 실행시간 비교

 

 

⑷ 각 알고리즘의 worst case에서의 실행시간 비교

 

 

⑸ big O time complexity와 실제 실행시간의 관계

① best case 

○ log f(N) / log N의 기울기를 보니 예상대로 bubble sort, selection sort는 N², 나머지 알고리즘은 N의 big O time complexity를 가짐

○ selection sort는 bubble sort에 비해 swap의 수가 적은 만큼 operation time에서도 예상대로의 대소관계가 나타남

○ merge sort 또는 quick sort는 큰 input을 대비할 부수적인 코드상의 장치를 만드는데 operation time을 할당하는 반면 insertion sort에서는 best case에 있어서 straight-forward하게 작동하므로 가장 빨랐음

○ radix sort는 counting sort에 비해 log 7 로그눈금간격만큼 위에 있음을 확인할 수 있었음

② average case

○ log f(N) / log N의 기울기를 보니 예상대로 bubble sort, insertion sort는 N², counting sort, radix sort는 N의 big O time complexity를 가짐

○ merge sort, quick sort의 big O time complexity는 N log N인데 N처럼 나타난 것은 N ≫ 1에 대해 N이 log N에 비해 상당히 커지기 때문으로 보임

○ selection sort는 bubble sort에 비해 swap의 수가 적은 만큼 operation time에서도 예상대로의 대소관계가 나타남

○ quick sort가 merge sort보다 더 빠르다는 점은 주목할 만함

○ radix sort는 counting sort에 비해 log 7 로그눈금간격만큼 위에 있음을 확인할 수 있었음

③ worst case

○ log f(N) / log N의 기울기를 보니 예상대로 bubble sort, insertion sort, selection sort, quick sort는 N², counting sort, radix sort는 N의 big O time complexity를 가짐

○ merge sort의 big O time complexity는 N log N인데 N처럼 나타난 것은 N ≫ 1에 대해 N이 log N에 비해 상당히 커지기 때문으로 보임

○ selection sort는 bubble sort에 비해 swap의 수가 적은 만큼 operation time에서도 예상대로의 대소관계가 나타남

○ quick sort는 best case, average case에 비해 달라진 시간복잡도를 가진다는 점이 눈에 띔

○ radix sort는 counting sort에 비해 log 7 로그눈금간격만큼 위에 있음을 확인할 수 있음 

④ 특히 input size가 작을 때 best, average, worst 순서대로 operation time이 길어지지 않는 경우가 더러 있었는데 운영체제의 스케줄링에 따라 프로그램 실행을 위한 컴퓨터의 리소스 할당이 일정하지 않기 때문

⑤ 특히 input size가 작을 때 알고리즘 간의 실행시간 대소관계가 분명하지 않은 경우가 더러 있었는데 운영체제의 스케줄링에 따라 프로그램 실행을 위한 컴퓨터의 리소스 할당이 일정하지 않기 때문

⑹ 부록

① time.perf_counter()의 용례

 

 

② random sample 생성

 

 

③ average case : 랜덤하게 5개의 결과를 만들어서 그것의 평균을 구함

 

 

3. 실험을 수행한 컴퓨터의 사양 [목차]

⑴ CPU의 종류 및 성능 : Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz

⑵ 운영체제의 이름 및 version : Microsoft Windows 10 Pro

⑶ 장착된 DRAM의 종류 및 크기 : 32.0GB DDR3

 

입력: 2021.09.29 00:25