[자료구조]04. 정렬

Published on Aug 12, 2020

목차

  1. 정렬이란
  2. 선택 정렬
  3. 삽입 정렬
  4. 버블 정렬



정렬이란

정렬(sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)로 나열하는 것을 의미합니다. 정렬은 가장 기본적이고 중요한 알고리즘이며 자료 탐색 시에 필수적입니다. 정렬 알고리즘은 매우 많지만 모든 경우에서 최상의 성능을 보여주는 최적 알고리즘은 없습니다. 따라서 상황에 맞춰서 적절한 알고리즘을 선택합시다.

내부 정렬과 외부 정렬

정렬 알고리즘은 내부 정렬(internal sorting)과 외부 정렬(externel sorting)이 있습니다. 전자는 모든 데이터가 주기억 장치에 저장된 상태일 때에 후자는 외부기억장치에 대부분의 데이터가 있고 일부만 주기억장치에 있을 때에 정렬을 하는 방법입니다. 여기서는 내부 정렬을 다룹니다.

안정성

안정성(stability)란 동일한 값을 갖는 레코드가 여러 개 있을 경우, 정렬 후에도 레코드의 상대적인 위치가 바뀌지 않음을 뜻합니다.


5 1 3 2 3

위와 같은 경우가 있습니다. 왼쪽 3을 3(1) 오른쪽 3을 3(2)라고 라벨을 붙여봅시다.

Sorting 후에

1 2 3 3 5

3(1)이 그대로, 3(2)보다 왼쪽에 있다면 상대적인 위치가 변하지 않은 stable한 정렬이 됩니다.



선택 정렬

선택 정렬(selection sort)은 오름차순으로 정렬할 경우에는 최솟값을 찾고, 내림차순으로 정렬할 경우에는 최댓값을 찾아 앞에서부터 정렬시킵니다.

선택 정렬 방법

  1. 인덱스를 배열의 처음을 가리키게 합니다.
  2. 인덱스부터 배열 끝까지 돌면서 배열의 최솟값을 찾습니다.
  3. 인덱스의 값과 최솟값을 바꿉니다.
  4. 인덱스를 하나 증가시킵니다.
  5. 인덱스가 끝을 가리킬 때까지 2~4 과정을 반복합니다.


선택 정렬 과정

1단계: index=0. 초기 상태.

5 3 8 1 2 7


2단계: index=0부터 배열을 돌아 최솟값을 찾습니다.
이후 index의 값과 최솟값 바꿉니다.

<5> 3 8 <1> 2 7


3단계: index=1

1 <3> 8 5 <2> 7


4단계: index=2

1 2 <8> 5 <3> 7


5단계: index=3. 이때는 index의 값과 최솟값이 동일하므로 3번 과정을 생략합니다.

1 2 3 <5> 8 7


6단계: index=4

1 2 3 5 <8> <7>


7단계: index=5. 인덱스가 배열 끝까지 왔으므로 정렬을 종료합니다.

1 2 3 5 7 8


선택 정렬 구현

i는 인덱스, least는 최솟값의 인덱스입니다.

#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

void selection_sort(int list[], int n) {
    int i, j, least, temp;
    for (i=0; i<n-1; i++) { // i는 n-2까지.
        least = i;
        for (j=i+1; j<n; j++) {
            if (list[j]<list[least])  least = j;
        }
        SWAP(list[i], list[least], temp);
    }
}


선택 정렬 분석

비교 횟수와 이동 횟수의 측면에서 분석해 봅시다.

비교 횟수을 비교하면, 외부 루프는 n-1번 실행되고, 내부 루프는 (n-1)-i (i는 0부터 n-2까지 변함)번 반복됩니다.

(n-1)+(n-2)+ … +1 = n(n-1)/2 = O(n2)

이동 횟수를 비교하면, 외부 루프는 n-1번 실행되고, 그 때마다 3번씩 이동(SWAP)하기 때문에 총 3(n-1)번 이동합니다.


선택 정렬은 자료 이동 횟수가 미리 결정되어 있다는 장점이 있지만, 자료가 정렬된 경우에는 불필요하게 자기 자신과 교환을 해야 합니다.(SWAP 전에 if문을 추가하여 문제를 해결할 수 있습니다.)



삽입 정렬

삽입 정렬(insertion sort)은 정렬된 리스트에 새로운 값을 올바른 위치에 삽입하는 방식입니다.

삽입 정렬 방법

  1. 인덱스를 1로 둡니다. 인덱스 이전의 배열을 정렬된 배열로 정의합니다.
  2. 현재 인덱스를 정렬된 배열 안에서 올바른 위치에 삽입합니다.
  3. 인덱스를 하나 증가시킵니다.
  4. 인덱스가 끝을 가리킬 때까지 2~3 과정을 반복합니다.


삽입 정렬 과정

1단계: index=1. 초기 상태.

[5] 3 8 1 2 7


2단계: index=1. 인덱스의 값인 3을 졍렬된 배열에 올바른 위치에 삽입합니다.

[5] <3> 8 1 2 7


3단계: index=2.

[3 5] <8> 1 2 7


4단계: index=3

[3 5 8] <1> 2 7

이 때의 과정을 자세하게 과정을 정리해보겠습니다.


