정렬 알고리즘

자료들을 정리하기 위한 알고리즘이다. 여러 가지 알고리즘이 있지만, 시간 복잡도가 가장 작은 알고리즘을 쓰는 것이 좋다. 정렬할 데이터가 얼마 없으면 상관이 없으나, 정렬할 데이터가 많아질 수록 처리 성능보다는 알고리즘이 더 중요해진다.

예시로, 1초에 100만 회의 작업을 할 수 있는 컴퓨터1이, n개를 정렬하는데 n²의 시간이 소요되는 알고리즘을 이용해서 정렬을 한다고 하고, (상대적으로 성능이 떨어지는) 1초에 1만 회의 작업을 할 수 있는 컴퓨터2는, n개를 정렬하는데 nlog₂n의 시간이 소요되는 알고리즘을 이용해서 정렬을 한다고 하자.

	처리 소요시간
n	컴퓨터1 (n2)	컴퓨터2 (nlog2n)
100	10ms	66.4ms
1,000	1000ms	997ms
10,000	1분 40초	13.3초
100,000	2시간 46분 40초	2분 46초
1,000,000	11일 13시간 46분 40초	33분 13초

컴퓨터1이 컴퓨터 2보다 처리속도가 100배나 빠르지만, 데이터가 커지면 커질수록 더 느린 결과를 보여준다.

시간 복잡도의 상한값은 Big-O 표기법으로 표시되고 (가장 느릴 경우), 그 크기는 O(1) < O(n) < O(nlogn) < O(n²) < 2^O(n) < O(n!) 순이며, 가능한 시간복잡도가 작은 알고리즘을 쓰는 것이 좋다.

종류

• 거품 정렬(Bubble sort): 가장 단순한 알고리즘이다. 이중 루프문으로 구현하며, 단순한 만큼 효율은 좋지 않다. 한 루프 내에서 가장 큰 값이나 작은 값이 발견되면 뒤로 보낸다. 즉시 뒤에 삽입되는게 아니라 처음부터 끝까지 훑고 지나가면서 비교문을 돌린다. 시간복잡도는 O(n²). 여러 정렬 알고리즘 중에 효율이 매우 나쁜 편이라서 교육용으로만 배우는 알고리즘이다.
  • 칵테일 정렬, 양방향 거품 정렬(bidirectional bubble sort)

    
    작은 수를 앞으로 보냈다 큰 수를 뒤로 보냈다 하면서 정렬한다.

  • 빗질 정렬(comb sort)

    
    오름차순 정렬에서 배열 끝 근처의 작은 값들은 '거북이'라고 하는데 거품 정렬에서 거북이로 인해 속도가 느려지는 현상을 개선한다.

• 삽입 정렬(Insertion sort): 배열의 첫 부분부터 뒤에 있는 값을 하나씩 앞으로 삽입하는 정렬. 이미 정렬된 구간을 탐색해서 알맞는 구간을 찾아 삽입한다.

  예제

  void insertionSort(int a[], int n) { //a = 배열 n = 배열의 크기
      for (int i = 1; i <= n; i++) { // 2번째 부터 n까지
          int locate = i-1; // 첫 번째
          int newitem = a[i]; // 2번째 값 (끼워넣어지는 수)
  
          while (locate >= 0 && newitem < a[locate]) {
              a[locate + 1] = a[locate], locate--; // 끼워 넣을 자리를 만든다.
          }
  
          a[locate+1] = newitem; // 끼워넣기
          
      }
  }
  

  [{1, 3, 5, 6, 7} << 4, 8, 2] -> [{1, 3, 4, 5, 6, 7} << 8, 2] -> [{1, 3, 4, 5, 6, 7, 8} << 2] -> [{1, 2, 3, 4, 5, 6, 7, 8}]

• 선택 정렬(Selection sort): 가장 큰 수 또는 가장 작은 수를 찾아서 A의 x번째 값(x는 루프문에서 하나씩 커지거나 작아진다.)과 그 자리의 값을 교환하여 정렬한다. 이때 A는 이미 정렬된 부분이다.

  

• 퀵 정렬(Quick sort)
• 병합 정렬(Merge sort)
• 힙 정렬(Heap Sort): 힙이라는 자료구조를 이용해서 정렬을 수행한다.

더 많은 정렬 알고리즘은 wikipedia:Template:Sorting 참고.

알고리즘 대장정

관련 문서

• 자료 구조