버블 정렬

1. 정렬(sorting)이란?

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

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

 

2. 버블 정렬(Bubble sort)란?

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

 

버블 정렬 알고리즘 작동방식(출처: 위키피디아)

의사 코드

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

• 만약 첫번째 턴에서 swap이 한번도 일어나지 않았다면 '정렬 되어있다'는 뜻이므로 빠져나오면 됨

3. 버블정렬 연습

 

데이터가 두 개일 때 버블 정렬

data_list = [9, 7]

if data_list[0] > data_list[1]:
    data_list[0], data_list[1] = data_list[1], data_list[0]
    print(data_list[0], data_list[1])

데이터가 세 개 이상일 때 버블 정렬

def bubblesort3(data):
    for index in range(len(data)-1):
        for index2 in range(len(data)-1):
            if data[index2] > data[index2+1]:
                data[index2], data[index2+1] = data[index2+1], data[index2]

    return data

data_list = [0, 9, 8]
bs = bubblesort3(data_list)
print(bs)

• 출력 : [0, 8, 9]

4. 알고리즘 구현

 

특이점 찾아보기

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

for num in range(len(data_list)) 반복 swap = 0 (교환이 되었는지 확인하는 변수) 반복문 안에서, for index in range(len(data_list) - num - 1) n-1번 반복해야 하므로 반복문의 반복문 안에서 if data_list[index] > data_list[index+1]이면 data_list[index], data_list[index+1] = data_list[index+1], data_list[index] swap += 1 반복문 안에서 if swap == 0이면 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

 

5. 알고리즘 분석

• 반복문이 두 개 O(n^2)
• 최악의 경우 : n * (n-1) / 2
• 완전 정렬이 되어있는 상태라면 최선은 O(n)