버블, 삽입, 선택 정렬

이들은 모두 정렬 알고리즘 중에 최악의 경우 시간복잡도가 $O(n^2)$인 정렬 알고리즘입니다.

버블 정렬(Bubble Sort)

버블 정렬은 앞의 값과 뒤의 값을 비교하여 교환하는 방식의 정렬 방식입니다. 버블 정렬의 특성상, 끝부터 정렬되기 때문에 비교 횟수는 $\displaystyle\frac{n(n-1)}{2}$번 비교하게 되므로 시간 복잡도는 $O(n^2)$입니다.

l = [5, 2, 3, 1, 9]
for i in l:
    for j in range(len(l)-i-1):
        if l[j] > l[j+1]:
            l[j], l[j+1] = l[j+1], l[j] # 교환
print(*l)

선택 정렬(Selection Sort)

선택 정렬은 배열에서 최솟값 혹은 최댓값을 찾아 정렬하는 방식입니다. key값을 기준으로 뒤의 원소들을 모두 비교하므로, $\displaystyle\frac{n(n-1)}{2}$번 비교하게 됩니다. 따라서 시간 복잡도는 $O(n^2)$입니다.

l = [5, 3, 8, 1, 2]
for i in range(len(l)):
    key = l[i]
    MIN = l[i]
    for j in range(i + 1, len(l)):
        if l[j] < MIN:
            MIN = l[j]
            MIN_index = j
    if key != MIN:
        cnt += 1
        l[MIN_index], l[i] = key, l[MIN_index]
print(*l)

삽입 정렬(Inserting Sort)

배열의 모든 요소를 앞에서부터 정렬된 배열과 비교하여 해당 요소가 들어갈 곳에 삽입하는 정렬 방식입니다. 앞에서부터 정렬된 배열과 비교할 때 그 배열의 크기가 1씩 증가하므로, 비교 횟수는 $\displaystyle\frac{n(n-1)}{2}$입니다. 따라서 시간복잡도는 $O(n^2)$입니다.

l = [5, 2, 3, 1, 9, 303, 2, 2, 1, 9, 8, 2, 8, 999, -1, 3, -100]

length = len(l)
for i in range(1, length):
    key = l[i]
    for j in range(i - 1, -2, -1): # 앞에 정렬된 배열에서 반복해서 삽입될 곳을 찾음
        if l[j] < key: # 더 작은 값이 존재한다면 그곳이 key가 들어갈 곳
            break
        l[j + 1] = l[j] # 만약 key 보다 더 큰 값이 있으면 서로 교환해주면서 뒤로 옮김
    l[j + 1] = key # 마지막 키가 들어갈 곳에 삽입

print(*l)