알고리즘 3주차 - 개요, 정렬(버블, 선택, 삽입)

3주차에 배울 것

• 정렬

• 스택, 큐의 개념과 활용법

• 해쉬의 개념과 활용법

정렬

• 정렬이란 데이터를 순서대로 나열하는 것이다. 정렬하기 위해서는 다양한 방법이 있다. 대표적으로 스택/큐, 해쉬 등을 배워보고자 한다.

스택/큐

• 스택과 큐는 들어가고 나오는 곳이 정해져있는 자료구조

• 스택: Last in, first out

• 큐: First in, first out

해쉬

• 해쉬 알고리즘을 통해 문자열을 고정된 길이의 데이터로 만들 수 있음

• 블록체인 기술에서도 쓰이고 딕셔너리를 만들 때도 활용됨

• 예전에 수업시간에 해시 테이블, 체이닝기법, 개방주소 기법을 배웠던 것이 어렴풋이 기억난다....

---

정렬

정렬이란?

• 데이터를 순서대로 나열하는 방법

• 이는 이진 탐색을 가능하게 하기도, 데이터를 효율적으로 탐색할 수 있게 만든다

• 컴퓨터에게 정렬을 시키려면 명확한 과정을 설명해주어야 함

버블정렬

• 가장 쉽고 직관적

• 첫번째 자료와 두번째 자료, 두번재와 세번째, ... 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하며 교환하면서 자료를 정렬함

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4와 6을 비교합니다!
        4 < 6 이면 그대로 둡니다.

2단계 : [4, 6, 2, 9, 1]
           6과 2를 비교합니다!
           6 > 2 이므로 둘을 변경합니다!
       [4, 2, 6, 9, 1] 이렇게요!

3단계 : [4, 2, 6, 9, 1]
              6과 9를 비교합니다!
              6 < 9 이면 그대로 둡니다.

4단계 : [4, 2, 6, 9, 1]
                 9와 1를 비교합니다!
                 9 > 1 이므로 둘을 변경합니다!
       [4, 2, 6, 1, 9] 이렇게요!

..... 이와 같은 과정을 반복함.
첫 루프를 돌리면 가장 큰 값이 맨 뒤로 가있음.
배열의 크기 - 1 만큼 반복하면서 한개씩 줄어들으며 반복함

# 출처: 스파르타코딩클럽

input = [4, 6, 2, 9, 1]

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

bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

• 이 함수의 시간복잡도는?

• O(N^2)

• 파이썬 스왑의 좋은 점: a, b = b, a

선택정렬

• 말 그대로 선택해서 정렬

• 한번 쓱 둘러보며 가장 작은 값을 찾아서 맨 앞으로 오게 함.

• 첫번째를 배제하고 반복함

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4와 6과 2와 9와 1을 차례차례 비교합니다.
	      그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
       [1, 6, 2, 9, 4] 이렇게요!

자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.

# 출처: 스파르타코딩클럽

• 배열의 크기만큼 반복했다가 앞에서부터 한 개씩 줄어들면서 반복하는 구조

• 버블정렬과 다른 점은 매 루프마다 최솟값을 찾아서 바꿔줘야 한다는 점

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)
    for i in range(n-1):
        min_index = i
        for j in range(n-i):
            if array[i+j] < array[min_index]:
                min_index = i+j
        array[i], array[min_index] = array[min_index], array[i]
    return


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

• 시간복잡도는 O(N^2)일 것(반복문 2개)

삽입정렬

• 선택 정렬이 전체에서 최솟값을 "선택"하는 것이라면 삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입"

• 선택 정렬: 현 데이터의 상태와 상관없이 항상 비교, 위치 변경

• 삽입 정렬: 필요할 때만 위치 변경

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4는 현재 정렬되어 있는 부대원입니다. 
			  그럼 이제 새로운 신병인 6을 받습니다.
        4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
       [4, 6, 2, 9, 1] 이렇게요!

자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!

2단계 : [4, 6, 2, 9, 1]
        4, 6 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 2를 받습니다.
        4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다!
        4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
       [2, 4, 6, 9, 1] 이렇게요!

..... 반복

# 출처: 스파르타코딩클럽

input = [4, 6, 2, 9, 1]

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return

insertion_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

• 더 작지 않을 경우에는 더 반복 안하고 끝내버림(else 문)

• 시간복잡도는 역시 O(N^2)

• 하지만 break문이 있기에 버블정렬, 선택정렬과는 달리 최소한의 경우에는 N 즉 오메가 N을 얻을 수가 있음

• 거의 정렬이 다 된 상태로 입력이 된다면 else 문으로 많이 빠지게 됨