[알고리즘] 정렬 (Swift)

정렬(Sort) 알고리즘이란

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미합니다.

ex ) 큰 순서대로 , 작은 순서대로 , 알파벳 순서대로

 

var arr : [Int] = [12, 24, 40, 9, 8]

arr.sort() // -> [8, 9, 12, 24, 40]
arr.sort(by : >) // -> [40, 24, 12, 9, 8]

var copyArr : [Int] = arr.sorted { $0 < $1 } // copyArr -> [8, 9, 12, 24, 40]

 

Swift에서 원본 배열 순서를 변경하고 싶으면은 sort() , 원본 배열의 사본을 만들어서 사용하고 싶으면은 sorted()를 사용합니다.

 

 

1. 버블정렬

 

버블정렬은 바로 옆에 있는 요소들을 비교해가며 마지막으로 최댓값을 보내는 정렬을 말합니다.

 

 

 

입력값만큼 n 번 반복하고 n번의 교환이 일어나기 때문에 시간복잡도는 평균, 최악, 최선 O(N^2) 입니다.

가장 이해하기 쉽고 구현하기 쉬운 알고리즘이지만 시간복잡도에서 이득을 보기 힘듦으로 잘 사용하지는 않습니다.

 

2. 선택정렬

 

선택 정렬은 정렬되지 않은 데이터들에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해가는 방식입니다.

 

배열 데이터 중 가장 작은 데이터의 위치와 맨 앞에 있는 데이터와 바꾸는 과정을 반복합니다.

맨 처음 위치를 뺀 나머지 배열을 위의 방법으로 교체를 하는 과정을 반복합니다.

 

n개의 주어진 배열을 비교하는 과정 n번을 반복함으로 시간복잡도는 최선 , 평균, 최악 O(N^2)으로 동일합니다.

시간 복잡도가 O(N^2)임으로 비효율적입니다.

 

 

3. 삽입정렬

 

삽입정렬은 2번째 원소부터 시작하여 그 앞의 원소들과 비교해 가면서 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘입니다.

 

데이터가 모두 정렬되어 있는 경우에는 n번의 과정만 반복함으로 시간복잡도 O(N) 을 가지고 평균과 최악은 O(N^2)의 시간복잡도를 갖게 됩니다.

 

 

 

4. 퀵정렬

 

퀵 정렬은 평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 사용하는 정렬 알고리즘입니다.

분할 정복 방법을 사용하여 주어진 배열을 정렬합니다.

 

배열 가운데중 하나의 원소를 기준원소로 잡습니다(pivot)

피벗보다 작은 수는 피벗 왼쪽에 나머지는 피벗의 오른쪽에 오도록 재배치합니다.

피벗 왼쪽과 오른쪽을 독립적으로 정렬합니다(배열의 길이가 1일때 멈추도록).

 

평균적인 시간복잡도는 O(nlogn) 이지만 pivot을 계속 최대값, 최소값으로 설정했을때 O(N^2)의 시간복잡도를 가집니다. 

평균적인 경우 다른 정렬보다 빠른 장점을 가집니다.

 

 

5. 병합정렬

 

합병 정렬이라고도 부르며 분할 정복 방법을 사용하여 수어진 배열을 정렬합니다.

 

 

주어진 배열을 중간지점 계산을 통해 분할 할 지점을 정한후 나눕니다

나눈 각각의 배열을 독립적으로 정렬합니다.

그 배열을 병합하는 과정을 거쳐 반복하면은 정렬된 배열을 얻을 수 있습니다.

평균 , 최악 , 최선의 시간복잡도는 O(nlogn)으로 동일합니다.

 

 

정렬 시간복잡도 정리(최악, 평균 , 최선 순)

 

버블정렬 : O(N^2) O(N^2)  O(N^2)

 

선택정렬 : O(N^2) O(N^2)  O(N^2)

 

삽입정렬 : O(N^2) O(N^2)  O(N) 

 

퀵정렬 : O(N^2) O(NlogN) O(NlogN)

 

병합정렬 : O(NlogN) O(NlogN) O(NlogN)

 

 

 

 

왜 사용해야할까 or 나만의 고민

버블정렬과 선택정렬은 구현이 쉬운 대신 시간이 오래걸려 비효율적임

삽입정렬의 경우 최선의 경우 O(N)으로 매우 빠르지만 최악은 O(N^2)임으로 데이터에 따라 성능차이 발생

퀵정렬의 경우 O(NlogN) 으로 빠른 시간을 가지지만 PIVOT에 따라 성능 차이가 심하다( O(N^2) )

병합정렬의 경우 항상 O(NlogN)으로 빠른 편이지만 추가적인 메모리 공간을 필요로 한다( 병합 과정시 )