[Algorithm] Sort algorithm 정렬 알고리즘

[Algorithm] Sort algorithm 정렬 알고리즘

정렬 알고리즘

Sort algorithm 은 “선택”, “삽입”, “버블”, “합병”, “퀵” 총 다섯가지 방법의 알고리즘이 있다.

본인이 알고리즘 배울 때 모두 학습한 내용이라고 생각했는데, 다시와서 생각해보니 하나도 생각나지 않는다. 정렬 알고리즘 문제가 때마침 나와 정리하는 겸 글로 남기려고 한다.

찾아보니 아래 나와있는 정렬 알고리즘 이외에  힙 정렬, 기수정렬, Count 정렬, Radix 정렬 등 많이 있는 것 같다.

 

선택정렬

선택정렬이란 첫 번째 부터 n까지, 순회하면서 어떤 값(Min or Max)이 들어갈 지 선택하여 정렬하는 것을 의미한다. 한 Cycle 돌 때마다 값의 자리가 확정된다.

백문이 불여일견, 아래와 같이 정렬된다.

selectSortAlgorithm
selectSortAlgorithm

15 Cycle를 돌 동안 전체의 경우의 수를 비교, 어떠한 경우에도 모든 값을 비교, Swap하므로 연산(시간 복잡도)는 O(n²)이다.

#include <stdio.h>
#include <time.h>
#include <malloc.h>
#include <stdlib.h>

/* 2020-12-03 선택정렬
 * 첫 번째 인덱스부터 
 * 가장 작은 값을 리스트에서 찾아 "선택" 후
 * 차례대로 정렬해가는 방식
 */
void selectSort(int *param, int paramSize)
{
    // 리스트가 비어있으면 종료
    if( param == NULL )
    {
        return;
    }
    // 정상 진행 - 선언
    int *list = param;
    int size = paramSize;//_msize(param);
    int i, j;
    int min;
    int index = -1;

    // 최솟값 먼저 찾아서 앞에 정렬함
    for( i=0 ; i<size ; i++ )
    {
        // Loop 돌기 전 min, index 세팅 후
        min = *(param + i);
        index = i;
        for( j=i ; j<size ; j++)
        {
            // Loop 돌면서 최솟값과 index찾음
            if( *(param + j) < min )
            {
                index = j;
                min = *(param + j);
            }
        }

        // 가장 작은 값을 가진 index 와 i번째 자리바꿈
        min = *(param + i);
        *(param + i) = *(param + index);
        *(param + index) = min;
    };

    return;
}

/* 2020-12-03 삽입정렬
 * 
 */

int main()
{
    int *list = NULL;
    int size = 0;
    int i;

    scanf("%d", &size);

    list = (int*)malloc(sizeof(int) * size);
    for( i=0 ; i<size ; i++ )
    {
        scanf("%d", (list + i));
    }

    selectSort(list, size);

    for( i=0 ; i<size ; i++ )
    {
        printf("%d\n", *(list+i));
    }

    return 0;
}

 

삽입정렬

삽입정렬이란 기준으로부터 다음 값이 어디에 위치될 지 판단 후 정렬하는 것을 의미한다.

insertionSortAlgorithm
insertionSortAlgorithm

삽입정렬의 경우, 선택정렬과 달리 이미 정렬이 되어있는 상태라면 비교하여 스왑할 필요가 없을 것이다.(처음부터 값이 있어야 할 자리를 판단, 선택정렬은 값의 Min or Max를 우선적으로 찾음)

반대로 정렬이 되어있다면(최악의 경우) 비교해가면서 스왑하므로 선택정렬과 같은 연산(시간의 복잡도)을 할 것이다.

#include <stdio.h>
#include <time.h>
#include <malloc.h>
#include <stdlib.h>

/* 2020-12-04 삽입정렬
 * 이전 인덱스의 값과 비교, 작으면 스왑
 * 스왑하다 그 자리가 맞으면 끝
 */
void insertSort(int *param, int paramSize)
{
    int *list = param;
    int size = paramSize;
    int i, j;
    int tmp;

    for( i=0 ; i<size ; i++ )
    {
        // 첫 번째 인덱스부터 시작
        for( j=i ; j>0 ; j-- )
        {
            // i번째 부터 시작하며, 왼쪽으로 비교
            // i번째가 j 보다 작으면 스왑
            if( *(param + j - 1) > *(param + j) )
            {
                tmp = *(param + j - 1);
                *(param + j - 1) = *(param + j);
                *(param + j) = tmp;
            }
        }
    }

    return;
}

int main()
{
    int *list = NULL;
    int size = 0;
    int i;

    scanf("%d", &size);

    list = (int*)malloc(sizeof(int) * size);
    for( i=0 ; i<size ; i++ )
    {
        scanf("%d", (list + i));
    }

    insertSort(list, size);

    for( i=0 ; i<size ; i++ )
    {
        printf("%d\n", *(list+i));
    }

    return 0;
}

 

