- 비교 중
- 교환됨
- 제자리
버블 정렬
버블 정렬은 목록을 거듭 훑으며 이웃한 두 값을 비교하고, 왼쪽 값이 더 크면 교환합니다. 패스가 끝날 때마다 아직 제자리에 있지 않은 가장 큰 값이 거품처럼 끝으로 떠오릅니다. 원하는 속도로 재생하거나 비교를 하나씩 진행하며 비교, 교환, 패스 카운터를 지켜보세요. ‘재생’을 눌러 정렬을 보거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 타일에는 비교, 교환, 패스 횟수가 표시됩니다. 막대 개수와 시작 순서를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.
작동 원리
- 막대 개수와 시작 순서를 고르세요: 무작위, 거의 정렬됨, 역순, 값 종류 적음. 직접 숫자를 입력해도 됩니다.
- ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 정렬의 원하는 지점으로 이동합니다.
- 타일에 표시되는 비교, 교환, 패스 횟수를 보고 최악의 경우와 비교해 보세요.
버블 정렬의 작동 방식
왼쪽에서 시작합니다. 처음 두 값을 비교해 왼쪽 값이 더 크면 교환합니다. 오른쪽으로 한 칸 옮겨 다시 비교하고, 목록 끝까지 반복합니다. 이것이 패스 한 번이며, 가장 큰 값이 마지막 자리에 놓입니다. 다음 패스는 한 칸 앞에서 멈춥니다. 교환이 없는 패스가 나오거나 값이 하나만 남을 때까지 계속합니다.
작업량 세기
값이 n개이면 첫 패스는 n − 1번, 다음 패스는 n − 2번 비교하는 식이므로 전체 정렬은 최대 n(n − 1)/2번 비교합니다. 교환 횟수는 항상 시작 목록의 역순쌍, 즉 순서가 잘못된 값 쌍의 개수와 같습니다. 역순 목록이 가장 많아 n(n − 1)/2개입니다. 정렬된 목록에는 역순쌍이 없고, 조기 종료를 켜면 n − 1번 비교하는 패스 한 번으로 끝납니다.
자주 묻는 질문
왜 버블 정렬이라고 하나요?
큰 값이 물속의 거품처럼 목록 끝으로 떠오르기 때문입니다. 각 패스에서 아직 제자리에 있지 않은 가장 큰 값이 한 칸씩 오른쪽으로 이동해 최종 위치에 도달합니다.
버블 정렬은 비교와 교환을 몇 번 하나요?
값이 n개이면 최대 n(n − 1)/2번 비교합니다. 10개면 45번, 40개면 780번입니다. 교환 횟수는 항상 시작 목록의 역순쌍 개수와 같으며, 정렬된 목록은 0번, 역순 목록은 n(n − 1)/2번입니다.
조기 종료는 무엇을 하나요?
패스 전체에서 교환이 없으면 이웃한 모든 쌍이 순서대로이므로 목록이 정렬된 것이고 정렬을 멈출 수 있습니다. 조기 종료를 켜면 정렬된 목록은 패스 한 번으로 끝납니다. 끄면 버블 정렬은 항상 n − 1번의 패스를 모두 수행합니다.
버블 정렬은 실제로 쓰이나요?
거의 쓰이지 않습니다. 단순한 안정 정렬이지만 평균적으로 n²에 비례하는 시간이 걸립니다. 짧거나 거의 정렬된 목록에서는 삽입 정렬이 같은 일을 더 적은 단계로 하고, 긴 목록에서는 병합 정렬이나 퀵 정렬이 훨씬 빠릅니다.
제 숫자가 어딘가로 전송되나요?
아니요. 정렬은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 저장됩니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동