알고리즘 자료구조 - 7

6장(이어서)

 

7)

셸 정렬(shell sort)

 - 단순삽입정렬의 장점은 살리고 단점은 보완한 알고리즘

    단순삽입정렬의 장점: 배열의 데이터가 정렬에 가까워질 수록 정렬속도가 매우 빨라짐

    단순삽입정렬의 단점: 데이터가 삽입되어야할 위치가 멀리 떨어져있으면 대입(이동)해야 하는 횟수가 많아진다

 - 도널드 셸이 고안

 - 배열의 요소를 그룹으로 나눠 각 그룹별 단순삽입정렬 수행, 이후 그룹을 다시 합쳐 단순삽입정렬 수랭

 

 - n-정렬 : n칸만큼 떨어진 요소들을 모아 n개의 그룹으로 나누어 정렬하는 방법

     ex) 4-정렬, 2-정렬, 1-정렬과 같이 2배씩 작아진다. 최종적으로 1-정렬까지 하면 정렬완료

    : 처음 n-정렬의 n은 n=배열요소수/2 로 정하면 된다

    : 3중 반복문으로 구성된다(전체 정렬을 위한 반복 - 시작요소를 증가시키기 위한 반복 - 1번의 정렬을 하기위한 반복)

  ** n은 증분(셸 정렬에서 데이터를 나누는 값).

 

 - 개선: 하지만 너무 적은 간격의 증분값은 비효율적이기 때문에 아래의 조건이 추가된다

   - 조건1 : 증분 n의 값은 1부터 3*n+1 배로 증가

   - 조건2 : 증분 n의 값은 (배열의 전체요소 수)/9 보다 작아야 한다

  ** 위키에서는 배열요소수/3+1로 증분을 구하는데, 배열요소수/2는 동일한 것으로 보인다

     (즉, 배열 요소수/2가 기본이며, 나머지는 알고리즘을 적용하는 방법에 따라 증분값을 구하는 방법이 달라지는 것으로 추측된다)

     - 위키 해당 페이지 : https://ko.wikipedia.org/wiki/%EC%85%B8_%EC%A0%95%EB%A0%AC

   -> 주어진 문제에서 위의 개선 조건을 적용하면 1-정렬만 수행하게 된다

 

 - 시간 복잡도는 O(n^1.25)이며, 단순삽입 정렬보다는 좋다

 

 

8)

퀵 정렬

 - 분할정복 알고리즘에 해당한다

 ** 분할정복 알고리즘

    : 문제(배열)를 조금씩 나누어 보다 작은 문제로 만들어 문제를 해결하는(정렬하는) 알고리즘

 

 

기본 방법

 - 피벗(pivot): 퀵정렬에서 그룹을 나누는 기준

 - 배열의 중간 요소의 값을 피벗으로 삼고, 시작과 끝에서 중앙방향으로 피벗을 불만족하는 요소를 찾는다.

   찾으면 해당 요소끼리 데이터를 교환한다

 - 피벗으로 삼은 요소에 도착 시 종료

 - 위의 2개의 그룹을 나누어(4개의 그룹으로) 반복(반복시 재귀 사용)

 - 그룹을 구성하는 요소 개수가 1개가 될 경우 종료

 

 

 

비재귀적인 퀵정렬

 - 좌, 우측 끝의 포인터(배열의 범위를 결정하는 좌/우측 커서)가 저장될 2개의 스택 생성 및 초기화(초기화 때 배열 처음과 끝은 포인터로 넣게된다)

 - 반복문은 스택에서 좌, 우측의 포인터 pop - 기존의 퀵정렬 - 그룹 분할 후 좌, 우측의 포인터 push 으로 구성된다

 - 반복문의 종료조건은 (둘중 아무거나 상관없음) 스택이 비었을 때

 

 - 스택의 용량

  1) 배열을 분할시, 요소의 개수가 많은 그룹을 먼저 정렬을 진행

  2) 배열을 분할시, 요소의 개수가 적은 그룹을 먼저 정렬을 진행

    : 1)과 2)중에 2)가 보다 적은 횟수로 분할정렬을 종료 할 수 있다. 즉, 보다 적은 스택의 용량으로 구성이 가능하다

    : 1)를 조건으로 스택구현시, 스택 데이터의 최대 개수를 log n(n: 배열의 요소개수) 보다 작게 구현 할 수 있다

   ** 즉 요소개수가 백만개라도 스택의 최대 용량은 요소 20개가 저장될정도면 중분하다

 

 

