[알고리즘] 패스트캠퍼스 알고리즘 학습 - 버블정렬

버블 정렬

두 인접한 원소를 검사하면서 정렬하는 방법

앞에서부터 두 개의 데이터를 비교하면서 정렬한다.

한 번 실행하면 가장 큰 값이 가장 뒤로 정렬되는 방식이다.

두 번째 실행하면 그다음 큰 값이 가장 뒤에서 한번 전까지 데이터를 비교하며 정렬하게 된다.

시간 복잡도가

에 해당되므로 느리지만, 단순하다.

 

 

 

 

 

 

data_list = [9, 7, 5, 3, 1]  
def bubbleSort(data_list):
    for i in range(len(data_list)):
        swap = False
        for j in range(len(data_list)-1-i):
            if data_list[j] > data_list[j+1]:
                swap = True
                data_list[j], data_list[j+1] = data_list[j+1], data_list[j]
                print(data_list)
        if swap == False:
            break
    return data_list

bubbleSort(data_list)

>>>
[7, 9, 5, 3, 1]
[7, 5, 9, 3, 1]
[7, 5, 3, 9, 1]
[7, 5, 3, 1, 9]
[5, 7, 3, 1, 9]
[5, 3, 7, 1, 9]
[5, 3, 1, 7, 9]
[3, 5, 1, 7, 9]
[3, 1, 5, 7, 9]
[1, 3, 5, 7, 9]
[1, 3, 5, 7, 9]

이중 for 문을 사용해서 앞에서부터 2개의 데이터를 비교해나간다.

가장 뒷 쪽 데이터는 확인할 필요가 없으니 반복문을 도는 횟수가 1개씩 줄어든다.

swap이라는 변수를 두어, 전체 반복문을 돌기 전 모든 정렬이 완료되면 for문을 종료한다.

def bubbleSort(data_list):
    for i in range(len(data_list)):
        swap = False
        for j in range(len(data_list)-1-i):
            if data_list[j] > data_list[j+1]:
                swap = True
                data_list[j], data_list[j+1] = data_list[j+1], data_list[j]
        if swap == False:
            break
    return data_list

import random

data_list = random.sample(range(100), 20)
print(data_list)
print(bubbleSort(data_list))

>>>
[69, 78, 25, 58, 76, 24, 21, 33, 42, 84, 15, 79, 59, 27, 71, 39, 56, 29, 49, 3]
[3, 15, 21, 24, 25, 27, 29, 33, 39, 42, 49, 56, 58, 59, 69, 71, 76, 78, 79, 84]

중간 부분 확인을 위한 print문을 삭제하고 random함수를 사용해서 임의의 숫자들이 잘 정렬되었는지 확인해보았다.

 

[알고리즘] 패스트캠퍼스 알고리즘 학습 - 삽입 정렬(Insertion Sort)

[알고리즘] 패스트캠퍼스 알고리즘 학습 정리 - 더블 링크드 리스트(Double Linked List)