[알고리즘] 정렬 알고리즘

*한국기술대학교 원격평생교육원에서 수강중인 학점은행제 컴퓨터공학 학사 과정의 알고리즘 요약 자료(시험 대비)입니다.

 

정렬

• 순서 없이 배열되어 있는 자료를 오름차순이나 내림차순으로 나열하는 것
• 정렬의 대상 : 레코드(Record)
  • 레코드는 필드(Field)로 구성되어 있음, 키(Key) 필드로 레코드 식별

 

정렬 방식 구분

주요 기준에 따른 분류	기준	정렬방식	설명
	실행 방법	비교식 정렬	비교할 키값을 한 번에 두 개씩 비교하고, 교환하여 정렬하는 방식
		분배식 정렬	키값을 기준으로 하여 자료를 여러개 부분집합으로 분해하고 각 부분집합을 정렬함으로써 전체를 정렬하는 방식 (분할과 정복 : Divide and Conquer)
	정렬 장소	내부 정렬	컴퓨터의 주기억장치에서 정렬 입력 크기가 주기억장치의 공간보다 크지 않을 경우 수행
		외부 정렬	주기억장치뿐만 아니라 보조기억장치도 이용하여 정렬 입력의 크기가 주기억장치의 공간보다 큰 경우 수행 보조기억장치에서 입력을 여러번 나누어 주기억장치로 읽어들인 후 정렬하여 보조기억장치에 다시 저장
	안정성	안정 정렬	동일한 값에 대해 기존 순서가 유지되는 정렬 방식 [A(1), A(2)] -> 오름차순 정렬 -> [A(1), A(2)]
		불안정 정렬	동일한 값에 대해 기존 순서가 뒤바뀔 수 있는 정렬 [A(1), A(2)] -> 오름차순 정렬 -> [A(1), A(2)] 또는 [A(2), A(1)]
1차 분류(정렬 장소)	2차 분류(실행 방법)	기준	설명
내부 정렬	비교식	교환 방식	키를 비교하고 교환하여 정렬하는 방식 (선택 정렬, 버블 정렬, 퀵 정렬)
		삽입 방식	키를 비교하고 삽입하여 정렬하는 방식 (삽입 정렬, 셸 정렬)
		병합 방식	키를 비교하고 병합하여 정렬하는 방식 (2-way 병합 정렬, n-way 병합 정렬)
		선택 방식	이진 트리를 사용하여 정렬하는 방식 (힙 정렬, 트리 정렬)
	분배식	분배 방식	키 값을 여러 개의 부분집합으로 분배하여 정렬하는 방식 (기수 정렬)
외부 정렬	비교식	병합 방식	파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합하는 방법 (2-way 병합 정렬, n-way 병합 정렬)

 

 

 

<주요 정렬>

선택 정렬(Selection Sort)

• 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식
• 코드 구현시 for 루프는 n-1번 반복(0 to n-2)

 

버블 정렬(Bubble Sort)

• 데이터집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬하는 방법
• 정렬 과정이 물 속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 버블 정렬이라는 이름이 붙음
• 비교 연산에 비해 이동 연산이 더 많은 시간 소요
• 코드 구현 시 루프가 두개 생기는데,
  • 루프 1은 배열의 각 숫자를 비교하여 가장 큰 수를 마지막에 두는 연산에 해당(N ~ 2까지 반복 : 원소가 1개 남았을 때는 반복이 필요 없음)하고,
  • 루프 2는 배열 내에서의 두 값의 비교 및 교환 행위에 대한 루프(1 to last - 1 : 첫 번째 숫자부터 마지막 숫자까지 N - 1번의 비교 행위 발생)

 

삽입 정렬(Insertion Sort)

• 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 방법
• 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법
• 공간 복잡도
  • n개의 원소에 대하여 n개의 메모리 사용(집합을 구분하지만 원소가 중복되지 않음)