피벗 선택방법

 방법1

   - 빠른 정렬방법은 배열에 저장된 데이터의 중앙값에 가까운 값을 구하면 된다.

   - 하지만 해당 값을 구하기 위해 또 다른 연산을 수행해야되기 때문에 임의의 요소 3개를 선택 후 그 중 중간에 해당하는 요소를 피벗으로 선택한다

 

 방법2

   - 첫 요소, 끝 요소, 중간요소를 선택하여 정렬 수행

   - 가운데 요소와 끝-1번째 요소의 크기 비교 후 정렬(오름차순 정렬일 경우, 가운데 요소의 값>끝-1번째요소의 값이면 교환된다)

   - 재귀적 반복 수행(다음 범위는 첫요소+1번째 요소~끝-1번째 요소이며, 그 범위의 배열에서 처음,중간,끝요소를 선택하여 반복수행한다 )

   - 장점: 나누어야할 그룹의 크기가 한쪽으로 치우침 방지 + 정렬할 요소가 3개씩 감소하는 장점이 있다

 

 

시간복잡도

 - O(nlog n)이나, 최악의 시간복잡도는 O(n^2)이다

 

 

 

qsort 함수

 - 헤더: stdlib.h

 - 선언: void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void*, const void*))

 - 설명

     void *base : 정렬대상 배열

     size_t nmemb : 요소의 개수

     size_t size : 요소 1개의 크기

     int(*compar)(const void*, const void*) : 비교함수 1<2 일경우 음수, 같은경우 0, 1>2일경우 양수를 반환하도록 구성

 

** qsort 함수는 함수이름을 퀵정렬에서 따왔지만, 함수내부에서 항상 퀵정렬 알고리즘을 사용하는 것은 아니다

 

 

9)

병합 정렬(merge sort)

 - 분할정복 알고리즘에 해당한다

 

 - 배열을 나누어 각각 정렬한 다음 병합하는 작업을 반복하는 알고리즘이다

 - 기본반복

    : 배열을 2부분으로 나눈다.

    : 앞 부분을 병합정렬로 정렬한다(재귀적)

    : 뒷 부분을 병합정렬로 정렬한다(재귀적)

    : 정렬이 끝난 두 배열을 병합한다

 - 병합방법: 두 배열의 요소를 비교하여 조건을 만족하는 요소의 값을 새로운 배열에 순차적으로 저장한다

             조건을 만족하는 요소의 값을 가지고 있던 원래 배열(두 배열중 1개)는 포인터를 증가시킨다

             또한 새로운 배열의 포인터 증가

             (즉, 병합정렬시 3개의 배열이 필요하다)

 

 

시간복잡도

 - 병합시에는 O(n), 병합을 위해 데이터는 나누어 정렬하는 단계는 log n 만큼 소요

 - 따라서 병합정렬의 전체 시간복잡도는 O(nlog n)이다

 

 

10)

힙 정렬(heap sort)

 - 힙을 사용하여 정렬하는 알고리즘 + 선택정렬을 사용하는 알고리즘

 - 힙상태의 배열에서 루트를 계속 제거+힙상태의 배열화를 반복하고, 제거한 루트를 배열에 나열하여 데이터를 정렬하는 알고리즘

 

 ** 힙: '부모의 값이 자식의 값보다 항상 크다(혹은 항상 작다)' 조건을 만족하는 완전이진트리

        (형제끼리의 값은 정렬되어 있지 않다 == 같은 차수의 데이터들 간의 정렬이 되어 있지는 않다)

       - 즉, 힙에서의 특성은 '부모의 값 >= 자식의 값'이며, 힙정렬은 가장 큰값이 루트에 위치하는 특징을 이용하는 알고리즘이다

 

 

