[+] 정렬

정렬

정렬이란 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 서로 줄지어 늘어서도록 바꾸는 작업을 말한다.

정렬 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할 수 있다.

정렬 알고리즘의 안정성

정렬 알고리즘은 안정 정렬과 비안정 정렬로 이루어져 있다.

이때 안정 정렬이란 같은 값의 키를 가진 요소의 순서가 정렬 전 후에도 유지되는 것을 말하며, 비안정 정렬은 반드시 순서대로 정렬되지 않는다.

내부 정렬과 외부 정렬

장렬 알고리즘은 하나의 배열에 작업할 수 있는 경우에는 내부 정렬을 사용하고, 하나의 배열에서 작업할 수 없는 경우에는 외부 정렬을 사용한다. 이때 내부 정렬과 외부 정렬의 설명은 아래와 같다.

 

1. 내부 정렬: 정렬할모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘 2.외부 정렬: 정렬할 데이터가 너무 많아 하나의 배열에서 작업할 수 없는 경우에 사용하는 알고리즘

[1] 버블 정렬

버블 정렬(bubble sort) 알고리즘

버블 정렬이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 이는 선택 정렬과 기본 개념이 유사하다.

버블 정렬(bubble sort) 알고리즘의 구체적인 개념

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1) 번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

아래 링크 참조

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

버블 정렬(bubble sort) 알고리즘의 특징

장점	구현이 매우 간단하다.
단점	순서에 맞지 않은 요소를 인접한 요소와 교환한다. 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다. 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다. 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

버블 정렬(bubble sort)의 시간복잡도

시간복잡도를 계산한다면,

 

비교 횟수

• 최상, 평균, 최악 모두 일정
• n-1, n-2, … , 2, 1번 = n(n-1)/2

교환 횟수

• 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
• 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
• T(n) = O(n^2)

버블 정렬 프로그램

버블 정렬의 기본 알고리즘은 코드는 아래의 [더 보기] 란을 확인한다.

#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
    scanf("%d", &n);
    for (i=1; i<=n; i++)
        scanf("%d", &a[i]);
    for(i=1; i<n; i++){
        for(j=1; j<=n-i; j++){
            if (a[j] > a[j+1]){
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
    for (i = 1; i <= n; i++)
        printf("%d\n", a[i]);
    return 0;
}

알고리즘 개선 (1)

버블 정렬 과정에서 반복을 하다 보면 요소의 교환이 한 번도 이루어지지 않는 경우가 발생한다. 이는 특정 패스에서 정렬을 마쳤기 때문이다. 이미 배열이 정렬을 마친 상태 하면 그 이후의 패스는 요소 교환을 하지 않아도 된다.

 

다시 말해, 어떤 패스에서 요소의 교환 횟수가 0이 되면 더 이상 정렬할 요소가 없다는 뜻이므로 정렬을 멈춰도 된다. 이런 정렬의 멈춤 조건을 추가한다면 정렬이 거의 다 된 상태의 대한 비교 연산이 생략되어 짧은 시간 내에 정렬이 가능하다.

 

알고리즘을 수정하면 아래와 같다. 추가한 부분을 형광펜 표시를 했다.

void bubble(int a[], int n){     int temp;     for(int i=1; i<n; i++){         int exchg = 0;         for(int j=1; j<=n-i; j++){             if (a[j] > a[j+1]){                 swap(int,a[j],a[j+1]);             }         }         if(exchg == 0 )break;     } }

알고리즘 개선 (2)

각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽 요소는 이미 정렬을 마친 상태이다. 따라서 그다음 비교에서는 이미 정렬된 요소의 뒤 인덱스부터 비교, 교환을 수행한다면 실행 시간을 대폭 감소할 수 있다.

void bubble(int a[], int n){     int k= 1;     while(k < n){         int last = n;         for(int j=1; j<=k; j++){             // printf(">[%d][%d]\n",k,j);             if (a[j] > a[j+1]){swap(int,a[j],a[j+1]);}             last = last - j;         }         k = last;     } }

버블 정렬 프로그램: 코드

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

#define swap(type, x,y)do{type t = x; x = y; y=t;}while(0)

void bubble(int a[], int n){
    int k= 1;
    while(k < n){
        int last = n;
        for(int j=1; j<=k; j++){
            // printf(">[%d][%d]\n",k,j);
            if (a[j] > a[j+1]){swap(int,a[j],a[j+1]);}
            last = last - j;
        }
        k = last;
    }
}
int main() {
    int n, temp;
    scanf("%d", &n);
    int *a = (int *)malloc(sizeof(int)*n);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    bubble(a,n);
    for (int i = 1; i <= n; i++) printf("%d\n", a[i]);
    return 0;
}

단순 선택 정렬 ~ 퀵 정렬은 다음에 다루도록 한다.