• 정렬이란?
    • 주어진 데이터를 일정한 기준에 따라 순서대로 나열하는 것
  • 정렬 방법
    • 오름차순(ascending) → 작은 것에서 큰 것으로, 오래된 것 부터
    • 내림차순(descending) → 큰 것에서 작은 것으로, 최근 것 부터
    • 단일 키 → 하나의 정렬 기준
    • 복합 키 → 두 개 이상의 정렬 기준
  • 정렬과 이진탐색
    • Binary Search
    • 정렬된 데이터에 대해서 O(log n) 의 성능을 보이는 탐색 알고리즘
    • 정렬의 이유 → 데이터를 빠르게 찾기 위해서
    • 데이터 정렬 → 이진 탐색이 가능하도록 데이터를 나열
  • 정렬의 목표
    • 복잡성을 줄이고, 안정성을 높인다.
      • 복잡도
        • 메모리 사용량과 CPU 사용 시간을 줄이는 것이 목표
      • 안정성
        • 일관된 실행결과를 보장
  • 정렬 구분

    • 시간복잡도 O(n^2) 계열 O(n*log n) 계열

      • 원소 개수가 10, 100 에서 시간복잡도 따른 비교

        Untitled

        Untitled

        Untitled

    • 실행방법 Comparison Sort(비교 기반 정렬) Distribution Sort (분포 기반 정렬)

    • 실행 메모리 Internal Sort(내부 정렬) External Sort(외부 정렬)

  • 안정/불안정 정렬 이란?
    • 안전 정렬 ( Stable Sort )
      • 정렬 대상에 대해서 동일한 값을 가진 데이터의 순서가 원래의 순서와 같이 유지되는 정렬 방법 입니다.
      • 즉, 데이터가 정렬된 상태에서 어떤 작업을 수행해도 데이터의 순서가 바뀌지 않는다는 것을 의미 합니다.
      • 종류
        • 버블 정렬 / 삽입 정렬 / 병합 정렬
    • 불안정 정렬 ( Unstable Sort )
      • 정렬 대상에 대해서 동일한 값을 가진 데이터의 순서가 변경 되는 정렬 방법 입니다.
      • 즉, 데이터가 정렬 되면서 데이터의 순서가 바뀐 것을 의미 합니다.
      • 종류
        • 선택 정렬 / 퀵 정렬 / 힙 정렬
    • 예시 ) 배열 [ 1, 7(1), 3, 5, 4, 7(2), 9 ] 와 같이 배열이 있습니다. 이때 안정 정렬의 기준은 동일한 값인 7 에 대해서 주목하면 됩니다.
      • 위 배열에 대해서 정렬을 진행한 경우
      1. [1, 3, 4, 5, 7(1), 7(2), 9] → 안정 ( Stable ) 정렬
      2. [1, 3, 4, 5, 7(2), 7(1), 9] → 불안정 ( Unstable ) 정렬
      • 7 에 대한 기존의 순번이 변경이 되지 않고 유지 된다면 안정 정렬로 보며, 7 에 대한 순번이 변경이 되면서 불안정 정렬이 됩니다.
    • 그런데 왜 ? 안정과 불안정이 있을까? 그냥 정렬만 하면 되는거 아닌가 라는 의문이 들 수 있다.
      • 사실 정렬이라면 데이터를 순서대로 줄만 세워 주면 되는 것 아닌가? 정렬의 기준이 요소 하나 전체라면 이라면 큰 의미는 없는 것이 맞다.
      • 다만, 보통의 경우에 요소의 전체를 기준으로 하지 않는다. 예를 들어 학생 정보를 기반으로 하는 경우 학생 정보 전체를 기준으로 하지 않고 학생 정보 안의 학번을 이용해서 정렬을 한다. 이때, 학년을 기준으로 정렬을 하기로 하고 같은 학생 동명이인에 대해서는 어떻게 정렬이 되어야 할까?
      • 여기서 불안정 정렬이라면 학년을 기준으로 분류만 되고 같은 학년 내에 있는 학생 정보는 뒤죽 박죽 일 것이다. 즉, 학번 정보가 오름차순, 내림차순 을 표현할 수 없다. 기존에 이름을 기준으로 정렬이 되어 있다하더라고 불안정 정렬로 진행한다면 보장 할 수 없고, 깨질 확률이 크다.
      • 반면에 안정 정렬을 한다면 기존의 정렬에 대해서 순서를 보장해준다는 이점이 있다.
      • 대체적으로 우리가 정한 기준으로 정렬을 구하고 그 안에서의 순서를 통해 값을 가져와야 하는 경우가 많다. 그러므로 안정 정렬과 불안정 정렬에 대한 차이는 알아야 한다.
  • 제자리 정렬(In-place Sort) 이란?
    • 제자리 정렬은 추가 메모리를 사용하지 않고 데이터를 직접 조작하여 정렬하는 알고리즘 입니다.
    • 즉, 별도의 메모리 사용 없이 주어진 배열만을 이용해 정렬하는 것을 의미 합니다. 단 예외적인 상황으로 너무 작은 메모리를 사용한다면 제자리 정렬로 볼 수 있습니다.
    • 제자리 정렬의 장/단점
      • 장점
        • 메모리 사용량이 적어 메모리 제한이 있는 환경에서 유용합니다.
        • 추가적인 메모리를 사용하지 않기 때문에 실행 속도가 빠릅니다.
      • 단점
        • 데이터를 조작하기 때문에 데이터가 손상될 가능성이 있습니다.
        • 데이터를 복사해두고 원본 데이터는 그대로 두는 안정적인 알고리즘에 비해 데이터의 완전성을 보장할 수 없습니다.