September 15, 2021

정렬

• 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

선택 정렬의 시간 복잡도

$N + (N-1) + (N-2) + ... + 2 = (N^2+N-2)/2=O(N^2)$

삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

삽입 정렬의 시간 복잡도

최악의 경우 O(N^2)이다. 하지만 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 최선의 경우(이미 정렬되어 있는 경우) O(N)의 시간 복잡도를 가진다.

퀵 정렬