힙 요소와 배열요소의 대응

 - 힙의 요소를 배열에 저장하는 방법 : 루트부터 시작하여 자식 순으로 좌에서 우로 한 줄씩 저장

 - 위와 같이 저장시 다음과 같은 관계 성립

    : 현재 요소를 x[i]라 했을때

      - 부모: x[(i-1)/2]

      - 왼쪽에 위치하는 자식: x[2*i+1]

      - 오른쪽에 위치하는 자식:  x[2*i+2]

 

 

힙정렬 기본방법

 - 힙정렬을 이용하기 위한 조건: 주어진 트리(배열)가 힙 상태를 가진 트리일 것

    ** 즉, 힙정렬 이전 '배열의 데이터를 힙상태로 정렬'하는 과정이 1번이라도 필요하다

 - 루트를 없애고 남은 데이터(트리)에서 가장 큰(혹은 작은) 값을 루트로 이동시킨다 -> 즉 배열의 제일 마지막 요소를 루트로 이동

    ** 메모리를 줄일려면, 루트를 다른 배열이 아닌 해당 배열의 끝으로 이동하면된다. 즉, 배열의 제일 마지막 요소와 루트의 데이터를 교환

       정렬은 n개 배열에서 n-1 개 배열로 생각

 - 남은 배열을 다시 힙으로 정렬

    : 부모와 자식을 비교하며 조건을 불만족할 시 부모와 자식의 값을 교환한다(가장 상위가 루트이니 루트부터 시작)

 - 반복

 - 부모 값보다 자식의 값이 작거나, 제일 마지막 차수(잎)에 도달하면 종료

 

 

배열로 힙 구현하기

 - 배열에 데이터가 저장되어 있을 경우 해당 배열을 힙상태의 배열로 정렬

 - bottom-up 방식으로 정렬(즉 가장 하위, 가장 우측의 가지부터 정렬 -> 상위 가지 정렬 순으로 진행한다)

 

시간복잡도

 - O(nlog n)

 

 

 

11)

도수 정렬

 - 요소의 대소관계를 판단하지 않고 정렬하는 알고리즘

 

 

방법

 - 도수분포표 만들기

   ** 도수분포표 : 주어진 자료를 몇개의 구간(단계)로 나누어 해당 구간별 데이터의 양을 표기하여 자료의 분포상태를 나타낸 표

   1) 배열을 하나 생성하고 초기화

   2) 원본 데이터가 저장된 배열에서 각 구간에 해당하는 데이터 발견시 해당 요소의 데이터 값 +1

 

 - 누적 도수분포표 만들기

   ** 첫번째 구간부터 n 번째 구간까지의 데이터 합계를 나타내는(즉, 시작부터 현재 n번째 구간까지 누적된 데이터량) 표 작석

   1) x[0] = x[0]

   2) 1부터 시작해서 n번째 구간까지 x[i]=x[i-1]+x[i]로 대입

 

 - 목적 배열 만들기

   ** 원본 데이터가 저장된 배열과 누적도수분포표를 참조하여 목적 배열 생성

   1) 원본 데이터가 저장된 배열과 동일한 크기의 배열(목적 배열) 생성 및 초기화

   2) 원본 데이터가 저장된 배열의 요소값을 증가(혹은 감소)시키면서 해당 요소의 데이터 값을 누적 도수분포표와 비교하여 해당 구간과 일치하는 목적배열의 요소에 저장

   3) 반복

    ** 목적배열에 정렬을 위해 원본 데이터가 저장된 배열의 요소값은 감소시키는 방향으로 하는 것이 좋다(그럴경우 안정 정렬이 된다)

 

 - 배열 복사하기

   1) 목적 배열의 데이터를 원본 배열에 저장