정렬 알고리즘 정리(삽입정렬, 선택정렬, 버블정렬, 병합정렬, 퀵정렬, 힙정렬, 기수정렬)

정렬 알고리즘 중 몇 가지 유명한 것들을 정리해보자.

1. 삽입정렬

왼쪽의 이미 정렬된 리스트에 그 다음 수를 삽입한다. 이 방식으로 왼쪽 끝부터 오른쪽 끝까지 진행한다.

최악 : O(n^2)

2.  선택정렬

왼쪽의 이미 정렬된 리스트를 제외한 나머지 중 가장 작은 수를  정렬된 리스트 바로 다음(바로 왼쪽) 수와 바꾸어준다. 이 방식으로 왼쪽 끝부터 오른쪽 끝까지 진행한다.

최악 : O(n^2)

3. 버블정렬

이웃한 둘을 모두 비교하여 왼쪽 둘 부터 오른쪽에 큰수가 가도록 순서를 모두 바꾼다. 그렇게 되면 가장 큰 수가 제일 오른쪽에 가게된다. 이 방식을 반복한다.

최악 : O(n^2)

4. 병합정렬

전체 리스트를 딱 반으로 나눠 각각에 대해 병합정렬을 한다. 그렇게 하다보면 모두 하나의 데이터를 가지는 리스트가 될 것인데 이를 반대로 나눴던 두 개씩 짝지어 합친다. 합칠 때에는 이미 순서로 배열되어 있는 두 개의 리스트를 합치는 것이기 때문에 두 개의 리스트 맨 앞에 숫자들을 비교해서 작은거 순서대로 계속 넣다보면 자동으로 순서 배열되어 합쳐진다.

최악 : O(n*lg(n))

5. 퀵정렬

기준 피봇이 될 어떤 수를 고르고 그 수를 기준으로 작은 수들을 왼쪽에, 큰 수들을 오른쪽으로 옮기고 이제 피봇 양쪽 리스트 각각에 대해 퀵정렬을 한다. 이 방식을 반복한다.(작은 수들을 왼쪽에 큰 수들을 오른쪽으로 옮기는 방법은 포인터 p1을 제일 왼쪽부터 쭉 오른쪽으로 가면서 피봇보다 큰수를 발견하는 순간 멈추고, 제일 오른쪽부터 쭉 왼쪽으로 가면서 피봇보다 작은 수를 발견하는 순간 멈춰서 그 둘을 교환하는데 이를 끝까지 하다보면 순서대로 배열 가능하다)

최악 : O(n^2)

6. 힙정렬

이분트리구조를 이용하여 순서대로 쫙 쓴 다음에 밑에 트리부터 차근차근 비교해가며 순서를 바꾸며 계속 큰 트리로 올라가며 정렬한다.

(조금 복잡하기에 제일 이해가 잘되는 블로그 주소 추가-> http://zeddios.tistory.com/56)

최악 : O(n*lg(n))

7. 기수정렬

일의 자리만 보고 먼저 크기순으로 먼저 배열하고, 그 다음 십의 자리를 보고 크기순으로 배열하고, 계속 자리수가 올라가며 이 방식을 반복한다.

최악 : O(n*k)(최대 k자리수 까지 존재한다 가정) -> 따라서 최대 자리수k가 n보다 월등히 작을때 사용하면 효율적이다