• 시간 복잡도
  • 순차정렬된 경우에는 비교만 수행(Best Case) -> O(n)
  • 역순으로 정렬된 경우에는 모든 비교 및 삽입 발생(Worse Case) -> O(n^2)
  • 원소들이 섞여 있는 경우(Average Case) -> O(n^2)

 

병합 정렬(Merge Sort)

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법
• 선택 정렬, 삽입 정렬, 버블 정렬(이하 O(n^2))와는 다르게 O(nlogn)의 평균 시간복잡도를 가짐(더 개선된 알고리즘)
• 분할 정복(Divide and Conquer + Combine) 알고리즘의 한 종류
  • 분할 : 입력 자료를 같은 크기의 부분집합으로 분할
  • 정복 : 부분집합의 원소들을 정렬함
  • 결합 : 정렬된 부분집합들을 하나의 집합으로 통합
• 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식
• 병합 정렬의 종류
  • 2-way 병합 : 2개의 정렬된 자료의 집합를 결합하여 하나의 집합으로 만드는 병합 방법
  • N-way 병합 : n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법
• 공간 복잡도
  • n개의 원소에 대해 2n개의 메모리 사용(분할한 부분집합을 저장하기 위한 추가 공간)
• 시간 복잡도
  • 분할 단계 : n개의 원소를 두 개로 분할하기 위해 logn번 연산 수행
  • 병합 단계 : 부분집합의 원소를 비교하면서 병합하는 단계에서 최대 n번의 비교 연산 수행
  • 전체 시간복잡도는 O(nlogn)

 

셸 정렬(Shell Sort)

• 주어진 자료 리스트를 매개 변수 h 길이를 갖는 부분집합으로 나누고, 각 부분집합에서 삽입 정렬을 수행
• h 값을 줄이는 과정을 반복하여, 매개변수 h가 1이 되면 중단(정렬의 완성)
• 부분집합으로 나누어 정렬하기 때문에 전체 원소에 대해 삽입 정렬을 수행하는 것보다 비교 연산과 교환 연산이 감소
• 부분집합 연산 과정
  • 1단계 : 부분집합의 기준이 되는 간격을 매개변수 h에 저장
  • 2단계 : 한 단계가 수행될 때마다 h의 값을 감소시키고 셸 정렬을 호출
  • 3단계 : h가 1이 될 때까지 반복
• 공간 복잡도
  • n개의 원소에 대하여 n개의 메모리와 매개변수 h의 저장 공간 사용
• 시간 복잡도
  • 매개변수 h의 값에 따라 성능이 달라지며, 자료의 특성에 따라 적절한 매개변수 사용
  • 일반적인 시간 복잡도
    • Worst Case : O(n^2)
    • Best Case : O(nlog2n)
    • Averagne Case : 평균적으로 O(n^1.5), h에 따라 다름 <- 삽입정렬에 비해 개선된 방법

 

 

퀵 정렬(Quick Sort)

• 전체 원소에 대해 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할하여 정렬하는 방법
• 왼쪽 부분집합에는 기준 값보다 작은 원소를 이동시키고, 오른쪽 부분집합에는 기준 값보다 큰 원소들을 이동시킴
• 기준값을 Pivot이라고 하며, 전체 원소 중 첫 번째, 가운데나 마지막에 위치한 원소를 선택함
• 다른 책에서는 '기준을 정해 줄 세우기'를 예시로 설명하고 있음
• 분할 정복 알고리즘 및 재귀 반복 활용
• 같은 시간복잡도를 가지는 다른 정렬 방법에 비해서 자리 교환 횟수를 줄임으로써 더 빨리 실행되어 실행 시간 성능이 좋은 정렬 방법
• 규칙
  • 1. 왼쪽 끝에서 오른쪽 끝으로 움직이면서 크기를 비교하여 피봇보다 크거나 같은 원소를 찾아 L로 표시, 단 L은 R 바로 옆(왼쪽)까지 이동하면 더 이상 오른족으로 이동하지 못함
  • 2. 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 R로 표시함. 단, R이 L의 바로 옆까지 이동하면 더 이상 왼쪽으로 이동하지 못하고 멈춤
  • 3-1. 규칙 1,2에서 찾은(규칙을 모두 수행하고 난 위치) L, R원소를 서로 교환하고, L,R의 현재 위치에서 작업을 다시 수행
  • 3-2. 규칙 1,2에서 L과 R이 같은 원소에서 만나 멈춘 경우, 피봇과 L의 위치를 서로 교환, 교환된 자리를 피봇의 위치로 확정하고 현재 단계의 정렬을 종료
  • 4. 피봇의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분집합과 오른쪽 부분집합에 대해서 규칙 1~3의 퀵 정렬을 순환적으로 반복 수행하고, 모든 부분집합의 크기가 1 이하가 되면 전체 퀵 정렬을 종료 
  • * 교재에서는 L이 R을 넘지 않고, 만나는 경우 L과 피봇을 교환한다고 했는데, 다른 글들을 보니 교차되는 경우 R을 교환하는 형태로 해결하였음. 아래 필기는 이 조건을 적용한 예시(강의에서도 R과 교환하기도 한다고 설ㅇ)
