정렬 Flashcards
정렬 알고리즘
[정의] 여러 원소로 구성된 데이터를 크기 순서에 따라 재배열하는 알고리즘
[유형]
<저장소>
- 내부정렬 : 주기억 장치에 저장 후 정렬
- 외부정렬 : 일부를 외부 기억장치에 저장
<정렬방식>
- 비교기반 정렬 : 선택, 버블, 합병, 퀵
- 분포기반 정렬 : 계수, 버킷, 기수
<동일값>
- Stable(안정적) 정렬 : 키값 동일 시 상대적 위치 미변경 (버블, 삽입, 합병)
- Unstatble 정렬 : 키값 동일 시 상대적 위치 변경 (퀵, 선택, 히프)
<별도>
- In-Place(제자리) 정렬 : 데이터 저장공간 외 상수개 별도 공간 필요
- Out-of-Place 정렬 : 중간 정보 저장 위해 입력 값 이상 공간 필요 (합병, 분포기반)
</별도></동일값></정렬방식></저장소>
외부정렬
[정의] 정렬 할 데이터의 크기가 주기억장소 용량보다 클 경우 외부 기억장치(메모리 외부), 디스크 장치파일을 직접 또는 순차적으로 접근하여 정렬하는 방법
[유형]
- (디스크)2원 병합정렬, m원 병합정렬
- (테이프) 균형 병합정렬, 다단계 병합 정렬, 계단식 병합 정렬, 교내식 병합정렬
삽입정렬
[정의] 첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법
* 미 정렬 원소와 기 정렬 자료 비교, 해당 위치에 삽입하여 정렬하는 기법
[특징]
- 레코드 이동이 많고, 비교적 크기가 작은 데이터 집합 정렬에 유리
- 안정된 정렬방법, 이미 정렬되어 있다면 효율적 : (n-1)
[정렬 메커니즘]
1. 추출 -> 이동 -> 삽입
* 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 과정을 수행
퀵정렬
[리드] 분할과 정복 방식 정렬
[정의] Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘
[특징] 재귀호출 구조, 정렬위한 별도 스택 필요
[정렬 매커니즘]
1. Pivot 설정 : 임의의 원소 선택, 대체로 좌측 첫번째 원소 선택
2. 원소교환, 분할 : 좌→우 (Pivot보다 크거나 같은 값 탐색), 우→좌(Pivot보다 작은 값 탐색) -> 교환
3. 분할 : 좌/우 index가 겹치거나 역전되면 Pivot과 역전된 오른쪽 값 교환 후 분할
3. 재귀적 반복(분할된 집합 크기가 1이 될때까지 반복)
4. 종료
[시간복잡도] 평균 O(NlogN), 최악의 경우 O(N^2)
버블정렬
[정의] 인접한 2개의 값을 비교하여 크기가 순서대로 되어있지 않으면 값을 서로 교환하여 끝까지 진행하는 알고리즘
[특징] 평균 O(N^2), 매우 간단하나 비효율적, 안정적, 제자리 정렬(상호 교환)
[정렬 매커니즘]
1. 좌측 혹은 우측부터 인접 원소 크기 비교
2. 크기 비교 후 교환
3. 한칸씩 이동후 1,2 반복 수행
* 정렬 여부와 상관없이 모든 원소를 비교, Flag 활용을 통해 성능 향상 가능
[차별화]
- flag를 두어 불필요한 과정 생략 가능(성능 향상), flag=0인 경우 완료
- flag 사용시 O(n) 성능 가능
선택정렬
[정의] 정렬이 안된 숫자들 중에서 최소 값을 선택하여 배열의 첫 번째 요소와 교환하는 정렬 기법
[시간복잡도] 최악의 경우 O(N^2)
[특징] 배열이 길수록 비효율, 구현 용이
[정렬 매커니즘]
1. 가장 작은 값을 찾아 기준위치인 첫번째 배열과 자리 교환
2. 첫번째는 제외하고 가장 작은 값을 찾아 기준 위치인 두번째 배열과 자리교환
3. 반복
병합정렬
[정의] 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식
[시간복잡도] O(NlogN) [공간복잡도] O(N)
[특징] 퀵정렬에 비해 느림, 최악의 경우 O(N^2)
[정렬 매커니즘]
- 분할(n/2개씩 두개의 부분순열 분리), 정복(정렬하면서 병합), 결합(정복을 반복)
힙정렬
[정의] 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
[시간복잡도] O(NlogN) [공간복잡도] O(1)
[정렬 매커니즘]
1. 완전 이진 트리를 구성
2. 최대 힙 구성
3. 삭제 연산후 최대 힙 구성
4. 연속 개수만큼 반복
버킷정렬
키값 범위 버킷 생성
버킷별 원소 정렬
전체 버킷 원소 정렬
기수정렬
[정의] 낮은 자릿수부터 비교하여 정렬하는 정렬 알고리즘
[시간복잡도] O(dn) (d는 가장 큰 데이터의 자리수)
[특징]
- 버킷 사용, 비교연산 불필요, FIFO 구조
- 숫자를 정렬하기 위해서는 10개, 영문자이면 26개의 버킷 영역 필요
[정렬 매커니즘] 1. 버킷 준비(숫자10, 영문자 26) 2.1자리수부터 일치하는 버킷에 순차적으로 대입 3.버킷 순서대로 추출 4.자릿수를 높여가며 반복
계수정렬
[정의] 원소간 비교하지 않고 각 원소가 몇 개 있는지 갯수를 세서 정렬하는 방법
[특징] 정수나 정수로 표현할 수 있는 자료에 대해서 동작, 집합 내의 가장 큰 정수를 알고 있어야 함
