[알고리즘] 정렬

정렬 (Sorting)

정렬은 데이터를 특정한 기준에 따라서 순차적으로 나열하는 것이다. 흔히 사용하는 내림차순이나 오름차순 역시 이 정렬을 통해 이루어진다. 이진탐색이라는 탐색기법은 정렬과정을 거친 후에만 사용이 가능하다. 

정렬알고리즘은 Comparison Sorting Algorithm(비교방식 알고리즘)과 non - Comparison Sorting Algorithm 이렇게 크게 두가지로 나눌 수 있다. 비교방식 알고리즘에는 선택정렬, 삽입정렬, 퀵정렬 등이 있고, non-비교방식 알고리즘에는 계수 정렬이 있다.

---

선택 정렬 (Seletion Sort)

 

선택 정렬은 배열에서 가장 작은 데이터를 선택하여 다른 데이터와 자리를 바꾸는 알고리즘이다. 일반적으로 쉽게 떠올릴 수 있다.

 

1. 정렬되지 않은 배열에서 가장 작은 데이터를 찾는다.
2. 정렬되지 않은 배열의 첫번째 값과 1에서 찾은 데이터를 바꿔준다. (Swap!)
3. 1과 2를 반복한다.

 

선택 정렬

 

공간 복잡도 : O(1)

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

 

---

삽입 정렬 (Insertion Sort)

 

삽입 정렬은 말 그대로 데이터를 삽입시켜서 배열을 정렬한다. 데이터가 n개 있다고 할 때, i번째 원소를 정렬할 때 i -1 까지의 데이터는 이미 정렬되어 있다고 가정한다.

 

1. i번째 데이터와 i-1번째 데이터를 비교한다.
2. i번째 데이터가 더 작다면 0번째 데이터까지 비교하다가 i번째 데이터보다 더 작은 데이터가 나온다면 그 데이터 왼쪽에 삽입한다.
3. 1과 2를 반복한다.

삽입 정렬

공간 복잡도 : O(1)

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

 

 

삽입 정렬은 원소가 거의 정렬되어있을때 매우 빠르게 동작한다. 최선의 경우 O(N)이면 해결된다. 원소 하나만 정렬시킨다고 가정할 때, 그 원소만 원위치에 삽입시킬 수 있도록 탐색하면 된다. 거의 정렬되어 있는 원소를 정렬할 때 강점을 보인다는 것은 다음에 나올 퀵 정렬과 반대되는 성격을 지닌다.

---

 

퀵 정렬 (Quick Sort)

 

퀵 정렬은 가장 많이 사용되는 정렬 알고리즘 중에 하나이다. 그만큼 효율이 좋다는 뜻이기도 하다.

퀵정렬은 피벗(pivot)을 사용한다. 리스트의 첫번째 데이터가 피벗으로 캐스트된다.

이제 탐색의 시작이다. 왼쪽에서부터 피벗값보다 큰 데이터를 찾고, 오른쪽에서부터는 피벗값보다 작은 데이터를 찾는다. 두 개의 데이터를 찾았다면, 그 두 데이터의 위치를 바꿔준다. 이 과정을 반복해주는데 만약 왼쪽에서 시작하는 탐색과 오른쪽에서 시작하는 탐색이 서로 교차되면 그 교차된 순간의 작은 값과 피벗값을 교체한다.

 

그렇게 되면 현재 피벗의 위치를 기준으로 좌측은 피벗값보다 작은 수들이, 오른쪽은 피벗값보다 큰 수들이 모여있다.

피벗을 기준으로 분할을 완료하였다.

분할된 파트에서 앞서 했던 과정을 반복한다. 왼쪽 리스트의 피벗값은 제일 앞의 데이터가 되고, 오른쪽 리스트의 피벗값은 구 피벗값의 오른쪽 데이터가 된다. 이 과정을 언제까지 반복하느냐?! 바로 리스트의 길이가 전부 1이 될때까지 한다.

 

퀵정렬은 재귀함수를 사용하여 구현할 수 있다.

퀵 정렬

 

while 문 안에 또 while 문 게다가 재귀 호출이라니,, 그래도 앞선 설명을 직관적으로 보인 코드이다.

 

아래는 파이썬의 장점을 살린 코드이다. 정통 퀵 정렬의 분할 방식과는 조금 다른데, 피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간 면에서는 조금 비효율적이다.

 

파이썬의 장점을 살린 퀵 정렬

 

퀵 정렬은 원소들이 흩어져있을 때 최대 효과를 발휘한다. 만약 원소가 거의 정렬되어있다면 오히려 시간복잡도가 늘어난다.

퀵 정렬의 평군 시간 복잡도는 O(NlogN)이고, 최악의 경우 시간 복잡도는 O(N^2)이다.