알고리즘 실행시간 비교실행시간의 상한O(n²): 선택 정렬, 버블 정렬O(n log n)O(n): 선형 검색O(log n): 이진 검색O(1) 실행시간의 하한 (개선 전)Ω(n²): 선택 정렬, 버블 정렬Ω(n log n)Ω(n)Ω(log n)Ω(1): 선형 검색, 이진 검색 샌프란시스코 대학교 컴퓨터 과학 부서의 비교 정렬 시각화 도구 버블 정렬 개선정렬이 모두 되어 있는 리스트가 주어진다면 어떨까? 원래의 의사 코드Repeat n-1 times For i from 0 to n-2 If i'th and i+1'th elements out of order Swap them실행시간의 하한: Ω(n²)문제: 이미 정렬되어 ..

정렬된 배열이 정렬되지 않은 배열보다 탐색하기 쉽다. 선택 정렬(Selection Sort)은 배열에서 가장 작은 값을 찾아 첫 번째 위치의 값과 교환하는 방식의 정렬이다.교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.동작 원리정렬되지 않은 숫자들을 오름차순으로 정렬해보자.6 3 8 5 2 7 4 11단계:가장 작은 값인 1을 찾는다첫 번째 값인 6과 교환한다결과: 1 3 8 5 2 7 4 62단계:정렬된 1을 제외하고 두 번째부터 가장 작은 값을 찾는다가장 작은 값인 2를 두 번째 값인 3과 교환한다결과: 1 2 8 5 3 7 4 63단계 이후:이 과정을 더 이상 교환이 일어나지 않을 때까지 반복한다최종 결과: 1 2 3 4 5 6 7 8의사 코드:For i from 0 to n-1 ..