이 실험 소개
버블 정렬, 삽입 정렬, 병합 정렬이 동일한 입력을 오름차순으로 변환하는 과정을 살펴보세요. 비교 지점에서 일시 정지하거나, 쓰기를 하나씩 진행하거나, 전체 추적을 거꾸로 이동할 수 있습니다. 값 비교 횟수와 주 배열 쓰기 횟수를 따로 집계하면 알고리즘의 작업량과 애니메이션 재생 시간을 구분할 수 있습니다.
학습 목표
- 세 가지 비교 정렬 알고리즘의 비교 및 쓰기 추적
- 무작위로 섞인 입력, 정렬된 입력, 역순 입력에서 성능 비교
- 최악의 경우의 이차 증가와 n log n 증가 구분하기
사용 방법
- 1무작위로 섞인 입력과 배열 길이를 고정하세요. 버블 정렬을 끝까지 실행하고 비교 횟수와 쓰기 횟수를 기록하세요.
- 2같은 입력으로 삽입 정렬을 실행한 뒤, 병합 정렬을 다시 시작해 실행하세요. 최종 횟수를 비교하세요.
- 3정렬된 입력을 사용해 버블 정렬의 조기 종료와 삽입 정렬의 적은 비교 횟수를 확인하세요.
- 4Previous와 추적 슬라이더를 사용해 병합 과정을 살펴보세요. 임시 버퍼에는 원래 메인 배열의 위치에서 더 이상 보이지 않는 값이 저장될 수 있습니다.
모델
가정
- 입력에는 1부터 n까지의 중복되지 않는 정수가 포함됩니다. 셔플에는 고정 시드를 사용하므로 모든 알고리즘이 동일한 데이터를 받습니다.
- 비교란 인덱스나 반복문의 경계값이 아니라 데이터 값끼리 비교하는 것입니다. 쓰기란 변경되지 않은 삽입 키를 포함해 메인 배열에 값을 할당하는 것을 말합니다.
- 병합 정렬의 임시 버퍼 복사는 쓰기 횟수에서 제외됩니다. 추가 메모리 사용량도 표시된 연산 합계에 포함되지 않습니다.
- 재생 속도는 학습을 위해 설정된 것이며 실제 시간 기준의 성능 벤치마크가 아닙니다.
수업에서 해 보기
- Q1이 구현에서 입력이 이미 정렬되어 있으면 버블 정렬의 비교 횟수가 왜 n − 1회뿐인가요?
- Q2배열 길이가 같을 때 역순 입력에서 비교 횟수가 더 적은 알고리즘은 무엇인가요?
- Q3애니메이션 프레임 수가 알고리즘 속도를 측정하는 신뢰할 수 있는 기준이 아닌 이유는 무엇인가요?
자주 묻는 질문
삽입 정렬이나 병합 정렬 중에 값이 잠시 중복되어 표시되는 이유는 무엇인가요?
주 배열을 덮어쓰는 동안 값이 임시 키나 병합 버퍼에 보관될 수 있습니다. 시각화에는 값을 쓸 때마다 주 배열의 내용이 표시되며, 작업이 완료되면 중복이 해소됩니다.
병합 정렬은 항상 쓰기 횟수가 더 적나요?
아니요. 병합 정렬은 비교 횟수의 증가를 효율적으로 억제하지만, 병합한 결과를 반복해서 다시 씁니다. 연산 횟수는 입력 데이터와 어떤 대입을 세는지에 따라 달라집니다.