• 공간복잡도 : n개의 원소에 대해 n개의 메모리 사용
• 시간복잡도 : 루프 반복 횟수 대신 재귀 횟수를 이용하여 분석
  • 최선의 경우 : 피봇에 의해 원소들이 왼쪽 부분집합과 오른쪽 부분집합으로 정확히 n/2개씩 2등분이 되는 경우가 반복되어 수행 단계 수가 최소가 되는 경우
    • nlog2n
  • 최악의 경우 : 피봇에 의해 원소들을 분할하였을 때, 한 개와 n-1로 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가 최대가 되는 경우
    • n(n-1)/2
  • 평균의 경우 1.39nlog2n이 소요되며(연구 결과), 이는 O(nlogn)으로 근사하여 나타낼 수 있음

 

 

 

 

 

힙 정렬(Heap Sort)

• 힙 자료구조에서 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환하는 것을 이용
• 정렬되지 않은 리스트를 힙의 삽입 연산을 이용하여 힙을 구성하고,삭제 연산을 수행하여 정렬을 수행
  • 최대 힙에 대해 원소의 개수만큼 삭제 연산을 수행하여 내림차순으로 정렬 수행
  • 최소 힙에 대해 원소의 개수만큼 삭제 연산을 수행하여 오름차순으로 정렬 수행
• 리스트 -> 힙 변환 -> 힙에서 원소 삭제하여 다시 리스트로 만듦
• 힙의 종류
  • 최대 힙 : 부모 노드의 키 값이 항상 자식 노드의 키 값보다 큼
  • 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
• 공간복잡도 : 원소 n개에 대해 n개의 메모리 공간과 크기 n의 힙 저장 공간 필요
• 시간복잡도 
  • n개의 노드에 대해서 완전이진트리는 log2(n+1)의 레벨을 가지므로 완전이진트리를 힙으로 구성하는 평균시간은 O(log2n)
  • n개의 노드에 대해서 n번의 힙 재구성 작업 수행

 

트리 정렬(Tree Sort)

• 이진탐색트리를 이용하여 정렬하는 방법
  • 1단계 : 정렬할 원소들을 이진탐색트리로 구성함
  • 2단계 : 이진탐색트리를 중위 우선 순회 함
  • 중위 순회 경로가 오름차순 정렬이 됨
• 이진탐색트리
  • 이진트리 : 트리 구조 중 트리의 모든 노드의 차수를 2 이하로 제한한 트리
  • 이진트리 중 탐색용 자료구조로 사용하기 위해 만든 트리
  • 이진트리 중 다음 조건을 만족하는 트리
    • 모든 노드의 키는 서로 다른 유일한 키임
    • 왼쪽 서브트리에 있는 노드들의 키는 루트 노드의 키보다 작음
    • 오른쪽 서브트리에 있는 노드들의 키는 루트 노드의 키보다 큼
    • 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리임
