응용된 정렬 방법들 (셸, 병합, 퀵)에 대해 알아보자

응용된 정렬 방법들 (셸, 병합, 퀵)

이 게시글은 정렬의 코드보단 정렬의 방법과 특징에 비중을 두고 있습니다.

기본적인 정렬 방법들 (선택, 삽입, 버블) 보러가기

정렬의 종류와 시간복잡도

정렬은 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬, 병합 정렬, 퀵 정렬로 이루어져있으며,

각각의 특징이 있으므로 상황을 고려해서 쓰는 게 좋다.

응용된 정렬 알고리즘(1) - 셸 정렬(Shell Sort)

셸 정렬의 과정

셸 정렬은 삽입정렬을 보완한 알고리즘이다.

1. 일정한 간격 gap끼리 묶어 삽입 정렬을 수행(gap=배열의 길이/2)

2. 간격을 줄여나가면서(gap = gap/2) 간격(gap)이 1이 될 때까지 삽입정렬을 반복

---

직접 짧은 정렬을 만들까하다가 셸 정렬을 보여주기에는 조금 긴 정렬이 나을 것 같아 동영상의 정렬을 참고했다. (동영상은 셸 정렬과정 아래에 있다.)

초기 정렬 상태. gap=5(gap=배열의 길이(10)/2)

• 5번째 값(gap)과 5가 차이나는 0번째(5-5=0)와 비교한다.
  • 73(0번째) > 41(5번째)이기 때문에 값을 바꿔준다.
• 6번째 값과 5가 차이나는 1번째(6-5-1)와 비교한다.
  • 67(1번째) < 83(6번째)이기 때문에 값을 바꾸지 않는다.
• 7번째 값과 2번째와 비교한다.
  • 56(2번째) > 37(7번째)이기 때문에 값을 바꿔준다.
• 8번째 값과 3번째와 비교한다.
  • 32(3번째) = 32(8번째)이기 때문에 값을 바꾸지 않는다.
• 9번째 값과 4번째와 비교한다.
  • 52(4번째) > 10(9번째)이기 때문에 값을 바꿔준다.

첫 번째 정렬이 끝난 후의 정렬상태이다. gap = gap/2이기 때문에 2가 된다.

• 2번째 값(gap)과 2가 차이나는 0번째(2-2=0)와 비교한다.
  • 41(0번째) > 37(2번째)이기 때문에 값을 바꿔준다.
• 3번째 값과 2가 차이나는 1번째(3-2=1)와 비교한다.
  • 67(1번째) > 32(3번째)이기 때문에 값을 바꿔준다.
• 4번째 값과 2가 차이나는 2번째(4-2=2)와 비교한다.
  • 41(2번째) > 10(4번째)이기 때문에 값을 바꿔준다.
  • 여기까지하면 아래 사진처럼 된다.

하지만 여기서 끝나지 않고 현재 10의 자리(2)에서 gap을 빼도 마이너스 값이 나오지 않는다.

(2-2=0). 즉, 여기서 그치지 않고 0번째인 37과도 비교할 수 있다.

• 37(0번째) > 10(2번째)이기 때문에 값을 바꿔준다.
• 5번째 값과 3번째 값을 비교한다.
  • 67(3번째) < 73(5번째)이기 때문에 값을 바꾸지 않는다.
  • 여기서 값을 바꾸지 않으면 다음 값으로 넘어간다.
• 6번째 값과 4번째 값을 비교한다.
  • 41(4번째) < 83(6번째)이기 때문에 값을 바꾸지 않는다.
• 7번째 값과 5번째 값을 비교한다.
  • 73(5번째) > 56(7번째)이기 때문에 값을 바꿔준다.
  • 5번째 값과 3번째 값(5-2)을 비교한다.
    • 67(3번째) > 56(5번째)이기 때문에 값을 바꿔준다.
    • 3번째 값과 1번째 값(3-1)을 비교한다.
      • 32(1번째) < 56(3번째)이기 때문에 값을 바꾸지 않는다.
