알고리즘 중간 정리

내부정렬

모든 데이터를 하나의 배열로 저장 가능 알고리즘

 

외부정렬

데이터가 너무 많아 하나의 배열에 저장 불가능 알고리즘

 

알고리즘의 핵심 요소

교환 선택 삽입

 

버블 정렬 

시간복잡도: O(n^2)

 

단순삽입정렬

- 가장 작은 요소부터 정렬하는 알고리즘

 

장점

정렬을 마친 상태에 가까우면 정렬속도가 매우 빨라진다. 

 

단점

삽입할 위치가 멀리 떨어져있으면 이동해야하는 횟수가 많아짐

 

단순삽입정렬

시간복잡도: O(n^2)

 

셸 정렬

시간복잡도: O(n^1.25

 

 

병합. 합병 정렬

앞 배열, 뒤 배열 정리 후 합치기

 

 

 

크기 비교

1 < n < logn < nlogn < n^2 < n^3 < n^k < 2n