선택트리/loser,sinner차이[ ]
2-Phase(두 단계)**라는 말은 **"정렬 1단계 + 합병 1단계"**를 통틀어서 하는 말입니다.
(런의 갯수(전체 레코드/m )!= 한번에 합칠수있는 갯수( m/b )
(런의 갯수(전체 레코드/m ) <= 한번에 합칠수있는 갯수( m/b )
(그래야 한번의 병합으로)
이거를 이항한게 f<=m(m/b-1)
2-Phase Multiway Merge Sort의 성능을 개선할 수 있는 방법을 2가지 이상 소개하라.
Polyphase Sort/Merge[ 패스 ]
2PMM 과정 [ ]
(f/m+1)b<=m
f<=m(m/b-1)
k-sort(한번에 몇개 동시에 합칠건지)
2pmm : 로그에서 진수=밑이라서 1이됫음
낱개 데이터(레코드)
f/m+1 :갯수를 두배 해야하는거네
(m자체를 변경하면 안되고)
100중 10개를 모을때, 남은게 90개가 되는게 아니라 10개 즉, log k가 되는것과 비슷한가
왜4번인지:아무튼 정렬 병합단계가 있어서
ㅇㅇ
1
성능개선(3) 부분 구현 [ ] 매개변수 순서만 주의
(merge만 순서 반대네 )
2
merge 함수 내부에서 비교 연산을 수행할 때, 현재 데이터를 가져오는 소스(Source)는 aux 배열입니다. 따라서 less 함수에 a가 아닌 aux 배열의 요소를 전달해야 합니다.
- 기존 코드: else if(less(a[j], a[i]))
- 수정 코드: else if(less(aux[j], aux[i]))
2pmm,바이너리 정렬 차이
sort안에 있는 sort재귀() sort재귀() merge를 호출하는건데,
그 이 재귀들에도 각각 sort있으니깐 ?
'레코드(Record)'가 뭔가요?
데이터베이스나 파일에서 **'한 줄의 데이터'**를 말합니다.
- 예시: 엑셀 시트에서 한 행(Row) 전체라고 생각하면 쉽습니다.
- [학번: 202401, 이름: 홍길동, 전공: 컴공] 이게 하나의 레코드입니다.
- "레코드의 수가 많을 경우" = "정렬해야 할 데이터가 수백만, 수억 줄이나 될 정도로 엄청나게 많을 경우"라는 뜻입니다.
배열에 대한 액세스 >디스크에 대한 액세스? 의미
b<m이니깐
작은게 밑에 와야지 양수가 되어야하니깐
loser인지 winner인지에 따라 다르긴하겟지만
(아, 입력, 출력이 그뜻이었구나)
'26년1학기 > 알고리즘' 카테고리의 다른 글
| 알고리즘 )1주차 퀴즈 준비( 26.3.22) (1) | 2026.03.22 |
|---|---|
| 알고리즘 )1주차 퀴즈 준비_코드( 26.3.21) (0) | 2026.03.21 |
| 알고리즘 )1주차 이론 etc..( 26.3.20) (0) | 2026.03.20 |
| 알고리즘 )1주차 퀴즈 준비_코드( 26.3.20) (0) | 2026.03.20 |
| 알고리즘 ) 과제( 26.3.20) (2) | 2026.03.20 |