[Algorithm] 정렬 알고리즘

cateto·2022년 6월 5일
0

정렬 알고리즘

  • 정렬 : 주어진 데이터를 값의 크기 순서에 따라 재배치하는 것

  • 정렬 수행시점에 데이터가 어디에 저장되어 있는가?

    • 내부정렬 : 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식
    • 외부정렬 : 모든 데이터를 보조기억장치에 저장한 채 그중 일부데이터를 꺼내서 정렬하는 방식
  • 내부 정렬 알고리즘

    • 비교 기반 알고리즘 : 데이터를 직접 비교하여 결정에 따라 정렬
      • 버블
      • 선택
      • 삽입

      • ---------------- O(n2)O(n^2)
      • 합병

      • ---------------- O(nlogn)O(nlogn)
    • 데이터 분포 기반 알고리즘 : 데이터의 분포적 특성을 기반으로 정렬
      • 계수 정렬
      • 기수 정렬
        ---------------- O(n)O(n)
  • 안정적 정렬 (Stable Sort)
    : 동일한 값을 갖는 데이터가 여러개 있을 때 정렬 전의 상대적인 순서가 그대로 유지되는 방식

  • 제자리 정렬 (in-place Sort)
    : 입력 데이터를 저장한 공간 이외에 추가적인 저장 공간을 상수 개(고정적인 값) 필요로 하는 정렬방식

Bubble Sort

  • 왼쪽(또는 오른쪽)에서부터 모든 인접한 두 값을 비교하여 왼쪽의 값이 더 큰 경우에는 자리를 바꾸는 과정을 반복해서 정렬하는 방식
BubbleSort(A[], n)
{
  for (i=0; i<n-1; i++){
    for (j=0; j<(n-1)-i; j++){
      if(A[j]> A[j+1]){
      // A[j] 와 A[j+1] 의 자리바꿈;
      }
    }
  }
  return A;
}
  • O(n2)O(n^2)
  • 안정적 정렬 알고리즘
  • 제자리 정렬 알고리즘
    • 입력배열 A[], 입력크기 n
  • 자리바꿈이 한 번도 발생하지 않으면 알고리즘이 종료되도록 개선 가능
    • → 데이터가 제 순서로 정렬된 경우에는 O(n)O(n)

Selection Sort

  • 주어진 데이터 중에서 최솟값을 차례대로 선택해서 나열하는 방식
  • O(n2)O(n^2)
  • 불안정적인 정렬 알고리즘
  • 제자리 정렬 알고리즘
  • 삽입 될 위치를 찾기 위해

Insert Sort

  • 주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 형태를 가지도록 바른 위치를 찾아 뽑은 데이터를 삽입해서 나열하는 방식
  • O(n2)O(n^2)
  • 안정적인 정렬 알고리즘
  • 제자리 정렬 알고리즘
  • 입력이 제 순서로 정렬된 경우에는 O(n)O(n)

Shell Sort (by Donald L.Shell)

  • 삽입정렬의 단점 :
    • 데이터가 삽입될 위치에서 멀리 떨어져 있어도 바로 왼쪽의 이웃한 데이터와의 비교를 통해 한번에 한자리 씩만 이동 -> 제자리를 찾는데 느리다.
  • 단점 해결
    • 멀리 떨어진 데이터와 비교, 교환하여 처리 속도를 향상
    • 처음에는 멀리 떨어진 두 데이터를 비교해서 필요 시 위치를 바꾸고, 점차 가까운 데이터와 비교 교환한 뒤에 맨 마지막에는 인접한 데이터를 비교, 교환하는 방식
    • 부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분 배열을
ShellSort(A[], n){
  for (D=[n/2];D>=1; D=[D/2]){
   for (i=D; i<n; i++){
     val = A[i];
     for ()
   }
  }
}
  • O(n2)O(n^2)
  • 제자리 정렬 알고리즘
  • 안정적이지 않은 알고리즘
  • 간격의 크기는 부분배열의 개수이며, 동시에 부분배열에서 이웃한 원소간의 거리를 의미
    • → 간격의 크기를 계산하는 방식에 따라 성능이 달라짐
profile
Curious for Everything

0개의 댓글