서리 개인 개발 블로그

퀵정렬(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);
}

버블정렬(Bubble sort)

- 1순회마다 큰숫자가 제일 뒤로 밀려나는게 거품이 수중표면으로 올라가는것과 비슷해서 지어진 이름이다.

- 인접한 두 원소를 검사하여 정렬하는 방법이다.

- 시간복잡도가 O(n^2)이기 때문에 느리지만 코드가 단순하다.

원리 (오름차순 기준)

  ※ 모든 순회를 다 표현하기엔 이미지 양이 많아지므로 1순회만 기준으로 설명한다.

  1. 2중 반복문으로 원소들을 돌면서 바로 다음 원소와 대소관계를 비교한다.

  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", i, arr[i]);
    }
}

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

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

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

  ※ 이 글은 코드 위주이니 설명은 아래 링크 확인 !

  ※ C AVL 트리(AVL Tree) 설명

AVL 트리에 사용할 구조체

typedef struct Node
{
    int data;
    struct Node* Parent, * Left, * Right;
}Node;

  ※ 이전 이진탐색트리와는 다르게 코드의 간결함을 위해 부모 노드를 참조할 변수를 하나 더 만든다.

균형 인수(Balance Factor) 구하기

- 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브트리의 높이

int GetHeight(Node* node)
{
    if (node == NULL) return 0;
	
    int leftDepth = GetHeight(node->Left);
    int rightDepth = GetHeight(node->Right);
	
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

int CalculateBalanceFactor(Node* node)
{
    return GetHeight(node->Left) - GetHeight(node->Right);
}

  ※ 균형 인수는 CalculateBalanceFactor를 호출하면 된다.

  ※ GetHeight는 재귀함수로 구성해서 단말노드까지의 높이를 반환한다.

LL(Left Left), RR(Right Right)

Node* LL(Node* node)
{
    Node* childNode = node->Left;
    node->Left = childNode->Right;
    if (childNode->Right != NULL)	
        childNode->Right->Parent = node;
	
    childNode->Right = node;
    childNode->Parent = node->Parent;
    node->Parent = childNode;
	
    return childNode;
}

  ※ LL은 다음과 같은 순서로 진행된다.

    1. Child node(이하 CNode)의 오른쪽 자식 참조를 Parent node(이하 PNode)의 왼쪽 자식으로 넣어준다.

      ※ 이 때 CNode의 오른쪽 자식 노드가 NULL이 아니면 오른쪽 자식노드의 부모 참조를 PNode로 변경해준다.

    2. CNode의 오른쪽 자식으로 PNode를 넣어준다.

    3. CNode가 PNode의 위치와 바뀌므로 CNode의 부모 참조를 PNode의 부모로 변경해준다.

    4. PNode의 부모는 CNode가 되므로 PNode의 부모 참조를 CNode로 변경해준다.

  ※ RR은 LL의 순서를 반대로 해주면 된다.

LR(Left Right) RL(Right Left)

Node* LR(Node* node)
{
    node->Left = RR(node->Left);
    return LL(node);
}

  ※ LR은 다음과 같은 순서로 진행된다.

    1. Parent node(이하 PNode)의 왼쪽 자식 노드를 RR회전 해준다.

    2. PNode를 LL회전 해준다.

  ※ RL은 LR의 순서를 반대로 해주면 된다.

AVL 리밸런싱

- AVL의 균형을 맞추는 함수는 다음과 같이 작성하면 된다.

Node* AVLSet(Node* node)
{
    int depth = CalculateBalanceFactor(node);
    if (depth >= 2)
    {
        depth = CalculateBalanceFactor(node->Left);
        if (depth >= 1)
        {
            //LL : Left Left
            node = LL(node);
        }
        else
        {
            //LR : Left Right
            node = LR(node);
        }
    }
    else if (depth <= -2)
    {
        depth = CalculateBalanceFactor(node->Right);
        if (depth <= -1)
        {
            //RR : Right Right
            node = RR(node);
        }
        else
        {
            //RL : Right Left
            node = RL(node);
        }
    
    }
	
    return node;
}

  ※ 어떤 서브트리의 부모노드를 대상으로 균형 인수를 구한다. (절대값이 2차이가 나면 균형을 잡아준다.)

  ※ 이 때, CalcualteBalanceFactor함수에서 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺴고있으니 반환값이 양수면 왼쪽 서브트리, 음수면 오른쪽 서브트리의 높이가 높다는 것이다.

  ※ 균형 인수의 절대값이 2가 되면 높이가 높은 서브트리를 대상으로 균형 인수를 한번더 계산해서 서브트리가 LL상태(혹은 RR)인지 LR상태(혹은 RL)상태인지 알아본 뒤, 상태에 따라 알맞은 함수를 적용해서 리밸런싱을 진행한다.

자, 여기까지 이해를 했다면 일단 AVL 트리의 리밸런싱 코드는 끝이났다.

이걸 어떤 타이밍에 적용해줘야 할까? 답은 트리에 변경점이 발생하는 시점이다.

즉, 데이터를 추가(Insert) 할 때, 데이터를 삭제(Delete) 할 때 위의 함수를 넣어주면 된다. 이점을 잘 생각해서 다음 풀 소스코드를 이해해보자. (이번엔 양이 양인만큼 코드가 길다.)

#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node* Parent, * Left, * Right;
}Node;

