[개념] Sort(정렬)

다양한 정렬 알고리즘의 개념과 구현 방법, 성능 특성을 비교 설명합니다. 교환, 버블, 삽입, 선택 정렬부터 기수, 버킷, 계수, 쉘 정렬, 그리고 합병, 퀵, 힙 정렬까지 각 알고리즘의 작동 원리, 시간복잡도, 공간복잡도, 안정성을 코드와 도식으로 상세히 다루고 있습니다.


다양한 정렬들이 있으며, 이들을 기본적으로 알아야 하기 때문에 공부한 것들을 정리해 보겠다.

우선 그전에 (비)오름차순, (비)내림차순, 분류기준(2가지), Stable, In-space(or not) 을 설명한다.

  • 차순
    • 모든 값이 다르면 - 오름차순, 내림차순
    • 같은 값이 있다면 - 비오름차순, 비내림차순
      • 비(Non)
      • 예로 비내림차순은 같은 숫자값이 있는것, 비(Non)라서 내림차순 반대인 오름차순
  • 분류기준
    • Comparison(비교) - 교환, 버블, 삽입, 선택
    • Distribution(분배) - radix(기수), bucket(버킷)
  • Stable : 같은 수 입력 순서를 지켜주는 것
    • Stable : 삽입, 버블, 병합
    • Non Stable : 교환, 선택, 퀵
  • In-space or not(제자리 정렬 or X)
    • In-space : QuickSort처럼 메인 메모리에 데이터를 담아둔 공간에서만 정렬을 진행하는 것들
    • Not In-space : Radix나 MergeSort(합병정렬)처럼 추가 메모리 공간을 사용하는 것들



Exchange, Bubble, Insertion, Selection Sort

코드를 바로 보고 해석해서 비교하는게 더 간단할 것이다.

image-20221228003613812

  • 순서 : 삽입(좌측상단), 버블(우측상단), 선택(좌측하단), 교환(우측하단)
    • 삽입정렬 : 앞에서부터 하나씩 삽입하면서 삽입된것들 비교해가며 자기 자리를 찾아가는 구조
      즉, 삽입했을때 바로앞과 비교하고 비교한거의 앞에것들도 다 비교해야한다는 것
    • 버블정렬 : 2개씩 비교하면서 작은걸 앞으로 옮기면서 한바퀴 지나면 제일 큰게 제일 뒤로 감
      이때, 제일 뒤로간 이 숫자를 제외하고 다시 반복하는 구조
    • 선택정렬: 교환정렬과 차이는 조건에 맞으면 따로 기억을 했다가 마지막에 swap을 하는 구조
      바퀴마다 맨 앞자리가 옳게 채워지므로 이 숫자를 제외하고 다음 바퀴를 반복하는 구조
    • 교환정렬 : 선택정렬과 차이는 매번 조건에 맞으면 swap을 하는 구조
      바퀴마다 맨 앞자리가 옳게 채워지므로 이 숫자를 제외하고 다음 바퀴를 반복하는 구조
  • 복잡도 : 전부 최악 N^2
    • 삽입정렬은 최선의 복잡도가 N이란 점 참고



Radix, Bucket, Counting, Shell Sort

image-20221228005521187

  • 맨 끝자리 기준으로 순서대로 통에 나눠 적고, 0번 통부터 다시 순서대로 배열 정리(끝자리 정렬)
    그다음은 10자리 기준으로 반복(십의자리 정렬), 그다음은 100자리 기준으로 반복(전체 정렬 끝)
    • 통에 갓다오는 횟수 = 자리수 * n번(n은 통 개수)


image-20221228005612383

  • 버킷들 각각이 알아서 정렬 후 이를 합하게 되는점이 기수(Radix)와의 차이점이다.


image-20221228005652439

  • 어떤 특정수 입장에서 나보다 작은게 몇개 있다라는걸 미리 구하는것
    • 따라서 주어진 입력이 얼만지 모르는 그런경우는 미리 카운트를 구해두질 못하니까 사용불가
    • 지금처럼 입력 배열이 저렇게 주어져야 구할수가 있음


