버블정렬 (Bubble Sort) - python

#마이 에디션
arr1 = [31, 53, 75, 42, 15, 64, 31]
print("[정렬되지 않은 배열]")
print(arr1)
print()

n = len(arr1)

for i in range(0, n):
    for j in range(0, n-i-1):
        if (arr1[j] > arr1[j+1]):
            arr1[j+1], arr1[j] = arr1[j], arr1[j+1]

print("[정렬 완료된 배열]")
print(arr1)
print()

#교수 에디션
arr2 = [86, 12, 54, 29, 65, 43, 23]
print("[정렬되지 않은 배열]")
print(arr2)
print()

n = len(arr2)

for i in range(1, n):
    for j in range(1, n):
        if arr2[j-1] > arr2[j]:
            arr2[j-1], arr2[j] = arr2[j], arr2[j-1]

print("[정렬 완료된 배열]")
print(arr2)
print()

#버블정렬 개선, TRUE 중간고사
arr3 = [86, 12, 54, 29, 65, 43, 23]
print("[정렬되지 않은 배열]")
print(arr3)
print()

n = len(arr3)

for i in range(n - 1, 0, -1):
    swap = False
    for j in range(i):
        if arr3[j] > arr3[j + 1]:
            arr3[j], arr3[j + 1] = arr3[j + 1], arr3[j]
            swap = True
    if not swap:
        break

print("[정렬 완료된 배열]")
print(arr3)

#마이 에디션과 교수 에디션은 별 차이 없음.

[정렬되지 않은 배열]
[31, 53, 75, 42, 15, 64, 31]

[정렬 완료된 배열]
[15, 31, 31, 42, 53, 64, 75]


[정렬되지 않은 배열]
[86, 12, 54, 29, 65, 43, 23]

[정렬 완료된 배열]
[12, 23, 29, 43, 54, 65, 86]


[정렬되지 않은 배열]
[86, 12, 54, 29, 65, 43, 23]

[정렬 완료된 배열]
[12, 23, 29, 43, 54, 65, 86]

개선 버전은 이전 비교에서 교환이 있었는지 True or False로 체크 하고 교환이 없었다면 반복을 끝내버린다.

더 효율적임.

 

1. 서로 이웃한 원소들을 비교하고 가장 큰 수를 오른쪽으로 계속 넘긴다.

2. 가장 큰 수는 자연스럽게 배열 마지막에 위치한다.

3. 처음으로 돌아와서 다시 반복한다.