[파이썬] 백준 23969 알고리즘 수업 버블 정렬 2

백준 23969 알고리즘 수업 - 버블 정렬 2

백준 23969 버블 정렬

☞ 백준 사이트: https://www.acmicpc.net/problem/23969

버블정렬 로직

배열의 두 수(a, b)를 비교하면서 정렬시킴. 이를 반복

▷ [7, 2, 0, 1, 5, 6, 4] 정렬 예시

1. [7, 2, 0, 1, 5, 6, 4] 0번 index 7,2 비교 swap
2. [2, 7, 0, 1, 5, 6, 4] 1번 index 7,0 비교 swap
3. [2, 0, 7, 1, 5, 6, 4] 2번 index 7,1 비교 swap
4. [2, 0, 1, 7, 5, 6, 4] 3번 index 7,5 비교 swap
5. [2, 0, 1, 5, 7, 6, 4] 4번 index 7,6 비교 swap
6. [2, 0, 1, 5, 6, 7, 4] 5번 index 7,4 비교 swap
7. [2, 0, 1, 5, 6, 4, 7] 0번 index 2,0 비교 swap
8. [0, 2, 1, 5, 6, 4, 7] 1번 index 2,1 비교 swap
9. [0, 1, 2, 5, 6, 4, 7] 2번 index 2,5 비교 pass, 3번 index 5,6 비교 pass, 4번 index 6,4 비교 swap
10. [0, 1, 2, 5, 4, 6, 7] 0번 index 0,1 비교 pass, 1번 index 1,2 비교 pass, 2번 index 2,5 비교 pass, 3번 index 5,4 비교 swap
11. [0, 1, 2, 4, 5, 6, 7] 정렬

▶ 버블 정렬의 정의 및 다른 버블정렬 문제풀이는 이전 글 참고

[파이썬] 백준 23968 알고리즘 수업 버블 정렬 1

풀이

1. 배열의 끝부터 반복한다.
2. 배열의 처음부터 i-1 번째까지 반복한다.
3. 배열의 처음과 다음 값을 비교하여 오름차순 안되어있으면 swap 한다.
4. 교환 횟수 count 한다.
5. K번 교환이 발생한 직후의 배열 A를 한 줄에 출력한다.
6. 교환 횟수가 K보다 작으면 -1 출력한다.

import sys
#배열 A의 크기 N, 교환횟수 K 입력받는다.
N, K = list(map(int, sys.stdin.readline().rsplit()))
#배열 A의 원소들을 입력받는다.
A = list(map(int, sys.stdin.readline().rsplit()))

def bubble_sort(lst,K):
    cnt = 0
    #1.배열의 끝부터 반복한다.
    for i in range(len(lst), 0, -1):
        #2.배열의 처음부터 i-1 번째까지 반복한다.
        for j in range(0, i-1):
            #3.배열의 처음과 다음 값을 비교하여 오름차순 안되어있으면 swap 한다.
            if lst[j] > lst[j+1]:
                #4.교환횟수 count 한다.
                cnt += 1
                #리스트 값 스왑
                lst[j], lst[j+1] = lst[j+1], lst[j] 
                #5.K번 교환이 발생한 직후의 배열 A를 한 줄에 출력한다.
                if cnt == K:
                    return(print(*lst, sep=" ", end=""))
    #6.교환횟수가 K보다 작으면 -1 출력한다.
    return(print(-1))

bubble_sort(A,K)
"""
6 10
4 6 5 1 3 2
1 3 2 4 5 6
"""