버블 정렬(Bubble Sort)

두 인접한 요소를 비교하여 정렬하는 방식!!

제일 단순!! but, 느림

array = [45, 7, 12, 82, 25]
print(f"정렬 전 : {array}")
# 오름차순 : 왼쪽 요소가 오른쪽 요소보다 크면 치환!!
for j in range(4):
    for i in range(4 - j):
        if array[i] > array[i + 1]:
            temp = array[i]
            array[i] = array[i + 1]
            array[i + 1] = temp
    print(f"step{j + 1} : {array}")

정렬 전 : [45, 7, 12, 82, 25] step1 : [7, 12, 45, 25, 82] step2 : [7, 12, 25, 45, 82] step3 : [7, 12, 25, 45, 82] step4 : [7, 12, 25, 45, 82]

# 치환(swap)
a, b = 10, 20
print(f"치환 전 : {a, b}")

# 치환 Logic
temp = a
a = b
b = temp
print(f"치환 후 : {a, b}")

치환 전 : (10, 20) 치환 후 : (20, 10)

test = [9, 5, 7, 1, 3]
# test를 bubble sort로 내림차순 정렬!!

print(f"정렬 전 : {test}")
# step1
# 4번의 비교 : 요소가 5개니까

# step은 4개까지 : 왜? 요소가 5개니까
for j in range(4, 0 , -1):
    for i in range(4):
        if test[i] < test[i + 1]:
            temp = test[i]
            test[i] = test[i + 1]
            test[i + 1] = temp
    print(f"step{5 - j} : {test}")

정렬 전 : [9, 5, 7, 1, 3] step1 : [9, 7, 5, 3, 1] step2 : [9, 7, 5, 3, 1] step3 : [9, 7, 5, 3, 1] step4 : [9, 7, 5, 3, 1]

# 치환 : 메모리 리소스
# 요소가 n개라면
# 치환이 최대 n-1, ... , 1 -> n^2
# 시간복잡도 -> 2중 for문 -> O(n^2)
# 10개 정렬 1초 -> 100개 정렬 -> 100초

선택 정렬(Selection Sort)

가장 큰 요소의 위치를 기억 후

가장 오른쪽과 치환하면서 정렬

arr = [98, 7, 70, 13, 24]
print(f"정렬 전 : {arr}")

# 오름차순 : 가장 큰 요소의 위치를 바탕으로 가장 오른쪽 값과 치환
for j in range(5, 1, -1):
    max_index = 0
    for i in range(j):
        if arr[i] > arr[max_index]:
            max_index = i

    # print(f"step1의 max_index : {max_index}")
    # max_index의 요소와 가장 오른쪽 값을 치환
    temp = arr[max_index]
    arr[max_index] = arr[j - 1]
    arr[j - 1] = temp
    print(f"step1 : {arr}")

정렬 전 : [1, 2, 3, 4, 5] step1 : [1, 2, 3, 4, 5] step1 : [1, 2, 3, 4, 5] step1 : [1, 2, 3, 4, 5] step1 : [1, 2, 3, 4, 5]

# 선택정렬을 활용하여 내림차순 정렬!!
exam = [9, 5, 7, 1, 3]
# 1) 가장 작은 위치 정보 <-> 가장 오른쪽 
# 2) 가장 큰 위치 정보 <-> 가장 왼쪽
for j in range(5, 1, -1):
    min_index = 0
    for i in range(j):
        if exam[i] < exam[min_index]:
            min_index = i
    temp = exam[min_index]
    exam[min_index] = exam[j - 1]
    exam[j - 1] = temp
print(exam)

[5, 4, 3, 2, 1]

# 선택정렬을 활용하여 내림차순 정렬!!
exam = [9, 5, 7, 1, 3]
# 2) 가장 큰 위치 정보 <-> 가장 왼쪽
for j in range(4):
    max_index = -1
    for i in range(j, 5):
        if exam[i] > exam[max_index]:
            max_index = i
    temp = exam[max_index]
    exam[max_index] = exam[j]
    exam[j] = temp

print(exam)