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

백준 23968 알고리즘 수업 - 버블 정렬 1 문제 풀이

백준 23968

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

 

버블정렬이란

• 배열의 두 수(a, b)를 선택한 뒤, 두 수를 비교하여 정렬이 필요하면 swap, 아니면 pass 한다.
• 위 작업을 계속 반복하는 것이 버블정렬이다.
• 시간복잡도 O(n2)로 상당히 느린 반면, 코드가 단순하기 때문에 자주 사용된다.

▶ 오름차순 정렬이면 a < b 판단하여 정렬

▶ 내림차순 정렬이면 a > b 판단하여 정렬

 

[ 4, 6, 5, 1, 3, 2] 정렬 대상 리스트인 경우 정렬 순서,

1. [ 4, 6, 5, 1, 3, 2] 4,6 은 정렬, 6,5는 미정렬 → 1번 index 6, 5 swap
2. [ 4, 5, 6, 1, 3, 2] 2번 index 6, 1 swap
3. [ 4, 5, 1, 6, 3, 2] 3번 index 6, 3 swap
4. [ 4, 5, 1, 3, 6, 2] 4번 index 6, 2 swap
5. [ 4, 5, 1, 3, 2, 6] 0번 index 4, 5는 정렬 → 1번 index 5, 1 swap
6. [ 4, 1, 5, 3, 2, 6] 2번 index 5, 3 swap
7. [ 4, 1, 3, 5, 2, 6] 3번 index 5, 2 swap
8. [ 4, 1, 3, 2, 5, 6] 4번 index 5, 6 정렬상태 pass → 0번 index 4, 1 swap
9. [ 1, 4, 3, 2, 5, 6] 1번 index 4, 3 swap
10. [ 1, 3, 4, 2, 5, 6] 2번 index 4, 2 swap, 나머지 정렬상태 pass
11. [ 1, 3, 2, 4, 5, 6] 1번 index 3, 2 swap, 나머지 정렬상태 pass
12. [ 1, 2, 3, 4, 5, 6] 전체 정렬상태 pass

풀이

문제에 있는 알고리즘을 파이썬에 맞게 작성한다.

1. 배열의 끝부터 반복한다. 반복변수 i
2. 배열의 처음부터 i-1 번째까지 반복한다.
3. 배열의 처음과 다음 값을 비교하여 오름차순 안되어있으면 swap 한다.
4. swap 시 교환횟수 count 한다.
5. 교환 횟수가 K와 같으면 출력한다.
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와 같으면 출력한다.
                if cnt == K:
                    return(print(lst[j], lst[j+1]))
    #6.교환횟수가 K보다 작으면 -1 출력한다.
    return(print(-1))

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