• 8번째 값과 6번째 값을 비교한다.
  • 83(6번째) > 32(8번째)이기 때문에 값을 바꿔준다.
  • 6번째 값과 4번째 값을 비교한다.
    • 41(4번째) > 32(6번째)이기 때문에 값을 바꿔준다.
    • 4번째 값과 2번째 값을 비교한다.
      • 37(2번째) > 32(4번째)이기 때문에 값을 바꿔준다.
      • 2번째 값과 0번째 값을 비교한다.
        • 10(0번째) < 32(2번째)이기 때문에 값을 바꿔주지 않는다.
• 9번째 값과 7번째 값을 비교한다.
  • 73(7번째) > 52(9번째)이기 때문에 값을 바꿔준다.
  • 7번째 값과 5번째 값을 비교한다.
    • 67(5번째) > 52(7번째)이기 때문에 값을 바꿔준다.
    • 5번째 값과 3번째 값을 비교한다.
      • 56(3번째) > 52(5번째)이기 때문에 값을 바꿔준다.
      • 3번째 값과 1번째 값을 비교한다.
        • 32(1번째) < 52(3번째)이기 때문에 값을 바꿔주지 않는다.

이후 gap을 1로 바꿔준 후(2/2=1) 똑같이 반복한다.

아래 영상과 함께 확인해보면 도움이 된다.

https://www.youtube.com/watch?v=qzXAVXddcPU

셸 정렬의 시간복잡도

• Best

  

• Worst

셸 정렬의 특징

장점

• 삽입 정렬을 보완한 방법이기 때문에 삽입 정렬보다 속도가 훨씬 빠르다.
• 알고리즘이 간단하다.

응용된 정렬 알고리즘(2) - 병합 정렬(Merge Sort)

병합 정렬의 과정

값을 병합하면서 정렬하는 알고리즘이다.

1. 값이 하나가 될 때 까지 분할한다.
2. 오름차순으로 정렬 한 뒤에 병합한다.
3. 정렬된 두 그룹을 병합한다.
4. 한 그룹이 될 때까지 반복한다.

---

타 사이트의 예시를 참고했다. (ELE428 Data Structures and Algorithms)

초기 배열 상태이다.

값이 하나가 될 때 까지 분할한다.

