[TIL] 99. [알고리즘] 정렬

키워드

• 알고리즘
• 정렬
• 버블정렬
• 삽입정렬
• 선택정렬

알고리즘

구구단을 예시로 든다면
구구단의 숫자들은 자료구조, 곱셈은 알고리즘에 해당
즉, 자료구조는 기반, 알고리즘은 방법

[알고리즘] 정렬

• 말 그대로 자료들을 일정한 규칙에 맞게 정리하는 알고리즘(보통은 오름차순)

[정렬] 버블정렬(Bubble Sort)

• 오른쪽부터 정렬되며 마치 거품이 올라오는 모양
• 서로 이웃한 두 원소 크기를 비교하고 교환을 반복
• 정렬 알고리즘 중 가장 간단한 알고리즘이며 사실상 가장 비효율적인 알고리즘

1. 1번째 항목과 2번째 비교 후 1번째가 더 크면 항목 교체
2. 2번째, 3번째 ~ 쭉 1번처럼 반복
   (한번의 사이클을 마치면 가장 끝에는 가장 큰 값이 위치하게 됨. 따라서 가장 끝단은 더 안봐도 괜찮다.)
3. 한 사이클을 돌고나면 마지막에 가장 큰 값이 위치하기 때문에 다시 1번째부터 n-1번째까지 반복

• 목록의 정렬 여부와 상관없이 무조건 이중반복문에 대한 시간복잡도를 갖게되므로 O(n^2)
• 바로 이웃한 노드만 교환하므로 비교적 안정적

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

    return li

[정렬] 삽입정렬(Insertion Sort)

• 왼쪽 1개부터 선택하여 정렬 배열이라 가정하고 오른쪽의 값들을 하나씩 삽입하여 정렬하는 알고리즘
• 위에서 회색영역(정돈이 되었다고 가정하는 정렬)에 대해 하얀색영역(새로 값을 보내는 영역)에서 값을 가져옴
• 31이 회색영역에 대해서 회색의 오른쪽(값이 큰 부분)부터 비교하며 31이 큰 경우 그 자리에서 스왑
• 선택정렬과 비슷하지만, 값이 가장 작은 원소를 선택하지 않고 비교 후 삽입을 동시에 진행
• 소량의 데이터를 정렬하는데 특화
• 버블, 선택 정렬이 점차 비교/탐색 범위가 좁아지는 것과 다르게 삽입정렬은 점차 커짐(회색부분이 커지니까)
• 아주 이상적으로 정돈된 정렬에 대해선 O(n)이지만 최악으로 내림차순 정렬에 대해선 O(n^2)

def insertion_sort(li):
    for i in range(1, len(li)):
        for j in range(i, 0, -1):
            if li[j] < li[j-1]:
                li[j-1], li[j] = li[j], li[j-1]

    return li

[정렬] 선택정렬(Selection Sort)

• 가장 왼쪽부터 나머지 정렬에서의 최솟값과 비교하여 스왑하며 진행
• 가장 왼쪽에 최솟값이 들어가면서 점차 탐색하는 범위가 줄어드는 구조
• '최소값을 갖는 노드 선택 -> 왼쪽값과 비교 -> 교환
• 서로 이웃하지 않은 노드를 교환하기 때문에 상대적으로 불안정
• 또한 외부 및 내부루프 모두 O(n)으로 이중반복문이므로 O(n^2)

def selection_sort(li):
    for i in range(len(li)):
        min_idx = i
        for j in range(i+1, len(li)):
            if li[j] < li[min_idx]:
                min_idx = j
        li[i], li[min_idx] = li[min_idx], li[i]

    return li

교환(스왑)

1) 일반적인 스왑 방식

a = 1
b = 2

temp = a
a = b
b = temp

2) 파이썬에서 구현 가능한 스왑 방식

a = 1
b = 2

a, b = b, a

---

알고리즘의 입문으로 많이 배우는 정렬 알고리즘에 대한 학습!
위의 정렬은 아주 기초이고 효율면에서 실용성은 떨어진다!
실제 정렬 알고리즘 종류는 정말 많다!