int GetHeight(Node* node)
{
    if (node == NULL) return 0;
	
    int leftDepth = GetHeight(node->Left);
    int rightDepth = GetHeight(node->Right);
	
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

int CalculateBalanceFactor(Node* node)
{
    return GetHeight(node->Left) - GetHeight(node->Right);
}

Node* RR(Node* node)
{
    Node* childNode = node->Right;
    node->Right = childNode->Left;
    if (childNode->Left != NULL)
        childNode->Left->Parent = node;
	
    childNode->Left = node;
    childNode->Parent = node->Parent;
    node->Parent = childNode;
	
    return childNode;
}

Node* LL(Node* node)
{
    Node* childNode = node->Left;
    node->Left = childNode->Right;
    if (childNode->Right != NULL)
        childNode->Right->Parent = node;
	
    childNode->Right = node;
    childNode->Parent = node->Parent;
    node->Parent = childNode;
	
    return childNode;
}

Node* LR(Node* node)
{
    node->Left = RR(node->Left);
    return LL(node);
}

Node* RL(Node* node)
{
    node->Right = LL(node->Right);
    return RR(node);
}

Node* AVLSet(Node* node)
{
    int depth = CalculateBalanceFactor(node);
    if (depth >= 2)
    {
        depth = CalculateBalanceFactor(node->Left);
        if (depth >= 1)
        {
            //LL : Left Left
            node = LL(node);
        }
        else
        {
            //LR : Left Right
            node = LR(node);
        }
    }
    else if (depth <= -2)
    {
        depth = CalculateBalanceFactor(node->Right);
        if (depth <= -1)
        {
            //RR : Right Right
            node = RR(node);
        }
        else
        {
            //RL : Right Left
            node = RL(node);
        }
    
    }
	
    return node;
}

Node* Insert(Node* node, int data)
{
    if (node == NULL)
    {
        node = (Node*)malloc(sizeof(Node));
        node->Left = NULL;
        node->Right = NULL;
        node->Parent = NULL;
        node->data = data;
		
        return node;
    }
    else if (data < node->data)
    {
        node->Left = Insert(node->Left, data);
        node->Left->Parent = node;
        node = AVLSet(node);
    }
    else if (data > node->data)
    {
        node->Right = Insert(node->Right, data);
        node->Right->Parent = node;
        node = AVLSet(node);
    }
    else
    {
        //데이터가 중복되므로 추가하지 않는다.
    }
	
    return node;
}

Node* GetMinNode(Node* node, Node* parent)
{
    if (node->Left == NULL)
    {
        if (node->Parent != NULL)
        {
            if (parent != node->Parent)
            {
                node->Parent->Left = node->Right;
            }
            else
            {
                node->Parent->Right = node->Right;
            }
			
            if (node->Right != NULL)
            {
                node->Right->Parent = node->Parent;
            }
        }
		
        return node;
    }
    else
    {
        return GetMinNode(node->Left, parent);
    }
}

Node* Delete(Node* node, int data)
{
    if (node == NULL) return NULL;
	
    if (data < node->data)
    {
        node->Left = Delete(node->Left, data);
        node = AVLSet(node);
    }
    else if (data > node->data)
    {
        node->Right = Delete(node->Right, data);
        node = AVLSet(node);
    }
    else
    {
        if (node->Left == NULL && node->Right == NULL)
        {
            node = NULL;
        }
        else if (node->Left != NULL && node->Right == NULL)
        {
            node->Left->Parent = node->Parent;
            node = node->Left;
        }
        else if (node->Left == NULL && node->Right != NULL)
        {
            node->Right->Parent = node->Parent;
            node = node->Right;
        }
        else
        {
            Node* deleteNode = node;
            Node* minNode = GetMinNode(node->Right, deleteNode);
			
            minNode->Parent = node->Parent;
			
            minNode->Left = deleteNode->Left;
            if (deleteNode->Left != NULL)
            {
                deleteNode->Left->Parent = minNode;
            }
			
            minNode->Right = deleteNode->Right;
            if (deleteNode->Right != NULL)
            {
                deleteNode->Right->Parent = minNode;
            }
			
            node = minNode;
            free(deleteNode);
        }
    }
	
    return node;
}

void Inorder(Node* node)
{
    if (node == NULL) return;
	
    Inorder(node->Left);
    printf("%d ", node->data);
    Inorder(node->Right);
}

void main()
{
    Node* root = NULL;
    
    //INSERT
    root = Insert(root, 4);
    root = Insert(root, 10);
    root = Insert(root, 13);
    root = Insert(root, 20);
    root = Insert(root, 25);
    root = Insert(root, 32);
    root = Insert(root, 55);
    
    Inorder(root);
    //결과 : 4 10 13 20 25 32 55 (root data : 20)
    
    //DELETE
    root = Delete(root, 4);
    root = Delete(root, 10);
    root = Delete(root, 13);
    
    Inorder(root);
    //결과 : 20 25 32 55 (root data : 25)
}

  ※ main 함수의 Insert를 보면 앞에서 다뤘던 이진탐색트리 때와는 다르게 수를 오름차순으로 넣어줘도 똑같은 트리가 만들어진 결과를 볼 수 있다.

  ※ Delete에서는 일부터 왼쪽 서브트리의 데이터를 모두 삭제했다. 그 결과, 리밸런싱을 통해 Root 노드가 25의 키값을 가진 노드로 변경이되어 양쪽 서브트리의 균형이 맞춰진걸 확인할 수 있다.