• [19, 6, 42, 72, 29, 40, 27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
• [19, 6, 42, 72] / [29, 40, 27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
• [19, 6] / [42,72] / [29, 40, 27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
• [19] / [6] / [42,72] / [29, 40, 27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
  • 19와 6을 병합하면서 오름차순으로 정렬한다.
• [6, 19] / [42, 72] / [29, 40, 27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
• [6, 19] / [42] / [72] / [29, 40, 27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
  • 42와 72를 병합하면서 오름차순으로 정렬한다.
• [6, 19] / [42, 72] / [29, 40, 27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
  • 6,19와 42,72를 병합하면서 오름차순으로 정렬한다.
• [6, 19, 42, 72] / [29, 40, 27, 60] / 8, 59, 63, 37, 85, 60, 33, 40

• [6, 19, 42, 72] / [29, 40] / [27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
• [6, 19, 42, 72] / [29] / [40] / [27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
  • 29와 40을 병합하면서 오름차순으로 정렬한다.
• [6, 19, 42, 72] / [29, 40] / [27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
• [6, 19, 42, 72] / [29, 40] / [27], [60] / 8, 59, 63, 37, 85, 60, 33, 40
  • 27와 60을 병합하면서 오름차순으로 정렬한다.
• [6, 19, 42, 72] / [29, 40] / [27, 60] / 8, 59, 63, 37, 85, 60, 33, 40
  • 29,40과 27,60을 병합하면서 오름차순으로 정렬한다.
• [6, 19, 42, 72] / [27, 29, 40, 60] / 8, 59, 63, 37, 85, 60, 33, 40
  • 6,19,42,72와 27,29,40,60을 병합하면서 오름차순으로 정렬한다.
• [6, 19, 27, 29, 40, 42, 60, 72] / [8, 59, 63, 37, 85, 60, 33, 40]
• 이런식으로 뒤 배열 그룹도 정렬한다.

• [6, 19, 27, 29, 40, 42, 60, 72] / [8, 33, 37, 40, 59, 60, 63, 85]
  • 앞 배열과 뒷 배열을 병합하면서 오름차순으로 정렬한다.
• [6, 8, 19, 27, 29, 33, 37, 40, 40, 42, 59, 60, 60, 63, 72, 85]

아래 동영상을 참고하면서 따라하면 도움이 된다.

병합 정렬의 시간복잡도

병합 정렬의 특징

장점

• 기본적인 정렬방법들에 비해 속도가 빠르다
• 정렬 정도에 구애받지 않는다.

단점

• 추가적인 저장 공간이 필요하다.

응용된 정렬 알고리즘(3) - 퀵 정렬(Quick Sort)

퀵 정렬의 과정

key보다 작으면 왼쪽, 크면 오른쪽에 배치하는 방법이다.

1. 0번째부터 key로 지정한다.
2. 좌측에서 우측으로 가면서 key보다 큰 값을 i라고 지정한다.
3. 우측에서 좌측으로 가면서 key보다 작은 값을 j라고 지정한다.
4. i의 위치보다 j의 위치가 더 우측에 있으면 i값과 j값을 교체한다.
5. 만약 i의 위치보다 j의 위치가 더 좌측에 있으면 j값과 key값을 교체한다.
6. 반복한다. (만약 나누어진 부분의 데이터가 2개 이상이면 재귀호출로 2~5를 반복한다.

초기 배열 상태

key의 값(23)을 기준으로 좌측 → 우측으로 가면서 key보다 큰 값을 i(37),

우측 → 좌측으로 가면서 key보다 작은 값을 j(20)라고 지정한다.

• i보다 j가 더 우측에 있으므로 i와 j의 값을 교체한다.

key의 값(23)을 기준으로 좌측 → 우측으로 가면서 key보다 큰 값을 i(30),

우측 → 좌측으로 가면서 key보다 작은 값을 j(11)라고 지정한다.

• i보다 j가 더 우측에 있으므로 i와 j의 값을 교체한다.

key의 값(23)을 기준으로 좌측 → 우측으로 가면서 key보다 큰 값을 i(30),

우측 → 좌측으로 가면서 key보다 작은 값을 j(11)라고 지정한다.

• i보다 j가 더 우측에 있지 않으므로 j와 key의 값을 교체한다.

• key의 값이였던 23은 정렬이 완료되었다.
• 23은 비교하지 않기 때문에 배열이 두 개로 나누어져 정렬된다 ( [11, 5, 20, 1] / [30, 52, 48, 37] )

key의 값(11)을 기준으로 좌측 → 우측으로 가면서 key보다 큰 값을 i(20),

우측 → 좌측으로 가면서 key보다 작은 값을 j(1)라고 지정한다.

• i보다 j가 더 우측에 있으므로 i와 j의 값을 교체한다

key의 값(11)을 기준으로 좌측 → 우측으로 가면서 key보다 큰 값을 i(20),

우측 → 좌측으로 가면서 key보다 작은 값을 j(1)라고 지정한다.

• i보다 j가 더 우측에 있지 않으므로 j와 key의 값을 교체한다.

• key의 값이였던 11은 정렬이 완료되었다.
• 11은 비교하지 않기 때문에 배열이 두 개로 나누어져 정렬된다 ( [1, 5] / [20] )

계속 반복하며 왼쪽 정렬을 마친다.

오른쪽도 반복하여 정렬한다.

만약 위 사진처럼 key보다 큰 값이 없을 경우에는 맨 끝을 i라고 한다.

아래 동영상을 참고하면서 따라하면 도움이 된다.

퀵 정렬의 시간복잡도

• Best

• Worst

퀵 정렬의 특징

• 장점
  • 가장 대표적인 정렬 방법이며, 랜덤 배열에서 가장 빠른 속도를 보인다.
  • 추가 메모리 공간이 필요없다.
• 단점
  • 정렬된 배열에서는 오히려 느리다

참고 문헌

셸 정렬

Algorithms and Data Structures explained and animated with fast and customizable applications. - algostructure.com

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

병합 정렬

합병 정렬(MergeSort)

ELE428 Data Structures and Algorithms

퀵 정렬

정렬 장단점