정렬의 종류

퀵 정렬 - 위키백과, 우리 모두의 백과사전

1. 퀵 정렬(Quick sort)

• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
  비교 정렬: 원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘. 예를 들어 Bubble sort는 비교하는 원소들이 숫자, 문자열, 심지어 복잡한 객체에 대해서도 순서가 결정되어 있다면 적용할 수 있음
  아무리 빨라도 최악의 경우 n log n 시간을 필요로 함.
  비교 정렬이 아닌 알고리즘들은 이런 시간 복잡도의 제약이 없지만, 대신 다른 제약을 가질 수 있음. 예를 들어 기수 정렬은 사전순으로 표기하고 분리하기 쉬운 숫자나 문자열에 대해서는 효과적이지만, 그렇지 않은 객체들에 대해서는 일반 비교 정렬보다 느릴 수 있음.
• n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행
• 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있음.
  (메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문에)
  히트율: 캐시 기억장치가 있는 컴퓨터의 성능을 나타내는 척도, 적중 횟수 / 총 접근 횟수
• 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능
• 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어듦
  때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작. -> 퀵 정렬(Quicksort) 이름의 기원
• 정렬을 위해 평균적으로 O(log n)만큼의 메모리를 필요로 함.
  이는 재귀적 호출로 발생하는 것이며, 최악의 경우 O(n)의 공간복잡도를 보임
• 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속함.

 

• 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬
  • 리스트 가운데서 하나의 원소를 고르고 그것을 피벗이라고 한다.
  • 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
  • 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

 

• 최악 시간복잡도: O(n^2)
• 최선 시간복잡도: O(n log n)
• 평균 시간복잡도: O(n log n)

---

합병 정렬 - 위키백과, 우리 모두의 백과사전

2. 합병 정렬(Merge sort)

• 합병 정렬 또는 병합 정렬은 O(n log n) 비교 기반 정렬 알고리즘.
• 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나.

n-way

• 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할.
  (한 원소만 든 리스트는 정렬된 것과 같으므로)
• 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성. 마지막 남은 부분리스트가 정렬된 리스트

하향식 2-way

• 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
• 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다
• 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다
• 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
• 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

 

• 최악 시간복잡도: O(n log n)
• 최선 시간복잡도: O(n log n)
• 평균 시간복잡도: 일반적으로, O(n log n)
• 공간복잡도: O(n)

---

힙 정렬 - 위키백과, 우리 모두의 백과사전

3. 힙 정렬(Heap sort)

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
• 내림차순 정렬을 위해서는 최소 힙, 오름차순 정렬을 위해서는 최대 힙을 구성하면 됨

 

• n개의 노드에 대한 완전 이진 트리를 구성
  이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성
• 최대 힙을 구성
  최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있음
• 가장 큰 수(루트에 위치)를 가장 작은 수와 교환
• 2-3번째 과정을 반복

 

• 최악 시간복잡도: O(n log n)
• 최선 시간복잡도: O(n log n)
• 평균 시간복잡도: O(n log n)
• 공간복잡도: O(1)

---

삽입 정렬 - 위키백과, 우리 모두의 백과사전

4. 삽입 정렬(Insertion sort)

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 배열이 길어질수록 효율이 떨어지지만 구현이 간단하다는 장점이 있음
• 선택 정렬이나 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠르고, 안정 정렬이며 in-place 알고리즘임

 

• 최악 시간복잡도: O(n^2) 비교 및 교환
• 최선 시간복잡도: O(n) 비교, O(1) 교환
• 평균 시간복잡도: O(n^2) 비교 및 교환
• 공간복잡도: O(n) 전체, O(1) 보조

---

선택 정렬 - 위키백과, 우리 모두의 백과사전

5. 선택 정렬(Selection sort)

• 제자리 정렬 알고리즘의 하나
  • 주어진 리스트 중에 최소값을 찾는다
  • 그 값을 맨 앞에 위치한 값과 교체한다(패스)
  • 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다
• 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 O(n^2) 만큼의 시간이 걸림
• 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있음

 

