[알고리즘] 정렬 00 : 정렬 개요

정렬(Sorting)

 주어진 일련의 데이터( 보통 배열 )를 순서대로 재배치하는 것. 물건을 가격별로 세워두기 위해 조사하거나, 유통기한이 임박한 순서대로 제품을 출고해야 하는 등 정보의 순서가 의미 있는 분야라면 어디든지 사용될 수 있다.

 알고리즘의 효율성은 데이터 및 데이터가 가진 특성에도 영항을 받지만, 해당 알고리즘을 구동하는 환경( 메모리, CPU 파워, 지원되는 소프트웨어 등 )과 같은 요소에도 영향을 받을 수 있다.

알고리즘 성능 측정 수단

• 시간 효율(Time Complexity)
  • Big-O, Big-Ω, Big-Θ 의 표현법을 이용.
  • best-case, worst-case, average-case 을 나타낼 수 있음.
• 공간 효율(Space Complexity)
  • 제자리성(In-place algorithm) : 입력을 정렬할 때 입력 원소 이외의 원소를 저장하는데 상수 배 이상의 메모리 공간을 요구하지 않는 알고리즘.
    ex) 어떤 알고리즘이 입력 원소 개수에 비례하는 추가 메모리 공간을 요구한다면, 공간 효율은 O(n) 이므로 추가 메모리가 n에 비례한다. 따라서 해당 알고리즘은 제자리성이 없다.
•  안정성(Stability) : 동일 값을 가지는 데이터들에 대해 정렬 전후 데이터 순서가 그대로 유지되는 알고리즘.
  ex) cb₁ab₂ 이 ab₂b₁c로 정렬되면, b₁과 b₂의 위치가 정렬 중에 변경되므로 안정성이 없는 알고리즘이다.
  • 보통 가까운 거리에서 원소의 정렬이 발생하면( ex : 버블 정렬 ), 안정성이 존재한다.

정렬시간

알고리즘의 시간복잡도를 통상 Big-O 표기법을 통해 나타내지만, 실제 정렬시간은 더 고려할 점이 있다.

• 정렬시간 = 데이터에 접근하는 시간 + 데이터를 비교&재배치하는 시간

우리가 알고리즘을 살필 때 주로 고려하는 시간은 데이터를 비교 및 재배치하는데 걸리는 시간이다. 반면 데이터에 접근하는 시간에는 소홀하는 경향이 있다. 사실 많은 알고리즘들이 메모리에서 데이터를 다루는 것을 전제로 하는데, 이 경우 메모리의 랜덤 엑세스를 통한 빠른 접근속도 덕분에 레코드 접근시간을 충분히 무시할 수 있다. 그러나 데이터의 규모가 커져 메모리를 통해 한번에 데이터를 모두 처리할 수 없는 수준에 도달하면, 필연적으로 보조기억장치에 의존하게 되므로, 보조기억장치와 메모리 사이의 커다란 속도 차이때문에 데이터 접근시간 역시 무시할 수 없는 수준이 된다. 따라서 보조기억장치를 이용할 정도로 큰 규모의 데이터를 처리해야 한다면 물리/환경적 요소도 충분히 고려해야 한다.

• 내부 정렬(Internal sort) : 자료를 주기억장치(메모리)만을 이용하여 정렬하는 것.
• 외부 정렬(External sort) : 보조기억장치에 전체 자료를 저장한 후, 일부분씩 메모리에 옮겨 정렬하는 방식.

정렬의 종류

• 비교기반(Comparison-based) 알고리즘 : Selection, Bubble, Insertion, Shell, Heap, Quick, Merge ...
• 분포기반(Distribution-based) 알고리즘 : 계수정렬(Counting), 기수정렬(Radix), 버킷정렬(Bucket) ...