• 트리 정렬은 L->D->R 순으로 처리
  • L :  현재 노드에서 왼쪽 서브트리로 이동
  • D : 현재 노드 처리
  • R : 현재 노드에서 오른쪽 서브트리로 이동
• 트리 정렬 동작 : 정렬되지 않은 리스트의 원소를 차례대로 삽입하여 이진탐색트리 구성
• 공간복잡도 : n개의 원소에 대하여 n개의 메모리 공간 및 크기 n의 이진탐색트리 저장공간 사용
• 시간복잡도
  • 노드 한 개에 대한 이진탐색트리 구성 시간 O(log2n)
  • n개 노드에 대한 이진탐색트리 구성 시간 O(nlog2n)
  • n개 노드에 대한 시간복잡도 : O(nlog2n)

 

계수 정렬과 기수 정렬

•   일반적으로 원소 비교를 기본 연산으로 하는 정렬의 하한선은 Ω(nlogn)이지만, 원소들이 특수한 성질을 가질 경우 O(n)의 선형 복잡도를 가질 수 있음을 이용한 정렬이다. 계수정렬은 원소의 크기가 ~O(n) ~ O(n)의 범위에 있을 때, 기수 정렬은 원소들이 모두 k이하의 자릿수를 가질 때 사용할 수 있다.
• 계수 정렬 : 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하면서 선형시간에 정렬하는 방법
  • 정수나 정수로 표현할 수 있는 자료에 대해서만 동작(제한사항)
  • 수행 방법
    • 1단계 : 입력 원소의 최대값까지 배열을 생성한다.
    • 2단계 : 입력 원소에 해당하는 배열의 인덱스에 입력 원소의 발생 횟수를 세어 저장한다. 이 때, 발생 횟수는 결과 배열에 입력 원소가 위치하는 최대 위치이다.
    • 3단계 : 발생 횟수가 저장되어 있는 배열을 참고하여 결과 배열에 입력 원소를 저장한다.
  • 공간복잡도 : n개의 원소에 대하여 n+k(k는 입력 원소 중 가장 큰 값)의 메모리 사용
  • 시간복잡도 : 평균 수행시간 : Θ(n)
    • 코드로 작성하면 일반적으로 배열 생성, 빈도 기록, 누적합으로 변환, 배열 완성 시에 각각 루프를 돌게 되는데, 이 중 배열 생성, 누적합 변환의 경우 Θ(n), 다른 루프는 Θ(k)의 복잡도를 가진다. 따라서 일반적인 평균 수행시간은 Θ(n)라고 할 수 있으나, k가 O(logn)보다 크다면 (입력 원소 값의 최댓값이 현저히 크다면) 알고리즘의 효율성이 크게 떨어질 수 있다.
• 기수 정렬 : 입력이 모두 k이하 자릿수를 가진 자연수인 경우에 쓰일 수 있는 정렬 방법으로, 제한적인 범위 내에 있는 숫자에 대해서 각 자릿수별로 정렬함
  • 숫자 대 숫자를 비교하는 정렬 방식이 아닌 숫자를 부분적으로 비교하는 정렬 방법(기수 : 특정 진수의 값을 의미)
  • 가장 낮은 자릿수부터 그 다음 자릿수를 순차적으로 비교하여 정렬, 특정 자릿수의 값이 동일하더라도 다른 값에 의해 순서가 정의되므로, 안정성을 가지는 정렬이라고 할 수 있음
  •  공간복잡도 : n개의 원소에 대해 n개의 메모리 공간 사용, 기수 r에 따라 버킷 공간이 추가로 필요
  • 시간복잡도
    • For 루프를 k번 반복
      • 루프가 한 번 수행될 때, n개의 숫자의 i자릿수를 읽으며 r개로 분류하여 개수를 세고, 그 결과에 따라 숫자가 이동
      • O(n+r)의 시간이 소요되고, k와 r이 n에 비해 현저히 작다면 O(n)
  • 주민등록번호, 계좌번호 등 대량의 숫자를 기반으로 하는 상용 데이터베이스에서의 정렬에 유용함