4044 : 버블 정렬 교환 횟수
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 12
•통과: 6
•만든사람: suakii
문제 설명
버블 정렬(Bubble Sort) 알고리즘을 시뮬레이션합니다.
버블 정렬은 인접한 두 원소를 비교하여 순서가 맞지 않으면 교환하는 과정을 반복하는 정렬 방식입니다.
한 번의 순회(패스, Pass)를 진행하는 동안 교환이 한 번도 발생하지 않으면, 이미 정렬이 완료된 것으로 판단하여 즉시 정렬을 종료합니다.
주어진 정수 배열이 완전히 정렬될 때까지 수행한 총 교환 횟수와 총 패스 수를 출력하는 프로그램을 작성하세요.
[제약 조건]
• $2 \le N \le 20$
• $-1000 \le (\text{각 정수}) \le 1000$
• 입력되는 모든 값은 정수
버블 정렬은 인접한 두 원소를 비교하여 순서가 맞지 않으면 교환하는 과정을 반복하는 정렬 방식입니다.
한 번의 순회(패스, Pass)를 진행하는 동안 교환이 한 번도 발생하지 않으면, 이미 정렬이 완료된 것으로 판단하여 즉시 정렬을 종료합니다.
주어진 정수 배열이 완전히 정렬될 때까지 수행한 총 교환 횟수와 총 패스 수를 출력하는 프로그램을 작성하세요.
[제약 조건]
• $2 \le N \le 20$
• $-1000 \le (\text{각 정수}) \le 1000$
• 입력되는 모든 값은 정수
입력 설명
첫째 줄에 정수의 개수 $N$이 주어집니다.
둘째 줄에 정렬할 $N$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 정렬할 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
정렬이 완료될 때까지의 총 교환 횟수와 패스 수를 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2 3 4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0 1도움
버블 정렬 의사코드:
pass_count = 0
total_swap = 0
while True:
pass_count += 1
swapped = 0
for i in range(0, n - 1):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped += 1
total_swap += 1
if swapped == 0:
break
print(total_swap, pass_count)