image-20221228005744571

  • 비교간격(Gap)을 큰 것 -> 점차 작은 것으로 변환하여 서로 떨어진 수를 swap
    • Gap이 3과 1인 상태를 수행하는 모습을 그림에서 볼 수 있음



MergeSort(합병정렬)

합병(Merge), 합병정렬(Mergesort) 함수를 이용해 재귀형태로 구현


합병(Merge)

두개의 정렬된 배열을 하나의 정렬된 배열로 합병

  • 두 배열 차례로 비교해서 더 큰 숫자를 새 배열에 넣는 식이고, 나중에 배열 하나가 먼저 비면 남은 배열꺼를 다넣음

image-20221228013515160


합병정렬(MergeSort)

정렬되지 않은 배열을 인수로 받아서 합병(Merge)도 이용해서 정렬

  • 입력 배열을 절반으로 나눈 2개를 mergesort()로 왼쪽 반, 오른쪽 반 호출 후 merge()로 합병 방식

  • mergesort(h, U)나 mergesort(m, V) 재귀 반복해서 제일 마지막 단계까지 가면, 그곳에서 merge() 함수로 합쳐지기 시작

    • U, V는 절반으로 나눈 2개 배열
    • h, m은 U, V의 크기

image-20221228013806406

  • 참고로 오른쪽에 공간을 나타낸것을 보면, 추가로 2n만큼 메모리 공간이 더 필요한 것이 핵심
    • 이는 제자리 정렬은 아니라는 의미
    • 다만, 이를 개선이 가능하다 (2n -> n으로 개선가능)


공간복잡도 개선한 합병정렬

값을 복사하지않고 index만 가지고 해결

image-20221228014119597

  • 변형된 Mergesort 함수


image-20221228014154035

  • 변형된 Merge 함수
    • 여기선 줄그은 부분이 기존에서 변형된 코드 부분
  • 결론은 여기 코드만 봐도 추가로 사용하는 배열이 2개가 아닌 하나라는 점을 알 수 있다.
  • 따라서 2n -> n으로 추가메모리 공간을 줄이는 개선을 보여준다.
    • 다만, 제자리정렬은 여전히 아니라는 점
  • 복잡도 : nlgn



QuickSort(퀵정렬)

quicksort()와 partition() 함수를 이용해 재귀형태로 구현

“분할교환정렬(partition exchange sort)”라 한다. - 분할 알고리즘

기준값이 무엇이든 상관없지만 예로 첫 번째 값을 기준값으로 선정해서,
그보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 나누는게 핵심 아이디어


빠른정렬(QuickSort)

  • partition()를 통해 pivotpoint(=기준값)의 왼쪽, 오른쪽으로 나누고,

  • pivotpoint의 index를 반환 받아서 mid처럼 사용해서 quicksort() 함수를 다시 재귀

image-20221228015204421


분할(Partition)

  • partition으로 나눌 때 흐름?
    • 15 22 13 27 12 10 20 25 -> 15 13 12 10 22 27 20 25 -> 10 13 12 15 22 27 20 25
      • 처음에선 15가 pivotpoint로 시작한것이고,
        pivotpoint는 index니까 pivotitem에 해당 index의 값을 저장해서 활용한다.
      • 두번째에선 아래 코드에서 for문을 다 수행한 순간의 모습이다.
      • 세번째에선 아래 코드를 마지막까지 수행한 모습이며,
        이때 pivotpoint가 중간인 mid위치의 index를 가지게 된다.
        => 이덕분에 quicksort함수에서 mid처럼 사용하는 것이다.

image-20221228015350865


  • 복잡도 : 최악의 복잡도는 n^2인데, 평균은 nlgn이다.
    • 합병정렬이 최악이 nlgn이라서 좋긴 하지만, 메모리 측면에서는 제자리정렬인 퀵이 우수
    • 또한, 퀵은 최악 복잡도를 피하는 방법들이 존재


