정렬(Sorting)

정렬(Sorting)이란 데이터를 특정 기준에 따라서 순서대로 나열하는 것이다. 예를들어 오름차순, 내림차순 등이 있다.

정렬 알고리즘 중에 유명한 것은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬등이 있다.

 

1. 선택 정렬

 

7

5

9

0

3

1

6

2

4

8

위와 같은 상태의 데이터가 있다고 가정해보자. 선택정렬은 데이터들 중 가장 작은 데이터를 선택해 맨앞의 데이터와 바꾸고, 그다음 작은 데이터는 두번째 데이터와 바꾸고... 의 과정을 반복하는 것이다. 일단 가장 작은 데이터를 찾는다. 그리고 맨앞의 7과 바꾼다.

0

5

9

7

3

1

6

2

4

8

이제 0은 정렬이 된 상태이다. 이제 두번째로 작은 값인 1을 두번째 값과 바꾼다.

0

1

9

7

3

5

6

2

4

8

0과 1은 정렬이 된 상태이다. 이를 계속 반복하면 결국 0부터 9까지 정렬된 데이터를 얻을 수 있다. 코드는 다음과 같다.

#include <iostream>
using namespace std;

int main() {
  int arr[10]={7,5,9,0,3,1,6,2,4,8};
  int n=10;
  int small_idx;
  for(int i=0;i<n;i++){
    small_idx=i;
    for(int j=i+1;j<n;j++){
      if(arr[small_idx]>arr[j])
        small_idx=j;
    }
    swap(arr[small_idx],arr[i]);
  }

  for(int i=0;i<10;i++){
    cout<<arr[i]<<" ";
  }
}

선택정렬의 시간복잡도는 어떻게 될까?

정석적으로 접근하면, N-1번만큼 작은 수를 찾아서 맨앞으로 보내기 때문에 N+(N-1)+(N-2)+...+2 이므로 (N^2+N)/2 이다. 이는 O(N^2) 로 표현 할 수 있다. 간단하게 생각하면 2중 for문에서 각각 N회씩 계산을 하므로 O(N^2) 라고 이해 할 수 있다.

 

 

2. 삽입 정렬

위와 같은 상태의 데이터가 있다고 가정하자.

7

5

9

0

3

1

6

2

4

8

삽입 정렬 에서는 두번째 데이터 부터 시작한다. 첫번째 데이터인 7은 이미 그자체로 정렬 되어 있다고 가정하기 때문이다. 5는 앞의 수인 7보다 작으므로 7의 앞으로 이동한다.

5

7

9

0

3

1

6

2

4

8

다음 수 인 9는 5와 7보다 크므로 7의 뒤에 위치한다. 즉  그대로 둔다.

5

7

9

0

3

1

6

2

4

8

0은 5,7,9보다 작으므로 맨앞에 삽입한다.

0

5

7

9

3

1

6

2

4

8

이 과정을 반복하면 정렬이 되는 것이다. 삽입 정렬을 할 때에는 이동하고자 하는 데이터를 선택하고 왼쪽으로 비교를 진행하여 그 데이터보다 작은 데이터를 만나면 그 위치에서 삽입하면 된다.

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void) {
    for (int i = 1; i < n; i++) {
        // 인덱스 i부터 1까지 감소하며 반복하는 문법
        for (int j = i; j > 0; j--) {
            // 한 칸씩 왼쪽으로 이동
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            }
            // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            else break;
        }
    }
    for(int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
}

삽입 정렬의 시간 복잡도는 O(N^2)이다. 하지만 정렬하고자하는 데이터가 거의 정렬되어 있는 경우에는 실행 속도가 많이 빨라진다. 보통의 상황에서는 삽입정렬은 비효율적인것은 맞지만 데이터가 거의 정렬되어 있는 경우는 퀵 정렬보다 빠르다.

 

3. 퀵 정렬

퀵 정렬의 핵심 알고리즘은 다음과 같다.

'기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.'

이때 기준데이터인 pivot은 배열에서 첫번째 데이터를 pivot으로 정한다. 피벗을 정한 이후에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음에는 데이터의 위치를 서로 교환 해준다.

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

void quickSort(int* arr, int start, int end) {
    if (start >= end) return; // 원소가 1개인 경우 종료
    int pivot = start; // 피벗은 첫 번째 원소
    int left = start + 1;
    int right = end;
    while (left <= right) {
        // 피벗보다 큰 데이터를 찾을 때까지 반복
        while (left <= end && arr[left] <= arr[pivot]) left++;
        // 피벗보다 작은 데이터를 찾을 때까지 반복
        while (right > start && arr[right] >= arr[pivot]) right--;
        // 엇갈렸다면 작은 데이터와 피벗을 교체
        if (left > right) swap(arr[pivot], arr[right]);
        // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
        else swap(arr[left], arr[right]);
    }
    // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);
}

int main(void) {
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
}

퀵 정렬은 시간복잡도가 평균적으로 O(NlogN)을 따른다. 하지만 최악의 경우에는 O(N^2) 을 가진다. 이미 데이터가 정렬이 되어 있는경우가 이러하다. 이럴때는 퀵 정렬 보다 삽입정렬을 사용할 때가 훨씬 빠르게 작동 한다.

C++ 에서는 퀵 정렬을 기반으로 제공하는 라이브러리가 있다. algorithm 헤더에 포함되어있는 sort()함수이다.