정렬 - bubble, selection, insertion

버블 정렬(bubble sort)

• 첫번째와 두번째, 두번째와 세번째, N-1번째와 N번째 요소를 비교해 나가면서 정렬을 하는 방법
• 만약 N-1번째와 N번째 요소를 비교했다면 다시 첫번째와 두번째 요소부터 N-2번째와 N-1번째 요소를 비교한다!
• 만약 오름차순으로 정렬하려면 매번 두 요소를 비교할 때마다 작은 요소와 큰 요소의 위치를 바꾼다
• 반복문 두개를 중첩해서 사용하므로 시간복잡도는 O(N^2)

예시

소스코드

def bubblesort(lst):
    lst_len = len(lst) - 1
    for i in range(lst_len):
        j = lst_len - i
        for k in range(j):
            if lst[k] > lst[k + 1]:
                lst[k], lst[k + 1] = lst[k + 1], lst[k]

a = [4, 2, 6, 1, 9]
bubblesort(a)
print(a)

// [1, 2, 4, 6, 9]

---

선택 정렬 (selection sort)

• 말 그대로 "선택"을 해서 정렬하는 방법
• 전체 요소 중 가장 작은 요소의 위치를 저장한 후 반복문 맨 앞의 인덱스 요소와 교환을 한다!
• 배열의 길이가 5라면 반복문을 한번 돌 때마다 인덱스가 0~4, 1~4, 2~4, 3~4로 변한다
• 버블 정렬과 다르게 반복문을 한번 돌 때마다 요소간의 교환이 일어나지 않지만 반복문을 중첩해서 사용하므로 시간복잡도는 버블 정렬과 같이 O(N^2)이다

예시

• 기준인 4와 나머지 수를 비교해서 가장 작은 1과 자리 교환

• 기준인 6과 나머지 수를 비교해서 가장 작은 2와 자리 교환

• 기준인 6과 나머지 수를 비교해서 가장 작은 4와 자리 교환

• 기준인 9와 6인 나머지 수를 비교해서 가장 작은 6과 자리 교환!

소스코드

def selectionsort(lst):
    for i in range(len(lst) - 1):
        min_idx = i
        for k in range(i+1, len(lst)):
            if lst[i] > lst[k]:
                min_idx = k
        if i != min_idx:
            lst[i], lst[min_idx] = lst[min_idx], lst[i]

a = [4, 2, 6, 1, 9]
selectionsort(a)
print(a)

---

삽입 정렬

• 선택 정렬이 전체에서 최솟값을 하나 "선택"하는 방법이라면 삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입"하는 방식
• 선택 정렬은 현재 데이터의 상태와 상관 없이 항상 비교하고 위치를 바꾸지만 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적이긴 하다
• 만약 배열이 이미 정렬(최선)된 경우 시간복잡도는 한번씩만 비교하므로 O(N)이지만 배열이 역으로 정렬(최악)되어 있을 경우 시간복잡도는 O(N^2)이다.
  → 최선의 경우 O(N), 평균과 최악 O(N^2)

예시

• 맨 처음에 아래와 같은 배열이 있다고 하자

• 배열에 4를 삽입

• 배열에 6을 삽입하고 4 < 6 이므로 그대로 냅둔다

• 배열에 2를 삽입하고 2 > 6이므로 둘의 자리를 바꿈 → [4, 2, 6]
• 2 < 4이므로 둘의 자리를 바꿈

• 배열에 9를 삽입하고 6 < 9이므로 그대로 냅둔다

• 배열에 1을 삽입하고 앞의 요소들과 비교해서 결국 [1, 2, 4, 6, 9]가 만들어짐

def insertionsort(lst):
    # 0번째 요소는 이미 정렬 -> 첫번째부터 len(lst) - 1번째를 정렬하면 됨
    for i in range(1, len(lst)):
        for j in range(i, 0, -1):
            print(i, j)
            if lst[j - 1] > lst[j]:
                lst[j - 1], lst[j] = lst[j], lst[j - 1]
            else:
                break
    return lst

a = [4, 6, 2, 9, 1]
insertionsort(a)
print(a)