Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 김영평생교육원
- 행렬식
- 선형대수학
- 중간고사
- 학사
- 정보처리기사 기출
- LU분해 알고리즘 구현
- 머신러닝
- 정보처리기사 후기
- 컴공수학
- 행렬식 파이썬
- 정규방정식
- LU분해 파이썬
- LU분해
- 학점은행제
- 행렬식의 정의
- 한국데이터산업진흥원
- 라이프니츠 공식
- 원격평생교육진흥원
- 화웨이라우터
- 가우스조던소거법
- 가우스조르당소거법
- 여인수 전개
- 알고리즘
- determinant
- 메가존아이티평생교육원
- lte라우터
- 한국기술교육대학교
- 선형회귀모델
- 컴퓨터공학
Archives
- Today
- Total
gyeo-ri.com
[알고리즘] 정렬 알고리즘 본문
*한국기술대학교 원격평생교육원에서 수강중인 학점은행제 컴퓨터공학 학사 과정의 알고리즘 요약 자료(시험 대비)입니다.
정렬
- 순서 없이 배열되어 있는 자료를 오름차순이나 내림차순으로 나열하는 것
- 정렬의 대상 : 레코드(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)으로 근사하여 나타낼 수 있음
- 최선의 경우 : 피봇에 의해 원소들이 왼쪽 부분집합과 오른쪽 부분집합으로 정확히 n/2개씩 2등분이 되는 경우가 반복되어 수행 단계 수가 최소가 되는 경우
힙 정렬(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)
- For 루프를 k번 반복
- 주민등록번호, 계좌번호 등 대량의 숫자를 기반으로 하는 상용 데이터베이스에서의 정렬에 유용함
'Study Note > 알고리즘' 카테고리의 다른 글
[알고리즘] 점화식과 수열 알고리즘 (0) | 2020.09.27 |
---|---|
[알고리즘] 복잡도와 점근적 표기법(빅오 표기법, 빅오메가 표기법, 세타 표기법) (0) | 2020.09.27 |
Comments