mergesort
-
[Algorithm] - 정렬Algorithm/Algorithm 2022. 9. 2. 14:06
알고리즘이란? 가정 : 정렬할 데이터가 담긴 배열(리스트)의 각 원소를 O(1) 시간에 접근 가능한가? 결과 : C , Python과 같은 배열인 경우 가능 하지만, 그렇지 않은 경우가 있다. 데이터가 HDD 에 있다면 ? 메인 메모리에 올라와 있어야만 이 가정이 통한다. 정렬 1. 버블 정렬 시간 복잡도 : O(N^2) Stable Sort ( 같은 값이라 하여도 순서를 보장 ) 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환 이 과정을 다시 나머지 n-1개 수에 대해서 반복 2. 삽입 정렬 시간 복잡도 최악의 경우 : O(N^2) , 최상 O(N) Stable Sort ( 같은 값이라 하여도 순서를 보장 ) 정렬 대상이 될 원소를 두 부분으로 나눔 앞은 '이미 정..