정렬 알고리즘

정렬 알고리즘이 왜 중요한가?

- 컴퓨터 분야에서 중요시되고 탐색에 용이하다. 프로그래밍과 알고리즘 이해에 많은 도움이 된다. 

 

- 버블 정렬 

가장 기초, 인접한 두 요소를 비교해가면서 정렬을 하는 방식. 

구현이 매우 간단함. 단점은 순서에 맞지 않는 요소들의 교환이 자주 일어나는 단점이 있다. 

시간 복잡도는 최악과 평균 모두 O(n^2). 최선일 때는 O(n)이지만 자주 일어나지 않는다. 

 

- 선택 정렬

전체 범위에서 차례대로 가장 작은 숫자를 탐색하고, 가장 왼쪽부터 차례대로 교환하는 방식. 

전체를 돌면서 최소를 구하고 가장 왼쪽 요소와 교환해준다. 

장점은 자료 이동 횟수가 미리 결정된다는 것이다. 단점은 값이 같은 요소가 있다면 상대적인 위치가 변경될 수 있다. 같은 1이어도 정렬 이후에 이 순서가 달라질 수 있다. 

시간 복잡도는 최선, 최악, 평균 모두 O(n^2)이다. 

 

- 삽입 정렬

모든 요소를 앞에서부터 이미 정렬된 배열과 비교하여 자신의 위치를 찾아 삽입하는 방식이다. 이미 정렬된 배열에서 자기 자신의 위치를 찾아 삽입된다고 하여 삽입 정렬이라고 한다. 

장점은 최선의 경우 O(n)이 나온다. 단점은 요소가 너무 많으면 비교적 많은 이동을 해야 하므로 성능이 좋지 않다. 최악과 평균은 O(n^2)이고 최선은 O(n)이다. 

 

- 병합 정렬

복잡하지만 효율젹인 알고리즘. 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방식이다. 병합 정렬은 분할보다는 병합 과정에서 정렬이 이루어져서 이름도 병합 정렬이다. 

데이터 분포의 영향을 덜 받는다. 단점은 요소를 배열로 구성하면, 임시 배열이 필요하다. 시간 복잡도는 O(nlogn)이다. 

 

- 퀵 정렬

복잡하지만 효율적인 알고리즘. 특정 요소를 기준점(pivot)으로 잡고, 기준점보다 작은 요소는 왼쪽, 기준점보다 큰 요소는 오른쪽으로 두고, 왼쪽과 오른쪽을 각각 정복하는 방식, 다른 정렬 알고리즘보다 효율적이고 빨라 퀵 정렬이라고 한다. 

장점은 평균 실행시간이 다른 알고리즘보다 빠른 편이다. 단점은 pivot에 따라 성능 차이가 심하다는 것이다. 시간 복잡도는 퀵 정렬은 pivot이 중간에 가까운 값을 찾을수록 성능이 좋다. 최악은 O(n^2), 평균은 O(nlogn)

 

정렬 알고리즘 선택시 고려 사항. 

시간 복잡도가 전부는 아니다!! 알고리즘 별로 각각 장단점이 있으므로 상황에 맞게 선택한다. 

정렬 후 안정성을 보장하는 알고리즘, 버블, 삽입, 병합. 

선택, 퀵, 힙은 안정성이 보장되지 않는다. 

공간 복잡도를 고려해야할 때도 있다.