정렬 알고리즘

이정연·2023년 5월 5일

Bubble Sort Merge sort Sort Tim-sort insert sort

Data Structure & Algorithm

목록 보기

6/10

정렬을 할 때 가져다 쓸 수 있는 도구들 집대성

버블 정렬

버블 정렬(Bubble Sort)은 인접한 두 원소를 비교하여 정렬하는 알고리즘 중 가장 간단한 형태입니다. 이름에서 유추할 수 있듯이, 정렬 과정에서 원소들이 "거품처럼" 이동하면서 정렬이 완료됩니다.

버블 정렬은 다음과 같은 알고리즘으로 동작합니다.

리스트의 첫 번째 원소부터 마지막 원소까지, 인접한 두 원소를 비교합니다.
왼쪽 원소가 오른쪽 원소보다 크면, 두 원소의 위치를 서로 바꿉니다.
모든 인접한 원소 쌍에 대해 위 과정을 반복합니다.
마지막 원소까지 위 과정을 수행한 후, 마지막 원소를 제외하고 다시 1번 과정부터 반복합니다.
리스트가 정렬될 때까지 위 과정을 반복합니다.

다음은 Python 코드로 구현된 버블 정렬의 예시입니다.

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(n-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

위 코드에서 lst는 정렬할 리스트를 나타냅니다. n 변수에는 리스트의 길이를 저장하고, 바깥쪽 for 루프는 리스트의 모든 원소를 순회합니다. 안쪽 for 루프는 인접한 두 원소를 비교하고, 원소의 위치를 교환합니다. 이 과정을 모든 인접한 원소 쌍에 대해 반복하며, 리스트를 정렬합니다.

버블 정렬의 시간복잡도는 O(N^2)이다.