버블정렬 - 스터디-

무엇인가?

순서 없이 정렬된 리스트를 하나하나 비교해가며 순서대로 정렬하는 기법이다. (오름 차순으로 정렬하는걸 정리함)

공부 방법

노트에 직접 상황들을 적어가며 공부함 길이가 긴 리스트여도 흐름을 파악할때까지 리스트의 길이를 늘림
다행히 길이가 4까지만 해도 이해가 되었다.

생각한 내용 적어보기

처음 생각한대로 내용 적고 코딩한 결과

list1 = [5, 3, 4, 1, 2]
for i in range(len(list1)):
  for j in range(len(list1)-1):
    if list1[j] > list1[j+1]:
      list1[j+1], list1[j] = list1[j], list1[j+1]

print(list1)

첫 for문에서 list1의 길이를 체크해서 그 횟수만큼 돌고 j가 포함되어있는 for문에서 리스트의 길이 -1을 하면 문제 없이 돌지 않을까? -1을 한 경우는 어짜피 정렬이고 순서대로 정렬하는 문제이면 뒤의 수(list1[j+1])를 써야하기때문에 마지막 길이까지 갔을땐 그 뒤의 수가 없기때문이라 -1을 해줘야한다고 생각했다.

일단, 정렬은 잘 되어 결과가 문제 없이 나온다.

하지만, 과정을 보면 순회가 필요없는곳 까지 순회를 해버려서 코드의 효율성이 현저히 떨어지는걸 볼 수 있다.

# 과정
list1 = [5, 4, 3, 2]
for i in range(len(list1)):  # 현재 list1의 길이는 4이다.
  for j in range(len(list1)-1):  # list1의 길이 4 그리고 -1 을 하면 3이다. index 0, 1, 2 이렇게 3번 순회 한다는 소리다.
    # i = 0
    ## j = 0 / j + 1 = 1
    ## j = 1 / j + 1 = 2
    ## j = 2 / j + 1 = 3.  ->   list1 max 길이인 3번째 index까지 돌았다.
    # i = 1
    ## j = 0 / j + 1 = 1
    ## j = 1 / j + 1 = 2
    ## j = 2 / j + 1 = 3.  ->  이렇게 또 list1의 max 길이인 3번째 index까지 돌았다.
    # 더이상 과정을 적어보지 않아도 계속 이렇게 될것이란걸 예상 할 수 있을것이다.

이렇게 효율성이 떨어지는걸 사용할 수 없으니깐 조치를 취해야한다.

그래서 내린 결론은

list1 = [5, 3, 4, 1, 2]
for i in range(len(list1)-1):  # -1이 추가되었다.
  for j in range(len(list1)-i-1):  # -i 가 추가 되었다.
    if list1[j] > list1[j+1]:
      list1[j+1], list1[j] = list1[j], list1[j+1]

print(list1)

위 코드를 보면 첫번째 for문에 길이가 -1 추가 되었고 두번째 for문에 -i가 추가되었는데
첫번째 for문에 -1을 안하고(for i in range(len(list1))) 그냥 길이가 4인채 두번째 for문으로 넘기게 되면 길이 연산(range(len(list1)-i-1)) 에서 첫번째 for문의 수가 4로 내려올때 길이 연산을 하게되면 4-4-1이 된다.

이렇게 되면 -1인 인덱스 즉, 마지막 인덱스와 거기에 +1한 0번째 인덱스를 비교하게 된다.
물론 그렇게 비교를 할 순 있겠지만 버블 정렬 형식에 맞지 않기에 사용하지 않기로 한다. 이러한 과정을 겪었으므로 첫번째 for문에서 길이에 -1을 하게됨으로써 -1인 인덱스가 나오는 상황을 막을 수 있다.

그런데 몇가지 생각을 해보면 무조건 순서없이 정렬 되어있진 않을 것이다.

어떤건 리스트는 전부 제대로 정렬되어있다면 반복문 도는 자체가 효율성 Zero가 된다고 생각한다.

그래서 True/False를 사용해서 처음 for문을 돌았을때 swap된 상황이 있는지 없는지 판별 해주도록 한다.

def bubble_sort(array: list) -> list:
    for i in range(len(array) - 1):
        swap = False
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                array[j + 1], array[j] = array[j], array[j + 1]
                swap = True
        if not swap:
            break  # 한 번 돌았는데 swap이 False일때(처음 for문을 돌았는데 변경할게 없다) 바로 모든걸 멈추고 빠져나가도록 한다.

    return array


if __name__ == "__main__":
    list1 = [5, 3, 4, 1, 2]
    print(bubble_sort(list1))