[자료구조] 12 정렬 알고리즘

1. 정렬이란?

물건을 내림차순이나 오름차순으로 나열하는 것. 자료 탐색에서 필수적이다. 최상의 성능을 보여주는 최적 알고리즘은 존재하지 않기 때문에 현재 프로그램의 수행환경에서 가장 효율적인 정렬 알고리즘을 선택해야 한다. (비교 연산의 횟수, 이동 연산의 횟수)

💡단순하지만 비효율적인 방법 - 삽입, 선택, 버블 등
💡복잡하지만 효율적인 방법 - 퀵, 히프, 합병, 기수 등

내부정렬: 정렬 전, 모든 데이터가 메인 메모리에 올라와 있는 정렬
외부정렬: 외부 기억 장치에 대부분의 데이터가 있고, 일부만 메모리에 올려놓은 상태에서 정렬

안정성: 입력 데이터에 동일한 키 값을 갖는 레코드가 여러개 존재할 경우, 레코드의 상대적 위치가 정렬 후에도 바뀌지 않는 것.

안정성이 필수적으료 요구되는 경우 = 삽입, 버블, 합병 정렬 등을 사용해야 한다.

2. 선택 정렬

입력 배열에서 최소값을 발견한 다음, 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택해 두번째 요소와 교환한다. 이 절차를 숫자개수-1만큼 되풀이한다.

i값이 0에서 n-2까지만 변화한다는 점을 기억해라. 0번부터 n-2까지 정렬이 되었으면 n-1이 가장 큰 값이기 때문에 n-1까지 정렬할 필요가 없다.

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

void selectionSort(int A[])
{
    printf("Before Sort: ");
	for (int i = 0; i < N; i++)
		printf("[%d] ", A[i]);

	printf("\n\n <<<<<<<<<<<<<<<<<<<selection Sorting...>>>>>>>>>>>>>>>>>>\n\n");

    for(int i=0;i<=N-2;i++)
    {
        int min = i;
        for(int j=i+1;j<=N-1;j++)
            if(A[min]>A[j])
                min = j;
        
        int temp = A[min];
        A[min] = A[i];
        A[i] = temp;

        printf("%d Step: ", i);
        for(int i=0;i<N;i++)
            printf("[%d] ", A[i]);
        
        printf("\n");
    }
}
int main()
{
    int A[N];
    srand(time(NULL));

    for(int i=0 ; i<N; i++) 
        A[i] = rand()%100;
    
    selectionSort(A);
}

📕 분석
비교 횟수 -> 두개의 for문, 외부루프 n-1번 실행되고 내부 루프는 0에서 n-2까지 변하는 i에 대하여 n-1-i번 반복될 것이다. 키 값들의 비교가 내부 루프안에서 이루어 지므로 전체 비교횟수는 다음과 같다.

n-1번 비교 + n-2번 + ... +1 = n(n-1)/2 = O(n^2)

레코드 교환 횟수(swap)은 3번의 이동이 필요하므로 전체 이동 횟수는 3(n-1)이 된다.

장점: 자료 이동회수가 미리 결정된다.
단점: 이동 회수가 크다. 자료가 정렬된 경우에는 불필요한 이동이 이루어질 수동 있다.

3. 삽입 정렬

손안의 카드를 정렬하는 방법. 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용한다.

void insertionSort(int A[])
{
    printf("Before Sort: ");
	for (int i = 0; i < N; i++)
		printf("[%d] ", A[i]);

	printf("\n\n <<<<<<<<<<<<<<<<<<<insertion Sorting...>>>>>>>>>>>>>>>>>>\n\n");

	//첫번째 값은 정렬이 되어있는 값, 두번째 값부터 정렬이 시작되면 된다.

    for(int i=1;i<N;i++)
    {
        int key = A[i];
        int j = i-1;

        while(j >= 0 && A[j] > key)
        {
            A[j+1] = A[j];
            j--;
        }

        A[j+1] = key;
        printf(" %d Step: ", i );
        for (int i = 0; i < N; i++)
			printf("[%d] ", A[i]);
		printf("\n");
    }
}

📕 분석

입력 자료의 구성에 따라서 정렬의 복잡도가 달라진다. 외부 루프는 n-1번 실행되고, 각 단계에서 1번의 비교와 2번의 이동만 이루어 지므로 총 비교횟수는 n-1번, 총 이동횟수는 2(n-1)번이 되어 알고리즘의 시간 복잡도는 O(n)이다.

최악의 복잡도는 입력 자료가 역순인 경우다. 전부 한 칸씩 뒤로 이동해야 하기 때문에 외부 루프 안의 각 반복마다 i번의 비교가 수행된다.

장점: 안전한 정렬 방법, 레코드의 수가 적을 경우 매우 간단하다. 대부분의 레코드가 이미 정렬되어 있는 경우 효율적이다.

단점: 레코드 양이 많고 크기가 클 경우 적합하지 않다.

4. 버블 정렬

인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.

하나의 스캔은 j=0부터 j=i-1까지 반복하는 루프, j번째 요소와 j+1번째 요소를 비교하여 크기순으로 되어 있지 않으면 교환한다.

void bubbleSort(int A[])
{
    printf("Before Sort: ");
    for (int i = 0; i < N; i++)
        printf("[%d] ", A[i]);

    printf("\n\n <<<<<<<<<<<<<<<<<<<selection Sorting...>>>>>>>>>>>>>>>>>>\n\n");

    for (int i = N - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
            if (A[j] > A[j + 1])
            {
                int temp = A[j + 1];
                A[j + 1] = A[j];
                A[j] = temp;
            }

        printf("%d Step: ", i);
        for (int i = 0; i < N; i++)
            printf("[%d] ", A[i]);

        printf("\n");
    }
}