[Python] 정렬 알고리즘

 

버블정렬

- 이웃한 두 값을 비교해 정렬하는 방법이다.

- 모든 원소를 하나하나 비교하여 swap하는 작업을 반복한다.

- 구현이 단순하다.

- 최대 O(n^2)의 시간복잡도를 가진다.

# 버블정렬
a = random.sample(range(1, 10), 5)
print("=== bubble ===")
print(a)  # 정렬 전
n = len(a)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
print(a)

 

삽입정렬

- 현재 위치에서, 이미 정렬된 이전 배열들의 데이터를 차례대로 비교하여 자신의 위치를 찾아 그 위치에 삽입한다.

- 최악의 경우 O(n^2), 최선의 경우(이미 정렬된 경우)에는 O(n)이다.

# 삽입정렬
a = random.sample(range(1, 10), 5)
print("=== insertion ===")
print(a)
n = len(a)
for i in range(1, n):
    key = a[i]  # 기준 값
    j = i - 1  # 바로 이전 위치
    while j >= 0 and a[j] > key:  # 몇 번째 자리에 값을 넣어야 하는지 찾음
        a[j + 1] = a[j]
        j -= 1  # 맨 앞까지 체크
    a[j + 1] = key
print(a)

 

선택정렬

- 주어진 배열에서 최솟값을 앞으로 보낸다.

- 데이터의 앞에서부터 순서대로 선택하고, 선택된 데이터의 뒤에 있는 데이터들 중 가장 작은 값과 swap한다.

- 탐색과정에서의 반복과 선택 위치를 증가시키는 반복을 하여 O(n^2)이다.

# 선택정렬
a = random.sample(range(1, 10), 5)
print("=== selection ===")
print(a)
n = len(a)
for i in range(n):
    min_idx = i
    for j in range(i + 1, n):
        if a[min_idx] > a[j]:  # 최솟값 인덱스를 찾음
            min_idx = j
    a[i], a[min_idx] = a[min_idx], a[i]
print(a)

 

퀵정렬

- 상대적으로 빠른 정렬 방법이다.

- 최대 O(nlogn)의 시간복잡도를 갖는다.

# 퀵정렬
a = random.sample(range(1, 100), 10)
print("=== quick ===")
print(a)


def quickSort(a, start, end):
    if start < end:
        left = start
        pivot = a[end]

        for i in range(start, end):
            if a[i] < pivot:  # 리스트의 인덱스 값이 pivot보다 작을 경우
                a[i], a[left] = a[left], a[i]
                left += 1
        a[left], a[end] = a[end], a[left]
        quickSort(a, start, left - 1)
        quickSort(a, left + 1, end)


quickSort(a, 0, len(a) - 1)
print(a)