서리 개인 개발 블로그

이전에 C로 퀵정렬을 구현한 글을 썼었는데, 육안으로 과정이 보이는 글이 아닌 코드만 작성되어있는 글이어서 유니티 C#으로 퀵 정렬 과정을 육안으로 확인할 수 있도록 제작해봤다.

만들면서 파티션 정렬하는 과정에서 high index가 파티션 배열의 범위를 벗어나는 버그가 있었는데, 단순히 조건문 순서상의 오류라 바로 수정했다. (생각보다 그 글이 조회수가 좀 됐는데, 글을 보신 분들이 문제 제기를 안했다는게 의아함)

1. 유니티 C# 퀵정렬 프로젝트

- 코드가 아닌 유니티 프로젝트로 올립니다. (깃허브)

2. QuickSort 컴포넌트 설명

- TargetArrSize : 배열의 길이를 지정할 수 있다.

- Min, Max : 배열 요소의 최소값과 최대값. (지정한 범위 안에서 랜덤 함수로 지정된다.)

- Delay : 정렬하는 속도 (값이 높을수록 느려집니다. WaitForSeconds값.)

※ Scene에 버튼 2개가 붙어있는데, Create arr 버튼으로 배열을 생성하고, Quick sort 버튼을 누르면 정렬이 시작되며 정렬 과정을 눈으로 확인할 수 있습니다.

※ low index - Red, high index - Blue, pivot index - cyan

※ 정렬이 완료되면 UI element가 초록색으로 변합니다.

3. 퀵정렬 설명

문자열 뒤집기

- 문자열의 n번째 순서와 마지막에서 n번째 순서의 위치를 변경해준다. (n의 값은 동일)

- 단순하게 생각하면 문자열의 길이만큼의 loop를 돌면서 위치를 변경해줘도 되지만, 위와 같은 swap 방식을 사용하면 문자열 길이의 반만 돌아도 뒤집기가 가능하기 때문에 훨씬 효율적이다.

#include <iostream>
using namespace std;

void Swap(char* c1, char* c2)
{
    char tmp = *c2;
    *c2 = *c1;
    *c1 = tmp;
}

void main()
{
    string str = "string";
    for(int i = 0; i < str.length() / 2; i++)
    {
    	Swap(&str[i], &str[str.length() - i - 1]);
    }
    cout << str << endl;
    
    //결과 : gnirts
}

숫자 뒤집기

- 숫자를 뒤집는 방법은 단순하게 2가지로 분류해볼 수 있다.

• 숫자를 문자열로 변경해 문자열을 뒤집은 후 문자열을 숫자로 변환.
• 수식을 사용해 뒤집기.

- 수식을 사용해서 숫자를 뒤집는 방법은 다음과 같다.

  1. 뒤집을 숫자를 10으로 나눠 나머지를 구한다.

  2. 나머지를 임시 변수에 더한다.

  3. 뒤집을 숫자를 10으로 나눠준다.

  4. 10으로 나눠진 뒤집을 숫자가 0이면 반복문을 빠져나간다.

  5. 10으로 나눠진뒤집을 숫자가 0이 아니면 임시 변수에 10을 곱해준다.

- 위의 과정에서 반복문을 빠져나오면 임시변수의 값이 뒤집을 숫자가 뒤집어진 값이 완성된다.

#include <iostream>
using namespace std;

void main()
{
    int n = 100;
    int reverse = 0;
    while(true)
    {
    	reverse += n % 10;
        n /= 10;
        if(n == 0)
        {
            break;
        }
        reverse *= 10;
    }
    cout << reverse << endl;
    
    //결과 : 1
}

퀵정렬(Quick Sort)

- 찰스 앤터니 리처드 호어가 개발한 알고리즘이다.

- 평균 O(n log n)으로 매우 빠른 정렬속도를 자랑한다.

- 기준(Pivot) 값을 기준으로 나머지 원소에 대해 대소관계를 비교하여 큰 것과 작은 것으로 이분한 다음 다시 해당 작업을 반복한다.

  ※ 이와 같이 문제를 작은 문제로 분할하여 해결하는 방법을 분할 정복(Devide and Conquer)이라 한다.

원리(오름차순 기준)

  1. Pivot의 값은 배열의 제일 오른쪽 원소로 정한다.

    ※ Pivot의 위치는 정해져있지 않다. (왼쪽도 되고 중앙도 된다.)

  2. Low는 오른쪽으로, High는 왼쪽으로 돌면서 각 원소를 Pivot 원소와 대소관계를 파악한다.

    2-1. Low는 Pivot보다 작아야한다. 즉, Pivot의 값보다 크면 순회를 멈춘다.

    2-2. High는 Pivot보다 커야한다. 즉, Pivot의 값보다 작으면 순회를 멈춘다.

    2-3. Low와 High의 값을 SWAP한다.

  3. Low와 High가 교차할때까지 2번의 작업을 반복한다.

  4. Low와 High가 교차를 하게되면 Low와 Pivot의 값을 SWAP한다.

  5. Pivot의 값을 기준으로 왼쪽 원소들은 Pivot보다 작은 값들, 오른쪽 원소들은 큰 값들만 있으므로, 왼쪽과 오른쪽의 원소들을 분할하여 1 ~ 4번의 과정을 반복한다.

    ※ Left와 Right가 더이상 쪼개지지 않을때까지 반복한다. (재귀함수를 이용)

    ※ Pivot을 기준으로 두개의 배열로 나누는걸 파티션(Partition)이라고 한다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 10
#define ASCENDING 1
#define DESCENDING 2

void SetArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        arr[i] = rand() % 100;
    }
}

void PrintArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        printf("%d\n", arr[i]);
    }
}

void Swap(int* n1, int* n2)
{
    int tmp = *n2;
    *n2 = *n1;
    *n1 = tmp;
}

int Sorting(int arr[], int left, int right, int sortType)
{
    int pivot = right;
    int low = left, high = pivot - 1;
	
    while (low <= high)
    {
        switch (sortType)
        {
        case ASCENDING:
            //find low index
            for (; low <= high && arr[low] <= arr[pivot]; low++);
            //find high index
            for (; high >= low && arr[high] >= arr[pivot]; high--);
            break;
        case DESCENDING:
            //find low index
            for (; low <= high && arr[low] >= arr[pivot]; low++);
            //find high index
            for (; high >= low && arr[high] <= arr[pivot]; high--);
            break;
        }
		
        if (low <= high)
        {
            Swap(&arr[low], &arr[high]);
        }
    }
	
    Swap(&arr[low], &arr[pivot]);
    return low;
}

void QuickSort(int arr[], int left, int right, int sortType)
{
    if (left >= right) return;
	
    int pivot = Sorting(arr, left, right, sortType);
	
    //Left partition
    QuickSort(arr, left, pivot - 1, sortType);
    //Right partition
    QuickSort(arr, pivot + 1, right, sortType);
}

void main()
{
    srand(time(NULL));
    int iArr[MAX] = { 0 };
	
    SetArr(iArr);
	
    QuickSort(iArr, 0, MAX - 1, ASCENDING);
    //PrintArr(iArr);
	
    QuickSort(iArr, 0, MAX - 1, DESCENDING);
    //PrintArr(iArr);
}

삽입정렬(Insertion Sort)

- 제자리 정렬 알고리즘의 하나이다.

- 카드를 순서대로 정리할때와 같은 방법이다.

- 선택정렬과 유사하지만 좀 더 효율적인 정렬이다. (시간복잡도는 O(n^2)로 동일하다.)

원리(오름차순 기준)

  1. 첫 번째 원소는 앞의 원소가 더 이상 존재하지 않으므로, 두 번째 원소를 기준 원소로 잡고 시작한다.

  2. 기준으로 잡은 원소의 앞(왼쪽)을 차례로 비교하면서 위치를 바꿔준다.

    ※ 즉, 두 번째 원소는 첫 번째 원소와 비교, 세 번째 원소는 두 번째, 첫 번째 원소와 비교하는 식이다.

코드

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 10

void SetArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        arr[i] = rand() % 100;
    }
}

void PrintArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        printf("%d\n", arr[i]);
    }
}

void InsertionSortAscending(int arr[])
{
    for (int i = 1; i < MAX; i++)
    {
        int j = i - 1;
        int current = arr[i];
		
        while (j >= 0 && arr[j] > current)
        {
            arr[j + 1] = arr[j];
            j--;
        }
		
        arr[j + 1] = current;
    }
}

void InsertionSortDescending(int arr[])
{
    for (int i = 1; i < MAX; i++)
    {
        int j = i - 1;
        int current = arr[i];
		
        while (j >= 0 && arr[j] < current)
        {
            arr[j + 1] = arr[j];
            j--;
        }
		
        arr[j + 1] = current;
    }
}

void main()
{
    srand(time(NULL));
    int iArr[MAX] = { 0 };
	
    SetArr(iArr);
	
    InsertionSortAscending(iArr);
    //PrintArr(iArr);
	
    InsertionSortDescending(iArr);
    //PrintArr(iArr);
}

선택정렬(Selection sort)

- 제자리 정렬 알고리즘의 하나이다.

- 각 순회마다 제일 앞의 기준 원소를 잡고 다음 원소부터 차례차례로 검사하여 정렬하는 방법이다.

- 시간복잡도가 O(n^2)이지만, 메모리가 제한적인 경우 사용시 성능 상의 이점이 있다.

  ※ 같은 시간복잡도를 가지고 있는 버블정렬보다 선택정렬이 우수하다. (교환 횟수가 작기때문)

원리 (오름차순 기준)

  1. 각 순회마다 제일 앞의 원소를 기준 원소로 잡는다.

  2. 기준 원소의 다음 원소부터 배열 끝까지 돌면서 최소값을 탐색한다. (이 때, 최소값은 기준 원소값보다 작아야한다.)

  3. 최소값이 존재하면 원소의 위치를 바꿔준다.

    ※ 마지막 순회는 정렬할 필요가 없으므로 순회를 돌 필요가 없다.

코드

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 10

void SetArr(int arr[])
{
    for(int i = 0; i < MAX; i++)
    {
        arr[i] = rand() % 100;
    }
}

void PrintArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        printf("%d\n", arr[i]);
    
    }
}

void SelectionSortAscending(int arr[])
{
    for (int i = 0; i < MAX - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < MAX; j++)
        {
            if (arr[min] > arr[j])
            {
                min = j;
            }
        }

        if (i != min)
        {
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
    }
}

void SelectionSortDescending(int arr[])
{
    for (int i = 0; i < MAX - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < MAX; j++)
        {
            if (arr[min] < arr[j])
            {
                min = j;
            }
        }

        if (i != min)
        {
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
    }
}

void main()
{
    srand(time(NULL));
    int iArr[MAX] = {0};
    
    SetArr(iArr);
    
    SelectionSortAscending(iArr);
    //PrintArr(iArr);
    
    SelectionSortDescending(iArr);
    //PrintArr(iArr);
}