• 거품 정렬(Bubble sort): 시간 복잡도 O(n^2)인 정렬 알고리즘 중에서 선택 정렬은 버블 정렬보다 항상 우수하다
• 삽입 정렬(Insertion sort): 삽입 정렬은 k번째 반복 이후, 첫 번째 k요소가 정렬된 순서로 온다는 점에서 유사. 하지만 선택 정렬은 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 삽입 정렬은 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있음
• 합병 정렬(Merge sort): 선택 정렬은 합병 정렬과 같은 분할 정복 알고리즘을 사용하지만 일반적으로 큰 배열보다 작은 배열 (요소 10~20개 미만)에서 더 빠르다. 따라서 충분히 작은 하위 목록에만 삽입 정렬 혹은 선택 정렬을 이용해서 최적화하는 것이 좋다.

 

• 최악 시간복잡도: O(n^2) 비교, O(n) 교환
• 최선 시간복잡도: O(n^2) 비교, O(n) 교환
• 평균 시간복잡도: O(n^2) 비교, O(n) 교환
• 공간복잡도: O(1) 예비

---

 

셸 정렬 - 위키백과, 우리 모두의 백과사전

6. 셸 정렬(Shell sort)

• 가장 오래된 정렬 알고리즘의 하나
• 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡함
• 다음과 같은 삽입 정렬의 성질을 이용, 보완한 삽입정렬의 일반화로 볼 수 있음
  • 삽입 정렬은 입력되는 초기리스트가 "거의 정렬"되어 있을 경우 효율적임
  • 삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적임
• 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행
  매개변수 값에 따라 부파일이 발생하며, 매개변수값을 줄이며 이 과정을 반복하고 결국 매개변수 값이 1이면 정렬은 완성
• 다음과 같은 과정으로 나눔
  • 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬
  • 데이터를 다시 잘게 나누어서 삽입 정렬
  • 위 과정을 반복하여 정렬
• 데이터를 나누는 값(이하 N)은 보통 전체에서 2로 나누는 값으로 진행. 그러나 3을 나누고 1을 더하는 경우가 더 빠르다고 알려져 있음
  즉 N/2 보다는 N/3+1이 더 빠르다

 

• 최악 시간복잡도: O(n^2) - worst known worst case gap sequence / O(n log^2 n) - best known worst case gap sequence
• 최선 시간복잡도: O(n log n) - most gap sequences / O(n log^2 n) - best known worst-case gap sequence
• 평균 시간복잡도: 갭 시퀀스에 따라
• 공간복잡도: O(n) 전체, O(1) 보조

---

버블 정렬 - 위키백과, 우리 모두의 백과사전

7. 버블 정렬(Bubble sort)

• 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용됨.
• 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 bubble sort로 명명
• 버블 정렬을 양방향으로 번갈아 수행하면 칵테일 정렬이 됨(8번 정렬)

 

• 배열의 두 수(a, b)를 선택한 뒤, 만약 그 두 수가 정렬되었다면 놔두고, 아니라면 두 수를 바꾸는 방식으로 진행
• 오름차순으로 정렬할 때는 a < b, 내림차순이라면 a > b여야 정렬된 것으로 판단
• 위의 작업을 배열의 처음부터 끝까지 아무 변화가 없을 때까지 반복

 

• 최악 시간복잡도: O(n^2) 비교, O(n^2) 교환
• 최선 시간복잡도: O(n) 비교, O(1) 교환
• 평균 시간복잡도: O(n^2) 비교, O(n^2) 교환
• 공간복잡도: O(1) 보조

---

칵테일 정렬 - 위키백과, 우리 모두의 백과사전

8. 칵테일 정렬(Cocktail sort)

• 칵테일 셰이커 정렬(Cocktail shaker sort)
  양방향 거품 정렬(Bidirectional bubble sort)
  셰이커 정렬(Shaker sort)
• 정렬 알고리즘 중 하나로, 버블 정렬의 변형

 

• 버블 정렬과 다른 점은 버블 정렬은 배열을 앞부터 뒤까지 반복하며 두 수를 바꾸지만, 칵테일 정렬은 배열을 앞에서 뒤까지, 다음은 뒤에서 앞까지, 다음은 다시 앞에서 뒤까지 반복하는 식으로 순서만 다름

 

• 최악 시간복잡도: O(n^2)
• 최선 시간복잡도: O(n)
• 평균 시간복잡도: O(n^2)
• 공간복잡도: O(1)