버블 정렬(bubble sort) 알고리즘

1. 정렬이란?

• 어떤 데이터들이 주어졌을 때, 정해진 순서대로 나열하는 것
• 다양한 정렬 알고리즘 이해를 통해 동일한 문제에 대한 다양한 알고리즘이 고안될 수 있고, 각 알고리즘 간 성능 비교를 통해 알고리즘 성능 분석도 이해할 수 있음

2. 버블 정렬(bubble sort)

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

## https://visualgo.net/en 사이트에서 보면 쉽게 그림으로 이해할 수 있다. 

 

3. 패턴 찾기

• 데이터가 4개 일 때 
  • data_list = [1,9.3.2]
    • 1차 로직
      • 1 vs 9 => X
      • 9 vs 3 => [1, 3, 9, 2]
      • 9 vs 2 => [1, 3, 2, 9]
    • 2차 로직
      • 1 vs 3 => X
      • 3 vs 2 => [1, 2, 3, 9]
      • 3 vs 9 => X
    • 3차 로직
      • 1 vs 2 => X
      • 2 vs 3 => X
      • 3 vs 9 => X

==> N 개의 리스트가 있는 경우 N-1 로직을 적용한다

==> 로직을 1번 적용할 때마다, 가장 큰 수가 뒤에서부터 1개씩 결정된다 

==> 로직이 일찍 끝날 수도 있다 

        => 로직을 적용 시,  한 번도 데이터가 교환되지 않는다면 이미 정렬된 상태므로 더 이상 로직을 반복 적용할

             필요가 없다 

==> 로직 한 회 끝날 때 마다 가장 큰 숫자가 뒤에서 1개씩 결정된다

리스트	1회	2회	3회	4회
1, 9, 3, 2	1, 3, 2, 9	1, 2, 3, 9
9, 7, 5, 3, 1	7, 5, 3, 1, 9	5, 3, 1, 7, 9	3, 1, 5, 7, 9	1, 3, 5, 7, 9

 

4. 알고리즘

<프로토 타입>
1. for num in range(len(data_list)) 반복
2. swap = false // 교환되어있는지 확인,  false 가 기본값이여야 아래 for문에서 swap 이 멈춰야 알고리즘 종료
3. 반복문 안에서 , for index in range(len(data_list) - num - 1) 를 n-1번 반복해야한다 
    //num 을 빼는 이유는  data_list에서 로직이 돌면 맨 뒤에 가장 큰 값이 고정되기 때문에 
4. 반복문안의 반복문 안에서, if data_list[index] > data_list[index + 1]  이면
5. swap 시켜야한다
6. 더이상 swap 되지 않고 false 값이 나오면 break

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data

import random

data_list = random.sample(range(50), 20)
bubblesort(data_list)

>>[3, 5, 10, 11, 18, 19, 20, 21, 24, 26, 28, 29, 31, 33, 34, 38, 39, 44, 46, 49]

5. 분석

• 반복문이 두개  :  O(𝑛2)
  • 최악 : 𝑛∗(𝑛−1)2
• 완전 정렬 되어 있으면 최선 : O(n)