[algorithm] 정렬 알고리즘

• 정렬의 개념
  • 정렬이란
    • 주어진 데이터를 값의 크기 순서에 따라 재배치 하는 것
    • 정렬수행시점에 데이터가 어디에 저장되어 있는가?
      • 내부정렬
        • 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식
        • 비교 기반 알고리즘
          • 버블정렬, 선택정렬, 삽입정렬, 셸정렬 O(n^2)
          • 합병정렬, 퀵정렬, 힙정렬 O(nlogn)
        • 데이터 분포 기반 알고리즘
          • 계수 정렬, 기수 정렬 O(n)
      • 외부 정렬
        • 모든 데이터를 주기억장치에 저장할 수 없는 경우 모든 데이터를 보조기억장치에 저장한 채 그중 일부데이터씩 반복적으로 주기억장치에서 읽어들여서 정렬하는 방식
  • 안정적 stable 정렬
    • 동일한 값을 갖는 데이터가 여러개 있을 때 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식
  • 제자리 in-place 정렬
    • 입력 데이터를 저장한 공간 이외에 추가적인 저장 공간을 상수 개만 필요로 하는 정렬 방식
      • 입력 크기 n이 증가함에도 불구하고 추가적인 저장 공간은 증가하지 않음
  • 기본가정
    • A[i] > 0, (0<=i<=n-1)
    • if i < j then A[i] <= A[j], (0<=i, j<=n-1)
    • 입력 크기(데이터 개수) -> n
    • 입력 배열 -> A[0...n-1]
    • 입력 값 -> 양의 정수
    • 정렬 방식 -> 오름차순 
• 버블 정렬
  • 모든 인접한 두 값을 비교하여 왼쪽의 값이 더 큰 경우에는 자리를 바꾸는 과정을 반복해서 정렬하는 방식
  • 안정적 정렬 알고리즘
  • 제자리 정렬 알고리즘
    • 입력 배열 A[], 입력 크기 n
      • 추가적인 저장 공간은 상수 개(-> 제어변수 i와 j, 데이터 교환을 위한 변수)
      • 입력 데이터의 상태에 따라 성능이 달라짐
        • 역순으로 정렬된 경우
          • O(n^2)
        • 제 순서로 정렬된 경우
          • O(n)
• 선택 정렬
  • 주어진 데이터 중에서 가장 작은 값부터 차례대로 '선택'해서 나열하는 방식
  • 특징
    • 언제나 동일한 시간 복잡도 O(n^2)
      • 최소값을 찾는 과정이 데이터의 입력 상태에 민감하지 않기 때문에
    • 제자리 정렬 알고리즘
    • 안정적이지 않은 정렬 알고리즘
• 삽입 정렬
  • 주어진 데이터를 하나씩 뽑은 후 나열된 데이터들이 항상 정렬된 형태를 갖도록 뽑은 데이터를 바른 위치에 '삽입'해서 나열하는 방식
    • 입력 배열을 정렬 부분과 미정렬 부분으로 구분해서 
      • 미정렬 부분에서 첫번째 데이터를 뽑은 후, 정렬 부분에서 제자리를 찾아 뽑은 데이터를 삽입하는 과정을 반복
  • 특징
    • 역순으로 정렬된 경우
      • O(n^2)
    • 제 순서로 정렬된 경우
      • O(n)
    • 입력이 거의 정렬된 경우 다른 어떤 정렬 알고리즘보다 빠른 수행 시간 O(n)을 가짐
    • 안정적인 정렬 알고리즘
    • 제자리 정렬 알고리즘
    • 삽입될 위치를 찾기 위해 한 번에 한 자리씩만 이동
      • 데이터의 이동이 여러번 발생
• 셸 정렬
  • 삽입 정렬의 단점 보완
    • 데이터가 삽입될 위치에서 멀리 떨어져 있어도 바로 왼쪽의 이웃한 데이터와의 비교를 통해 한 번에 한 자리씩만 이동 -> 제자리를 찾는데 느리다. 
  • 기본 아이디어
    • 멀리 떨어진 데이터와 비교, 교환해서 처리 속도 향상
      • 처음에는 머릴 떨어진 두 데이터를 비교해서 필요시 위치를 점차 가까운 위치의 데이터를 비교, 교환한 뒤, 맨 마지막에는 인접한 데이터를 비교, 교환하는 방식
      • 입력 배열을 부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 변화시켜 가면서 반복
  • 성능 분석
    • 최악의 경우 -> O(n^2)
    • 최선의 경우 -> O(nlogn)
  • 특징
    • 간격의 크기 D를 계산하는 방식에 따라 성능이 달라짐
      • D = n/2^i (n: 데이터 개수, i=1,2,3 ...)
    • 가장 좋은 간격을 찾는 것은 미해결 과제
    • 간격의 크기 D는 순열의 역순으로 차례대로 적용
    • 제자리 정렬 알고리즘
    • 안정적이지 않은 정렬 알고리즘
• 정렬의 개념
  • 내부 정렬, 비교 기반 <-> 데이터 분포 기반, 안정적, 제자리
• 버블 정렬
  •  O(n^2), 안정적, 제자리, 입력 데이터의 상태에 따라 다른 성능을 보임
• 선택 정렬
  • O(n^2), 불안정적, 제자리, 언제나 동일한 성능
• 삽입 정렬
  • O(n^2), 안정적, 제자리, 입력 데이터의 상태에 따라 다른 성능을 보임
  • 삽입할 위치를 찾기 위해 여러 번의 데이터 이동이 필요
• 셸 정렬
  • O(n^2), 삽입 정렬 보완, 부분배열의 크기와 개수를 변화시키며 반복
  • 불안정적, 제자리, 간격의 크기를 계산하는 방식에 따라 다름