[알고리즘] 버블 정렬

들어가기 전에…
알고리즘을 효과적으로 공부하는 방법은
문제를 읽고 바로 코드를 작성하는 것이 아니라!

1. 문제를 분석한 뒤에, 그 문제를 해결할 수 있는 알고리즘을 연습장에 충분히 고안한다.
2. 이 때, 가장 간단한 경우부터 복잡한 경우까지 순서대로 생각해본다.
3. 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.
4. 코드화하기 위해 데이터 구조 또는 사용할 변수를 정리하고, 각 문장을 코드 레벨로 적는다.
5. 데이터 구조 또는 사용할 변수가 코드에 따라 어떻게 변하는지를 손으로 적는다.
6. 에디터에 코드를 작성하는 것은 최종적으로 그 알고리즘이 많은 경우에서도 동작하는지 테스트 하기 위해서이다!

왜 이렇게 할까?
여러가지 경우의 수를 고려해서 효율적인 알고리즘을 먼저 고안하고, 코드로 작성해 테스트를 해야한다.
그렇지 않고 바로 코드로 작성하면 효율적인 알고리즘을 만들기가 어렵기 때문이다.

1. 정렬 (sorting) 이란?

• 정렬 (sorting): 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
• 정렬은 프로그램 작성시 빈번하게 필요로 함
• 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수

다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고,
각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있다

2. 버블정렬(bubble sort) 이란?

• 두 개의 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

(이 사이트에서 더 명확히 이해할 수 있을 것이다)

3. 어떻게 코드로 만들까?

데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
예: data_list = [5, 2, 3, 1]

• 첫 번째 턴
  - 5 와 2 비교, 자리바꿈 [2, 5, 3, 1]
  - 5 와 3 비교, 자리바꿈 [2, 3, 5, 1]
  - 5 와 1 비교, 자리바꿈 [2, 3, 1, 5]
• 두 번째 턴
  - 2 와 3 비교, 그대로 [2, 3, 1, 5]
  - 3 과 1 비교, 자리바꿈 [2, 1, 3, 5]
  - 3 와 5 비교, 그대로 [2, 1, 3, 5]
• 세 번째 턴
  - 2 과 1 비교, 자리바꿈 [1, 2, 3, 5]
  - 2 과 3 비교, 그대로 [1, 2, 3, 5]
  - 3 과 5 비교, 그대로 [1, 2, 3, 5]

위 예제를 그림으로 확인해보자

첫 번째 사진에서 (데이터길이, 비교, 턴) = (4,3,3) 이라는 패턴을 알 수 있다.
다른 예제도 해본다면 (2,1,1)과 (3,2,2)도 찾을 수 있기 때문에 패턴을 알 수 있다.
이를 대략적으로 글로 나타낸다면 두 번째 사진에 있는 것처럼 아래와 같이 나타낼 수 있다.

for i in range(데이터길이 - 1):
  for j in range(데이터길이 - 1):
    if 앞데이터 > 뒤데이터:
    swap(앞데이터, 뒤데이터)

이때 i는 각각의 “턴”을 의미하고, j는 한 턴에서의 “비교”를 의미한다.

그런데 매번 턴 마다 가장 큰 데이터가 맨 뒤로 이동하기 때문에, 가장 큰 데이터와 그 앞 데이터는 비교할 필요가 없다.
따라서 첫 번째 사진으로부터 두 번째 사진에 있는 것처럼 아래와 같이 코드를 최적화 할 수 있다.

for i in range(데이터길이 - 1):
  for j in range(데이터길이 - 1 - i): // 🌟 이 부분이 변경되었다!
    if 앞데이터 > 뒤데이터:
    swap(앞데이터, 뒤데이터)

여기서 한 번 더 최적화를 할 수 있을것이다.
예를 들어 데이터가 처음부터 [1, 2, 3, 5] 처럼 정렬된 상태라면,
첫 번째 턴 이후에 굳이 두 번째 턴과 세 번째 턴을 할 필요가 없을 것이다.
따라서 첫 번째 턴에서 swap이 한번도 실행되지 않았다면, 그것은 이미 정렬된 데이터로
그 다음 턴을 실행하지 않고 정렬을 끝내도 될 것이다.

4. 알고리즘 구현

def bubbleSort(data):
    for i in range(len(data) - 1):
        isSwapped = False # swap이 일어났는지 나타내는 flag
        for j in range(len(data) - 1 - i):
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j] # swap
                isSwapped = True
        if isSwapped == False: # 원래부터 정렬되어있던 데이터
            break
    return data

코드 이미지

테스트

5. 알고리즘 분석

• 반복문이 두 개 $O(n^2)$
  - 최악의 경우, $\frac{n(n−1)}{2}$
• 완전 정렬이 되어 있는 상태라면 최선은 $O(n)$
  - isSwapped 변수를 통해 다음 턴을 진행하지 않기 때문

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기