루트1 [알고리즘] 비교 기반 정렬 문제 정렬 문제→ 여러 방법이 존재하며, 방법마다 특징이 다름 → 시간복잡도, 최적성에 대해 증명이 쉬움 → n개의 서로 다른 수가 주어질 떄, 이들을 이동하여 점점 커지게(오름차순) 또는 점점 작아지게(내림차순)으로 만드는 문제 가정 : 정렬한 데이터가 담긴 배열의 각 원소를 O(1)시간에 접근 가능하다. (= 데이터가 메인 메모리에 저장되어 있다.) 버블 정렬 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해가면서, 큰 수가 오른쪽으로 가도록 교환함. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복 정확성 : 자명함 시간 복잡도 : 처음 가장 큰 원소를 구할 때 n-1번 비교, 두 번째 큰 원소를 구할 때 n-2번 비교 (n-1) + (n-2) + … + 1 =.. 2023. 1. 16. 이전 1 다음 728x90 반응형
