버블 정렬
이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
가장 짧은 시간을 먼저 배치하세요
- 세 명의 경기 시간이 배열에 있습니다:
14,9,11. 가장 작은 값이 먼저 와야 합니다. - 인접한 쌍(neighbours)을 각각 비교하십시오. 왼쪽 값이 크면 서로바꿔 swap하십시오.
- 단일 비교로 목록이 완성되지 않습니다. 다음 쌍이 비교됩니다.
English
DECLARE Score : ARRAY[1:3] OF INTEGER
DECLARE J, Temp : INTEGER
Score[1] ← 14
Score[2] ← 9
Score[3] ← 11
FOR J ← 1 TO 2
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
반복적인 pass
- 안쪽 루프의 한 pass는 보이스업(bubble up)하여 보아온 가장 큰 값을 끝으로 이동시킵니다.
- 바깥쪽 루프는 pass를 반복합니다. 네 개의 값이라면 세 번의 pass면 충분합니다.
- 이는 교재 과정의 버블 정렬(bubble sort)입니다. 앞서 작성한 선형 탐색(linear search)은 단순히 바라보기만 하지만, 정렬(sort)은 재배열합니다.
English
DECLARE Score : ARRAY[1:4] OF INTEGER
DECLARE I, J, Temp : INTEGER
Score[1] ← 4
Score[2] ← 1
Score[3] ← 3
Score[4] ← 2
FOR I ← 1 TO 3
FOR J ← 1 TO 3
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
NEXT I
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
OUTPUT Score[4]
주의사항
Temp변수와 교체합니다.Score[J] ← Score[J + 1]만으로는 왼쪽 값을 삭제할 수 없습니다.- 안쪽의 **
NEXT**는 **J**이라는 이름을 가집니다. 바깥쪽의 **NEXT**은 **I**이라는 이름을 가집니다.
아무것도 스왑되지 않으면 멈춥니다
- 수정된 버전은 이미 정렬된 목록이라도 모든 반복을 반드시 수행합니다.
BOOLEAN플래그인Swap가 반복 중 어떤 스왑도 있었는지 기억합니다. 스왑이 없으면 목록이 정렬되었으므로 루프가 멈춥니다.- 각 반복 후 가장 큰 값이 제자리에 놓이므로
Last이 하나씩 줄어듭니다.
DECLARE Score : ARRAY[1:5] OF INTEGER
DECLARE J, Last, Temp : INTEGER
DECLARE Swap : BOOLEAN
Score[1] ← 2
Score[2] ← 1
Score[3] ← 3
Score[4] ← 4
Score[5] ← 5
Last ← 4
REPEAT
Swap ← FALSE
FOR J ← 1 TO Last
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
Swap ← TRUE
ENDIF
NEXT J
Last ← Last - 1
UNTIL NOT Swap OR Last = 0
FOR J ← 1 TO 5
OUTPUT Score[J]
NEXT J
여기서 첫 번째 반복에서 2과 1가 스왑되고, 두 번째 반복에서는 스왑이 없으므로 네 번의 반복 대신 두 번으로 정렬이 멈니다.
흔한 실수
- 테스트가 "왼쪽이 크다"라면 작은 값이 왼쪽으로 이동합니다. 반대 방향으로 하면 역순(reverse order) 정렬이 됩니다.
- 이 과정에서 배열은 1부터 시작합니다. 마지막 쌍은 끝 바로 앞 셀과 마지막 셀입니다.
- 4-셀 배열에서
FOR J ← 1 TO 4를 읽으면, 존재하지 않는Score[5]를 읽습니다. 내부 루프는 끝점보다 하나 앞까지만 실행됩니다. REPEAT이전, 한 번만Swap ← FALSE를 설정합니다. 매 passes 시작 시 반드시 재설정해야 합니다.
이제 직접 해보기
- 첫 번째 과제는 한 번의 반복입니다. 두 번째는 전체 정렬입니다. 세 번째는 다섯 가지 값을 읽고
Swap플래그와 함께 내림차순으로 정렬한 뒤, 각 값을 줄마다 출력합니다. - 답안 확인을 눌러 테스트해 보십시오.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
배열 Score에는 14, 9, 11이 들어 있습니다. 한 번의 반복만 수행하여 왼쪽 값이 클 경우 이웃과 위치를 바꿉니다. 세 값을 각각 한 줄씩 출력합니다(9, 이후 11, 이후 14).
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
배열 Score은 4, 1, 3, 2을 포함합니다. 이를 오름차순으로 버블-정렬하여 네 값을 줄마다 출력하십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
정수 5개를 Score : ARRAY[1:5] OF INTEGER에 읽어들이십시오. 버블 정렬을 사용하여 내림차순으로 정리하되, 한 번의 pass에서 스왑이 이루어지지 않으면 BOOLEAN 플래그 Swap으로 정렬을 멈추십시오. 5개의 값을 각 줄마다 하나씩 출력하십시오.
출력을 보려면 '실행'을 클릭하세요.