버블정렬

버블정렬은 바로 옆 값과 비교하여 스왑하는 알고리즘이다. 선택정렬과 비슷하게 한 번의 Cycle가 돌 때 마다 자리가 확정되며, 맨 뒤의 값이 확정되어 정렬 된다.

bubbleSortAlgorithm
bubbleSortAlgorithm

버블정렬도 모든 Cycle에서 모든 경우의 수를 비교하기 때문에 연산(시간의 복잡도)은 O(n²)가 된다.

#include <stdio.h>
#include <time.h>
#include <malloc.h>
#include <stdlib.h>

/*
2020 - 12 - 05 버블정렬
*/
void bubbleSort(int *param, int paramSize)
{
    int *list = param;
    int size = paramSize;
    int i, j;
    int tmp;

    for( i=size-2 ; i>=0 ; i-- )
    {
        for( j=0 ; j<=i ; j++ )
        {
            if( *(list + j) > *(list + j + 1) )
            {
                int swapTmp;

                swapTmp = *(list + j);
                *(list + j) = *(list + j + 1);
                *(list + j + 1) = swapTmp;
            }
        }
    }

    return;
}

int main()
{

    int *list = NULL;
    int size = 0;
    int i;

    scanf("%d", &size);

    list = (int*)malloc(sizeof(int) * size);
    for( i=0 ; i<size ; i++ )
    {
        scanf("%d", (list + i));
    }

    bubbleSort(list, size);

    for( i=0 ; i<size ; i++ )
    {
        printf("%d\n", *(list+i));
    }
    return 0;
}

 

합병정렬

합병정렬은 “분할 & 정복”기법을 사용하는 정렬 알고리즘이다. 정렬 할 리스트를 계속 반으로 나누어 정렬 한 후 합치는 방법이다.

mergeSortAlgorithm
mergeSortAlgorithm

어떤 경우라도 시간의 복잡도는 O(log n)이 되며, 정렬 시 사이즈가 같은 배열을 하나 더 사용하므로 2N만큼 공간을 사용하게 된다.

아래 코드에서 정렬 시 필요한 배열을 필요한 만큼 동적으로 할당받아 구현해봤다.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

void merge(int *list, int leftIndex, int mid, int rightIndex)
{
    int left = leftIndex;
    int right = mid;
    int size = rightIndex-leftIndex+1;
    int *temp = (int*)malloc(sizeof(int)*size);
    int i=0;

    // Merge sort 핵심 : 정렬된 리스트를 재정렬
    while( left<mid && right<=rightIndex )
    {
        if( *(list+left) < *(list+right) )
        {
            *(temp+i++) = *(list+left++);
        }
        else
        {
            *(temp+i++) = *(list+right++);
        }
    }

    if(left>=mid) 
    {
        while(right<=rightIndex)
        {
            *(temp+i++) = *(list+right++);
        }
    }
    else
    {
        while(left<mid)
        {
            *(temp+i++) = *(list+left++);
        }
    }

    left = leftIndex;
    for(i=0 ; i<size ; i++)
    {
        *(list+left++) = *(temp+i);
    }
    free(temp);
    return;
}

void mergeSort(int *list, int leftIndex, int rightIndex)
{
    if(leftIndex<rightIndex)
    {
        int mid = (leftIndex + rightIndex)/2;
        // 분할
        mergeSort(list, leftIndex, mid);
        mergeSort(list, mid+1, rightIndex);
        // 정복
        merge(list, leftIndex, mid+1, rightIndex);
    }

    return;
}

int main()
{
    int size;
    int *list = NULL;
    int i;

    scanf("%d", &size);

    list = (int*)malloc(sizeof(int)*size);

    for( i=0 ; i<size ; i++ )
    {
        scanf("%d", list+i);
    }

    mergeSort(list, 0, size-1);


    for( i=0 ; i<size ; i++ )
    {
        printf("%d\n", *(list+i));
    }

    free(list);
    return 0;
}

 

퀵정렬

합병정렬과 비슷하지만(분할 & 정복 기법), 반을 나누는 것이 아닌, 임의의 기준을 세워 정렬한다는 것에서 차이가 있다.

quickSortAlgorithm
quickSortAlgorithm

시간의 복잡도는 합병정렬과 똑같은 O(log n)이며, 최악의 경우는 이미 정렬 된 경우 N번만큼 분할이 일어나므로 O(n²)이다.

이를 방지하기 위해 기준이 되는 Pivot값을 랜덤 인덱스의 값으로 정하거나 중간 값으로 정하여 사용한다.

 

참조 사이트

기본 정렬 알고리즘 요약 정리(선택, 삽입, 버블, 합병, 퀵) v1.1

 A computer science portal for geeks


%d 블로거가 이것을 좋아합니다: