1. Quick Sort

1) Quick Sort Algorithm

(1) 0. Setting

<고정 값>

left, right : 가장 왼쪽, 오른쪽에 있는 값으로써 한 순환 내에서 값이 변하지 않음

<기준 값>

pivot : 기준값이다. 한 circulation의 목표는 pivot의 자리를 찾는 것이다. 지금은 가장 왼쪽에 있는 값을 기준으로 하자.

<변동 값>

low : pivot을 제외한 가장 왼쪽의 값
high : 가장 오른쪽의 값

(2) 1. 1st move

첫 번째 이동을 확인해보자.

low와 high를 중앙으로 이동시킨다. 언제까지 이동하냐면

low : pivot (= 기준)보다 높은 지점까지
high : pivot (= 기준)보다 낮은 지점까지

참고로 low와 high는 개별적으로 움직이는 것이기 때문에 사이좋게 한 칸씩 움직일 필요 없음

따라서 low는 5보다 큰 7이 나오는 시점까지, high는 4가 나오는 시점까지 이동한다.

(3) 2. switch

low, high가 도착한 값을 서로 바꾼다.

(4) 3. 2nd move

low, high를 아까와 같은 기준으로 다시 이동시킨다.

low : pivot (= 기준)보다 높은 지점까지
high : pivot (= 기준)보다 낮은 지점까지

(5) 4. last move

마지막으로 low, high를 위와 같은 기준으로 이동시키면, 서로의 위치가 바뀐 시점이 올 것이다.

이렇게 high, low가 멈춘 지점이 서로 위치가바뀐 경우 움직임을 멈춘다.

이후, high와 pivot의 위치를 바꾸어 pivot의 위치를 확정한다.

이렇게 한 번의 순환이 끝나면 pivot의 위치가 확정되는 것이다 (=그림에서의 5)

5의 위치가 결정되었으면, 5를 기준으로 partition을 나눴으니, 지금부터는 각 부분을 기준으로 pivot을 재설정해주면 된다.

2) Implement

위에서 설명한 퀵소트 알고리즘을 코드로 구현해보려고 한다.

(1) Setting

Swap

    void Swap(int arr[], int idx1, int idx2){
        int tmp = arr[idx1];
        arr[idx2]=arr[idx1];
        arr[idx1]=tmp;
    }

→ switching element in idx1, idx2

이 함수는, high, low가 이동을 마쳤을 때 && 멈추었을 때 값들을 Swap하기 위해 만든 것 같다

(2) partition func

Partition 1/2

int Partition(int arr[], int left, int right){
    int pivot = arr[left];
    int low = left+1;
    int high = right;
    ...
}

Partition(int arr[], int left, int right) : left, right로 나눠진 Partition안에서 → pivot을 결정.

→ 즉, 한 바퀴의 순환을 의미하는 함수임
- pivot → value of the arr
  - low, high → index
  즉, pivot은 값을 참조하여 넘어갈지를 정해야 하기 때문에 value를 할당했고, low, high는 포인터처럼 이동하는 데만 사용할 것이기 때문에 index만 얻어온 것이다.

Partition 2/2

//move untill the position is overturned
while(low<high){
    //low ->
    while(arr[low]>pivot)
        low++;

    //high <-
    while(arr[high]<pivot)
        high--;

    //Swap
    Swap(arr, low, high);
}

이렇게 적으면 마지막에 Swap할 때 문제가 된다. 우리는 이동을 멈춘 low와 high가 전복된 경우, swap을 멈춰야 한다. 전복된 상황은 while문의 조건에 반영하긴 했지만, Swap을 하는 것 까지 막진 못했다.

(move low high) → (swap)

→ (move low high) → (swap)

→ (move low high) 여기서 멈춰야 하는데 마지막 Swap을 막을 수 없다는 것이다.

해결책은

while문 밖에서 Swap을 한 번 더 해서 원래상태로 되돌이켜 주거나
처음부터 While문 안의 Swap을 조건부로 실행시키거나

두 가지 방법이 있다. 나는 두 번째 방법을 적용해보려고 한다.

//conditionally run
if(low<=high)
    Swap(arr, low, high);

return location of the pivot

return high;

(3) QuickSort

void QuickSort(int arr[], int left, int right){
    if(left<=right){//if left>right Sorting is ->already done
        int pivot=Partition(arr, right, left);
        QuickSort(arr, right, pivot-1);
        QuickSort(arr, pivot+1, left);
    }
}

pivot : pivot의 위치 확정
QuickSort *2회 → pivot설정 후 left, right를 할당하여 ‘재귀함수’형태로 만들기 위해 작성한 듯

결국 핵심 계산은 pivot = Partition이고, 이를 실행하기 위해 QuickSort를 재귀형태로 선언하는 것이다.

3) Problem && solve

지금까지 만든 quick sort함수로 실행을 시켜보자

int arr[3]={3,3,3}

QuickSort(arr,0, 2);

for(i=0;i<3;i++)
    printf("%d",arr[i]);

원래라면 3이 세 번 출력되었어야 하는데, 그렇게 출력되지 않는다.

이는 Partition함수에서 문제가 발생한 것이다. =

//low ->
    while(arr[low]>pivot)
        low++;

//high <-
    while(arr[high]<pivot)
        high--;

while내부의 조건문이 항상 거짓이기 때문에 low와 high가 움직이질 않는다.

즉, pivot과 중복되는 값이 있는 경우에 문제가 발생하는 것이다.

//low ->
    while(arr[low]>=pivot && low<=right)
        low++;

//high <-
    while(arr[high]<=pivot && high>=(left+1))
        high--;

arr[low]≥pivot : 등호를 추가하였다. 따라서 값이 동일한 경우에도 high와 low가 움직일 수 있도록 하였다.

그런데, 값이 동일하다고 계속 움직여버리면
low<=right, high>=(left+1)

이 값들은 low, high가 무한히 한 방향으로 넘어가는 상황 (= 주어진 값을 넘어가는 상황)을 방지하기 위함이다.

내가 처음에 의문을 가졌던 이유 : while문의 조건 안에 low≤right와 같이 등호를 포함하게 된다면, low=right시점 이후에, low값이 right보다 한 칸 더 앞으로 가는 거 아닌가?
마찬가지로, high가 비교 대상인 left+1보다 한 칸 왼쪽에 있을 수도 있는 거 아닌가?

이게 문제가 되는 이유는 → high, low값을 참조하여 Swap을 진행할 것인데, 참조 범위를 넘어가면 문제가 된다고 생각했기 때문이다. 즉 등호를 포함해도 되는가? 의 문제를 담고 있다.

이게 문제되지 않는 이유는 아래와 같다.

high가 왼쪽을 넘어가건, low가 오른쪽으로 넘어가건 아무튼 서로의 위치가 뒤틀린 상황임. 조건부로 실행되는 Swap은 일어나지 않음 (=high, low의 값 의미 x)

4) Quality Evaluation

Data의 개수를 n개라 하자(복습필요..)

1 번 Partition함수가 실행될 때 배열의 원소를 모두 검사해야 하므로 시간복잡도가 O(n)이다
Partition함수는 몇 번 실행되냐면 → log₂n번 실행됨

→ 배열의 크기가 1이될 때 까지 Patition을 나눠야 하므로, n / 2^k = 1 → k=log₂n

성능평가하는 거 조금 더 복습해야 할 것 같다. 특히나 1번은 잘 이해가 안간다. 한 번 파티션함수가 실행될 때 시간복잡도가 n이라는 것이.. → 그럼 두 번째 실행될 때는 시간복잡도가 n/2아닌가?

2. Radix Sort

기수정렬은, 지금까지 배웠던 Sort의 과정과 다르게 비교과정을 거치지 않는다. 앞에서 배웠던 퀵정렬, 병합정렬 등등에서 핵심 연산은 비교를 통해 원래 자리를 찾아가는 것이었다. 하지만 기수정렬은 비교과정 없이 정렬이 이뤄지기 때문에 과정이 굉장히 간단하다.

하지만, 이렇게 간단한만큼, 정렬할 수 있는 대상에 조건이 달린다.

지금부터는 기수정렬의 조건과, 정의, 코드구현에 대해 알아보자.

1) Condition of the array

기수정렬을 하기 위해서는 배열 요소의 길이가 동일해야 한다.

{1,2,12,13} 처럼 숫자의 길이가 다른 배열은 불가능하다.
{spring, summer, fall, winter}처럼 문자열의 길이가 다르면 불가능하다.

2) Definition of the radix

Radix, 기수는 데이터를 구성하는 기본 요소를 의미한다.

2진수는 0과 1로 구성되어있다. 이 경우 기수는 0과 1이므로 0과 1의 버켓 두 개를 만들어야 한다.

10진수라면 0~~9로 구성되어있다. 이 경우 기수는 0~~9이므로 0~9까지의 버켓 10개를 만들어야 한다.

여기서 궁금했던 것은, 예를 들어 123이라는 숫자가 있다면 → 100의 자리에 있는 0~~9, 10의자리에 있는 0~~9, 1의 자리에 있는 0~9까지 30개의 버켓이 필요한 거 아닌가? 라는 생각이 들었다. 단 10개만으로 정렬이 가능하다면 10개를 계속해서 재사용하는 것인가? 라는 생각이 들었다.