(index = 2의 값인 8부터 index=0의 값인 3까지 차례대로 비교한다.)
8보다 1이 작으므로 8을 오른쪽으로 한 칸 옮기고,
5도 1이 더 작으므로 5를 오른쪽으로 한 칸 옮기고,
3도 1이 더 작으므로 3을 오른쪽으로 한 칸 옮긴다.
1을 남은 자리에 저장한다.


5단계: index=4

[1 3 5 8] <2> 7


6단계: index=5

[1 2 3 5 8] <7>


7단계: 정렬 완료.

1 2 3 5 7 8


삽입 정렬 구현

i는 인덱스, j는 정렬된 배열의 인덱스, key는 인덱스(i)의 값입니다.

void insertion_sort(int list[], int n) {
    int i, j, key;
    for (i=1; i<n; i++) {
        key = list[i];
        for (j=i-1; j>=0 && list[j]>key;j--)
            list[j+1] = list[j]; // key값을 찾을 때까지 정렬된 배열을 한 칸씩 옮긴다.
        list[j+1] = key;
    }
}


삽입 정렬 분석

삽입 정렬의 복잡도는 입력 자료의 구성에 따라 달라집니다.
입력 정보가 정렬되어 있는 경우가 가장 빠릅니다. 외부 루프 n-1번 실행되고 각 단계에서 이동 없이 비교 연산만 1번 있으므로 시간 복잡도는 O(n)입니다.
입력 자료가 역순일 때 최악의 복잡도를 가집니다. 각 단계에서 앞에 놓인 자료들은 전부 한 칸씩 뒤로 이동해야 하므로 총 비교 횟수는 다음과 같습니다.

1+2+ … +(n-1) = n(n-1)/2 = O(n2)

총 이동 횟수는 외부 루프의 각 단계마다 i+2번을 이동해야 하므로 다음과 같습니다.

n(n-1)/2 + 2(n-1) = O(n2)



버블 정렬

버블 정렬(bubble sort)는 인접한 2개의 레코드를 비교하여 역순일 경우에 교환하는 과정을 배열의 처음부터 끝까지 진행하고, 전체 레코드가 정렬될 때까지 이 과정을 반복하는 방식입니다.

버블 정렬 방법

  1. 인덱스를 배열의 처음을 가리키게 합니다.
  2. 인덱스의 값과 그 오른쪽 값을 비교합니다.
  3. 인덱스의 값이 오른쪽 값보다 크면 교환합니다.
  4. 인덱스 값을 하나 증가시킵니다.
  5. 인덱스가 끝을 가리킬 때까지 2~4의 과정을 반복합니다.
    => 최댓값을 배열의 마지막 값으로 만들었습니다.
  6. 1~5의 과정을 반복하며 큰 값부터 뒤에 정렬합니다.


버블 정렬 과정

1단계: index=0. 초기 상태.

5 3 8 1 2 7


2단계: index=0과 index=1의 값을 비교하여 교환 여부를 결정합니다.
5가 3보다 크므로 이 둘을 교환합니다.

<5> <3> 8 1 2 7


3단계: index=1과 index=2의 값을 비교하여 교환 여부를 결정합니다.

3 <5> <8> 1 2 7


4단계: index=2

3 5 <8> <1> 2 7


5단계: index=3

3 5 1 <8> <2> 7


6단계: index=4

3 5 1 2 <8> <7>


7단계: index=5 스캔 완료.
이후 동일한 과정(1-6단계)을 반복하며 큰 값부터 뒤에 정렬한다.

3 5 1 2 <7> [8]


8단계: index=4,5 스캔 완료. (7을 정렬하기 위한 과정 생략)

3 1 2 5 [7 8]


9단계: index=3~5 스캔 완료. (5를 정렬하기 위한 과정 생략)

1 2 3 [5 7 8]


10단계: index=2~5 스캔 완료. (3을 정렬하기 위한 과정 생략)

1 2 [3 5 7 8]


11단계: index=1~5 스캔 완료. (2를 정렬하기 위한 과정 생략)

1 [2 3 5 7 8]


12단계: index=0~5 스캔 완료. 정렬 완료. (1을 정렬하기 위한 과정 생략)

[1 2 3 5 7 8]


버블 정렬 구현

#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

void buble_sort(int list[], int n) {
    int i, j, temp;
    for (i=n-1; i>0; i--) {
        for (j=0;j<i; j++) // 하나 스캔
            if (list[j]>list[j+1])
                SWAP(list[j], list[j+1], temp);
    }
}


버블 정렬 분석

비교 횟수는 항상 일정합니다.

n(n-1)/2 = O(n2)

이동 횟수는 세 가지 경우로 나눌 수 있습니다. 최악의 경우 입력 자료가 역순으로 정렬되어 있으면 총 이동 횟수는 (비교 연산)*3입니다. 최상의 경우 입력자료가 정렬되어 있으면 이동 횟수는 0입니다. 평균적인 경우에는 자료 이동이 0번에서 i번까지 같은 확률로 일어나므로 O(n2)의 시간복잡도를 가집니다.

버블 정렬은 하나의 요소가 특정 위치로 이동하기 위해서 반복해서 요소를 교환해야 합니다. 일반적으로 자료의 교환 작업이 이동 작업보다 복잡하기 때문에 버블 정렬은 잘 쓰이지 않습니다.



출처

C언어로 쉽게 풀어쓴 자료 구조, 천인국 저