최악 복잡도를 피할 수 있는 방법

최악을 피할 수 있는 방법은 무엇이 있을까?

  • 기준값 선택 – 맨앞, 중간, 맨뒤를 구해 3개 중 중간 값 사용방법
  • 미리 shuffle – 미리 n정도 복잡도를 사용해 섞어두면, 평균정도의 복잡도는 얻게 됨



HeapSort(힙정렬)

힙 개념

힙의 조건은 Complete Binary Tree, Key(v)>=Key(child(v))

  • Complete Binary Tree : 레벨 순서로 채워나가고, 왼쪽부터 오른쪽으로 채워나감
  • Key(v)>=Key(child(v)) : 자식보다 키값 같거나 크다는 성질
    • 참고로 이것은 Max Heap을 의미


힙 만드는 법

힙 만드는 2가지 방법 : Insertion, Adjust

  • Insertion : 자식이 부모보다 크다면 자리 교환하면서 자기 자리 끝까지 찾아감(2k, 2k+1)
    • 자식이 삽입되어 자기 자리 정해가는 거니까 자식이 주체인것
  • Adjust : 부모가 왼쪽, 오른쪽 자식 중 큰 값과 자리 교환하면서 자기 자리 찾아가기
    • 자식 있는 부모 노드들만 실행하는것임, 부모가 주체인것

참고로 k를 배열 인덱스로 보는게 핵심. 인덱스를 1부터!
또한, 배열로 봤을때 완전이진트리 자식을 찾아 가는 방식이 2k, 2k+1이라는 것


Insertion힙 만드는 과정만 소개하겠다.

image-20221228021606450

  • 참고로 원본 배열 값 : [10, 7, 3, 1, 6, 12, 13, 15, 19]


힙정렬

Heapsort(힙정렬) : 루트와 최하위 값을 바꿔서 최하위를 제외하고 다시 Heap(Adjust) 생성을 반복

  • 따라서 힙을 만드는 방법을 아는것이 중요

  • 복잡도 : Insertion, Adjust, Heapsort - nlgn


복잡도 상세 설명

해당 복잡도가 나온 이유를 좀 상세히 설명해보겠다.

  • Heapsort는 n-1번 힙을 새로 만듬. 힙만드는 Adjust가 1번 동작하는 자체는 lgn걸리므로 힙정렬의 복잡도는 nlgn이라 할 수 있다.
    • 당연히 초기에 힙도 아니었을땐 힙 만드는건 Adjust로 nlgn인데, 그 후 맨끝과 루트 값만 서로바꾸고 한번 Adjust로 힙동작하는(lgn)거기 때문에 nlgn이라 볼수있고, 총 nlgn+nlgn=nlgn으로 복잡도를 정의.
  • Adjust가 nlgn이라 한것은, 그건 처음에 힙을 구성할때 쭉 뒤에부터접근해서 계속 힙만드는(lgn)을 반복해서 nlgn 이라는 것.



합병, 힙 vs 퀵 정렬 비교

퀵 정렬을 많이 사용하는 이유가 궁금해서 구글링을 해보았다.


퀵 vs 힙

퀵 정렬에서 최악의 경우가 O(n^2) 이고 힙은 최악이든 최선이든 O(NlogN)인데 퀵 정렬이 성능이 보통 더 좋다고 한다.

이유가 무엇일까?

  • swap의 횟수 때문이라고 한다.


퀵 vs 합병

합병도 O(NlogN)이고 퀵은 최악이 O(n^2) 인데, 왜 또 퀵 정렬 성능이 보통 더 좋다고 하는것일까?

  • 합병은 배열을 생성하는 시간이 있기 때문이라고 한다.
  • 따라서 배열의 길이가 길수록 차이가 난다고 한다.

댓글남기기

참고