3) Comprehension of the Radix Sort

기수정렬의 종류는 관찰을 시작하는 지점에 따라 LSD와 MSD로 나눈다.

(1) LSD

Least Significant Digit 즉, 가장 덜 중요한 숫자부터 관찰하는 방식이다. 세 자리 자연수를 비교한다고 할 때 가장 안중요한 자리는 어디일까?

우리는 크기비교를 할 때 큰 자리수를 먼저 비교한다. 100의자리 → 10의자리 → 1의자리 순서로 비교하고, 만약 중간에 크기비교가 되면 (=값이 같지 않으면 ) 뒤의 자리는 비교하지 않는다.

따라서 내가 느끼기엔, 자릿수가 큰 자리가 우선순위가 높고, 1의 자리가 Least Significant 라고 할 수 있다.

Step 1. 1의자리를 기준으로 정렬한다.

위에서부터 버킷에 차례로 쌓은 후, 선입선출 방식으로 (=큐) 위에서부터 출력을 하여 정렬한다.

Step 2. 10의 자리를 기준으로 정렬한다.

10의 자리를 기준으로 정렬한다. 버킷에 순서대로 쌓은 후, 위에서부터 하나씩 빼는 것이다.

Step 3. 100의 자리를 기준으로 정렬한다

100의 자리 기준으로 정렬한다. 이렇게 되면 위에서부터 하나씩 뺐을 때 순서대로 정렬되는 것을 확인할 수 있다.

처음에는 일의 자리부터 검사를 하는 게 굉장히 의아했다. 마지막 자리를 중심으로 정렬을 했던게 신기했었다. 왜 가장 큰 숫자를 중심으로 비교하지 않는 것인가? 이는 MSD과정을 보면 답이 될 것 같다.

(2) MSD

우리가 일반적으로 하는 방식인, 윗글자부터 크기를 비교하는 MSD방식을 사용해보자

LSD와 비교의 시작점만 다르니까, 일부만 변경하면 될 것이라 생각했지만, 이렇게 되면 제대로 정렬이 안된다는 것을 확인했다

즉, 100의 자리로 값을 정렬한 후, 2번째 자리를 토대로 값을 정렬하면, 1번째에서 세워둔 정렬이 모두 흐트러진다.

이렇게 문제가 발생하니 든 생각은, 2번째 정렬은 각 그룹별로 진행해야 할 것 같다는 생각이다.

맨 앞의 숫자가 1인 것끼리, 2인 것끼리 정렬한다면 다음과 같은 문제는 발생하지 않을 것이다.

생각은 접어두고 문제가 무엇이었는지 확인해보자.

224, 232는 이미 두 번째에서 자리비교가 끝난 상황이다. 여기서 마지막 자리숫자까지 정렬을 시도했기 때문에 문제가 발생하는 것이다.

(3) Difference

그렇다면, 위의 LSD, MSD의 차이는 무엇일까?

LSD는 마지막까지 도달해야 정렬이 완성되는 방식이고,

MSD는 아래 자리부터 점진적으로 코드를 완성해나가는 방식이다.

따라서 MSD는 원래 흘러갈 수록 정렬 결과가 예측되는 형태이기 때문에 중간에 계속해서 점검을 해주어야 한다. (지금 비교를 해야 하는지, 굳이 안해도 이미 결정이 났는지)

일반적이라고 생각했던 MSD방식이 의외로 복잡할 수 있다.

LSD는 1번째 정렬을 바탕으로 2번째의 기준, 버켓 안에 ‘순서대로’넣는다. 순서대로 삽입을 했기 때문에 큐와 같이 들어간 순서대로 나와야 한다.

4) Implement

(1) Setting

variable, parameter

void RadixSort(int arr[], int num, int maxLen){
    Queue buckets[BUCKET_NUM];

    int bi;
    int pos;
    int di;
    int divfac = 1;
    int radix;
}

(int arr[], int num, int maxLen) : num에는 데이터의 개수가, maxLen에는 데이터 길이의 최댓값이 들어간다. 숫자의 경우, 데이터의 길이가 동일하지 않은 경우에도 기수정렬이 가능하다

⇒ 1, 10을 01, 10으로 처리하여 자리수를 맞추면 되기 때문이다.

variable
1. pos : 자리숫자를 옮길 때 사용할 for문 내의 변수
2. bi : bucket index로, 버켓을 순서대로 호출할 때 사용할 for문 내의 변수
3. di : data index같은데..? 아무튼 data값을 모두 한 번씩 확인할 때 사용할 for문 내의 변수
Resetting 10 buckets

