[알고리즘] #1_1 버블 정렬

** 정렬(Sorting)

• 정의: 어떤 데이터들이 주어졌을 때, 이를 정해진 순서대로 나열하는 것
• 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수

 

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

 

 

 

** 버블 정렬(Bubble sort)

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

 

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

클릭시 출처로 이동

 

 

 

** 알고리즘 구현

• 패턴 분석

1. n개의 리스트가 있는 경우, 최대 n-1번의 로직을 적용한다.
2. 로직을 1번 적용할 때마다, 가장 큰 숫자가 뒤에서부터 1개씩 결정된다.
3. 로직이 경우에 따라 일찍 끝날 수도 있다. 로직을 적용할 때 한 번도 데이터가 교환된 적이 없다면, 이미 정렬이 완료된 상태이므로 더 이산 로직을 반복 적용할 필요가 없다.

 

 

---

def bubble_sort(data_list):
    for i in range(len(data_list) - 1):
        swap = False # swap 여부 확인
        
        for j in range(len(data_list) - i - 1):
            if data_list[j] > data_list[j + 1]:
                data_list[j], data_list[j + 1] = data_list[j + 1], data_list[j] # swap
                swap = True
        
        if swap == False: # swap이 한번도 일어나지 않은 경우
            break
            
    return data_list

 

# 테스트

import random

data_list = random.sample(range(100), 50)
bubble_sort(data_list)

---

 

** 알고리즘 분석

• 이중 반복문이므로, O(n^2)
• 최악의 경우, n*(n-1)/2
• 완전 정렬이 되어 있는 경우(최선), O(n)