정렬 알고리즘

알고리즘을 조금씩 공부해나가야 할 것 같아 인강을 듣는다. Bubble Sort 부터 하루 하나씩 개념 익히기 도전.

Bubble Sort(거품정렬)란?

• 두 개의 인접한 원소를 비교해서 정렬하는 알고리즘이다.
  • 가장 대표적으로는 배열 속 숫자를 오름차순으로 정렬시키는 것
• 논리는 굉장히 단순하지만 시간복잡도는 O(n²)으로 엄청나게 효율적이진 않다.
• 정렬될 원소가 거품처럼 하나하나 타고 올라가서 붙여진 이름이라고 한다.

배열 속 정수 오름차순 정렬하기로 보는 Bubble Sort 구현

중첩된 for문

1
2
3
4
5
6
7

arr = [ 3, 6, 1, 2, 4, 23, 4214 ]

for i in range(len(arr)-1):
    for j in range(len(arr)-i-1):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = a[j+1], a[j]
    return arr

• n개의 정수가 담긴 배열에 대해, 작은 수부터 앞에 오도록 정렬해보자
• 앞에서부터 두개씩 크기를 비교하고 앞의 숫자가 크면 뒤의 숫자와 바꿔주는 연산을 n-1번 수행한다.
  • 최대값이 이동하여 가장 뒷자리로 간다. 하지만 그 앞의 값들은 여전히 정렬되지 않은 상태이다.
• 동일한 연산을 앞에서부터 n-2번 수행한다. 가장 뒷자리는 이미 최대값이므로 비교하지 않아도 된다.
  • 이제 가장 뒤쪽에서 두개는 정렬된 최대값 2개이다. 하지만 앞에서부터 n-2개 값은 여전히 정렬되지 않은 상태.
• 이런식으로 비교하고 바꾸는 작업을 첫번째는 n-1번, 두번째는 n-2번, 세번째는 n-3번 … n-1번째는 1번 수행한다.
  • 중첩된 for문: outer for문의 전체 range는 (n-1)번, inner for문의 range는 (n-index(outer for문이 몇번째 돌고있는지)-1)이다.

정렬된 상황에 대해 break하기

• 정렬이 완료되면 inner for문을 돌며 한 번도 교체작업이 일어나지 않는다. 그러면 굳이 나머지 for문을 돌릴 필요가 없다.
• outer for문에 swap이라는 변수를 0으로 초기화해둔다.
• 교체작업이 일어날 때마다 swap 이라는 변수에 교체작업의 횟수를 기록하고, 이 횟수가 0일 경우 그냥 for문을 break 한다.

1
2
3
4
5
6
7
8
9
10
11

arr = [ 3, 6, 1, 2, 4, 23, 4214 ]

for i in range(len(arr)-1):
    swap = 0
    for j in range(len(arr)-i-1):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = a[j+1], a[j]
            swap += 1
    if swap == 0:
        break
    return arr

Bubble Sort의 시간복잡도

• n-1번 도는 for문이 중첩되어 있어서 O(n²)의 시간복잡도를 갖는다.
• 그러나 이미 정렬되어 있는 경우, 첫 순회 후 break 되므로 O(n)까지도 줄어든다.

느낀 점

• 기억도 나지 않는데 이 정렬문제를 해커랭크에서 풀고 블로그에도 기록하기까지 했다.
• 당시에는 왜 교체한 횟수가 0일 때 break를 썼는지 궁금해했는데, 의문이 풀렸다.

참고자료

• 위키백과 거품정렬
• 내 블로그의 해커랭크 sorting 문제풀이