for(bi=0; bi<BUCKET_NUM, bi++){
    QueueInit(&buckets[bi]);
}

(2) Sorting

repeat (~num of the buckets)

for(pos=0; pos<maxLen; pos++){

}

즉, 데이터의 길이만큼 반복문을 반복할 것임. 예를 들어 3자리 자연수인 경우 → 3번의 과정을 반복할 것이다.

digit check → input to the bucket

for(di=0; di<num; di++){
    radix=(arr[di]/divfac)%10;

    Enqueue(&buckets[radix], arr[di]);
}

for… di<num : num 즉, 데이터의 개수만큼 반복할 것임
radix : 관찰하려고 하는 자리의 숫자 ⇒ 이 값에 따라서 buckets[radix]로 버켓에 넣을 것임
divfac : 확인하고 싶은 자리숫자와 관련된 값. 즉, 100의 자리가 알고싶으면, divfac는 100, 10의 자리가 알고싶으면 divfac는 10이런 식으로 할당한다.

1의 자리부터 확인하고 싶으니, 처음 radix를 만들 때 1을 할당했으며, 다음 바퀴를 돌기 시작할 때 (=for문에서 pos값이 변경될 때) radix*=10을 해줘야 할 것이다.

Enqueue : radix에서 구한 값을 참조하여 bucket에 넣는다.

End of one cycle

 for(bi=0, di=0 ; bi<BUCKET_NUM; bi++){
     while(!QIsEmpty(&buckets[bi]))
         arr[di++]=Dequeue(&buckets[bi]);
 }

 divfac*=10;

for → bucket의 개수만큼 한 개씩 돌아갈 것
while → 한 bucket안에서 값이 끝날 때 까지 출력할 것.
divfac : 확인하려는 자리숫자 한 칸 늘리기

5) Quality Evaluation

맨 앞에서 소개했던 것과 같이 기수정렬의 핵심은 비교가 아니라, 삽입과 추출이다.

주요 반복문에 주석을 달면 다음과 같다

// 가장 긴 데이터의 길이만큼 반복
for(pos=0; pos<maxLen; pos++)

    //정렬 대상의 수만큼 data를 bucket에 삽입
    for(di=0; di<num; di++)

    //정렬 대상의 수만큼 data를 bucket에서 추출
    for(bi=0; bi<BUCKET_NUM; bi++)

따라서 삽입, 추출의 횟수를 계산하면 다음과 같다.

Let. l = max length of the data, n= number of the data

O(ln)

여기서 l이 상수이기 때문에 이 값을 O(n)으로 봐도 괜찮다.

저작자표시 비영리 변경금지 (새창열림)

'프로그래밍 > Data Structure' 카테고리의 다른 글

자료구조 복습 #1 Node 값, 포인터 할당의 차이 (0)	2025.03.21
3주차 수업 - 재귀함수 && 추가학습 (0)	2025.03.18
10. Sort #2 Complex Sort Algorithm1 (0)	2025.03.10
10. Sort #1 Basic sort Algorithm (0)	2025.03.10
3. Queue (0)	2025.02.21

공대생의 일상에 퐁당

10. Sort #3 Complex Sort Algorithm2

1. Quick Sort

1) Quick Sort Algorithm

(1) 0. Setting

(2) 1. 1st move

(3) 2. switch

(4) 3. 2nd move

(5) 4. last move

2) Implement

(1) Setting

(2) partition func

(3) QuickSort

3) Problem && solve

4) Quality Evaluation

2. Radix Sort

1) Condition of the array

2) Definition of the radix

3) Comprehension of the Radix Sort

(1) LSD

(2) MSD

(3) Difference

4) Implement

(1) Setting

(2) Sorting

5) Quality Evaluation

'프로그래밍 > Data Structure' 카테고리의 다른 글

티스토리툴바

10. Sort #3 Complex Sort Algorithm2

1. Quick Sort

1) Quick Sort Algorithm

(1) 0. Setting

(2) 1. 1st move

(3) 2. switch

(4) 3. 2nd move

(5) 4. last move

2) Implement

(1) Setting

(2) partition func

(3) QuickSort

3) Problem && solve

4) Quality Evaluation

2. Radix Sort

1) Condition of the array

2) Definition of the radix

3) Comprehension of the Radix Sort

(1) LSD

(2) MSD

(3) Difference

4) Implement

(1) Setting

(2) Sorting

5) Quality Evaluation

'프로그래밍 > Data Structure' 카테고리의 다른 글

관련글

티스토리툴바