Bubble sort

iissaacc·2022년 1월 19일
1

Prologue

Sorting을 공부하다보면 어떤 상황에서는 뭘써야 하는지 알게되면서 더 큰 알고리즘을 만들 때 도움이 될 거라고 기대하면서 몇가지를 정리하려고 한다. 그래서 우리가 알아야 하는 것은 크게 3가지다.

  1. 알고리즘
  2. 구현
  3. best and worst case

그리고 이건 앞으로 우리가 정렬할 array다.

Building block

bubble sort는 index를 한 칸씩 옮기면서 이웃하는 두 수를 비교해서 오른쪽에 작은 수가 있으면 자리를 바꾼다.

두 수를 골라서 비교한다.

4가 1보다 크므로 두 수의 자리를 바꾼다. 이 작업을 sorting이 끝날 때까지 반복한다. 그러면 array에 있는 모든 수를 한 번 훑는 과정을 시각적으로 보자.

Think visually

오른쪽에 있는 수가 크니까 그대로 둔다.

이제 배열에 있는 모든 수를 한 번 비교했다. 그러면 가장 오른쪽에는 반드시 array에서 가장 큰수가 자리하게 되므로 더이상 나머지 숫자들과 비교할 필요없게 된다.

그러므로 두번째 비교가 시작할 때는 array의 마지막 index를 1씩 줄여준다.

Pseudo code

1. 정렬이 끝날 때까지
2. 0번 index부터 마지막 index안에서
3. 이웃하는 두 수 선택
4. n번째 수보다 n+1번째 수가 크면
4-1. 두 수의 index를 교환
5. 2번 loop 종료
6. 마지막 인덱스에 도달하면 마지막 인덱스를 1만큼 감소

Implementation

def bubble_sort(array):
    not_sorted = True
    length = len(array)       # 인덱스 수
    while not_sorted:         # 정렬할 때까지
        not_sorted = False
        for i in range(length-1):
            if array[i] > array[i+1]:      # 이웃하는 두 수를 비교
                array[i], array[i+1] = array[i+1], array[i]    # 두 수의 위치를 swap
                not_sorted = True                             # 조건문에 들어왔으면 정렬이 되지 않았다
        length -= 1  # 인덱스 수 1만큼 감소

    return array

Best and worst case

array의 수가 n개만큼 있을 때 모든 수를 얼마나 비교하는지 생각해보면 첫번째 loop에서는 n1n-1만큼, 두번째 loop에서는 n2n-2만큼 비교한다. 정렬이 끝났을 때는 n(n1)/2n(n-1)/2번 비교한다.

  • Best case: 제대로 정렬되어 있는 array
    비교만 n(n1)/2n(n-1)/2번 일어난다.

  • Worst case: 역순으로 정렬되어 있는 array
    비교할 때마다 교환이 일어나므로 시행횟수는 n(n1)n(n-1)이다.

이러나 저러나 O(n2)O(n^2)이므로 가급적이면 안 쓰는 게 좋다.

Epilogue

sorting을 오랜만에 공부하는데 알고리즘을 확실히 모르니까 code가 자꾸 오류를 내서 이렇게 정리해놓는다. 알고리즘 전부를 리뷰하기는 어렵고 몇 가지를 리뷰할 건데 아마 quick sort, merge sort 즈음 가면 마칠 것 같다.

0개의 댓글