TIL 9일차: 정렬 Sort (버블정렬, 선택정렬, 삽입정렬, 병합정렬), 스택 Stack

오늘은 아침에 자료구조 알고리즘 특강을 듣고 오후에는 3주차 정렬과 스택에 대해 배웠다.

강의 시간도 늘어나고, 중간중간 연습문제 푸느라 일시정지하는 것까지 생각하면 한 강당 30분에서 1시간은 걸렸다.

오늘 조금밖에 공부하지 못했다고 생각했는데, 이런식으로 생각하니 그래도 앉아있었던 만큼은 했구나 싶어서 뿌듯하다.

오늘 공부했던 것들을 찬찬히 살펴보면,

 

1. 정렬 Sort

정렬이란 데이터를 순서대로 나열하는 방법이다. 버블정렬, 선택정렬, 삽입정렬, 그리고 병합정렬에 대해 배워보자.

1) 버블정렬 Bubble Sort

첫째와 둘째 원소 비교, 둘째와 셋째 원소 비교, ... , 마지막-1과 마지막 원소의 비교 및 교환하면서 정렬한다.

파이썬에서의 원소 교환 방법은 a,b = b,a로 간단하다. 이중반복문으로 쓸 수 있다.

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

 

2) 선택정렬 Selection Sort

배열의 모든 요소를 살펴본 뒤 가장 작은 요소를 0번째 인덱스에 정렬한다.

그 다음으로 가장 작은 수를 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 array

 

3) 삽입정렬 Insertion Sort

1번째에는 1번째 인덱스에 있는 값을 0번째와 비교한다.

2번째에는 2번째 인덱스에 있는 값을 1번째, 0번째와 비교한다.

...계속 1만큼 비교했다가, 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]: #i - j 를 해줘야 우리가 원하는 1, 21, 321, 4321,... 이 나온다
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1] #앞의 원소가 크다면, 그 원소를 오른쪽으로 옮겨준다
            else:
                break #앞의 원소가 작다면 순서대로 정렬된 것이므로 그냥 넘어가면 된다.
    return array

 

4)병합정렬 Merge 단순히 합치기

병합정렬이란 배열의 앞 부분과 뒷 부분으로 두 그룹을 나누어 각각 정렬한 후, 병합하는 작업을 반복하는 알고리즘이다.

즉 배열의 값들을 하나씩 비교하고, 더 작은 값을 새로운 배열에 하나씩 추가해주는 것이다.

이를 위해 인덱스를 저장할 변수 array1_index, array2_index를 생성해야 한다.

만약 한 배열의 모든 원소들이 먼저 정렬되었다면, 남은 배열의 남은 값들은 새로운 배열에 추가하면 된다.

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    result = [] #새로운 배열 생성
    array1_index = 0 #인덱스를 저장할 변수 생성
    array2_index = 0 
    while array1_index < len(array1) and array2_index < len(array2): # 배열1과 2가 끝날때까지 반복
        if array1[array1_index] < array2[array2_index]: #둘중 작은 값을 새로운 배열에 차례대로 넣는다
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1


# 한 배열의 정렬이 먼저 끝나면, 다른 배열의 모든 값을 새로운 배열에 추가한다
    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge(array_a, array_b))

 

5) 병합정렬 MergeSort

앞선 병합정렬과 달리 여기에서는 분할 정복 Divide and Conquer의 개념을 도입한다.

분할 정복이란 문제를 2개의 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

반으로 쪼개고 쪼개서 마지막에 배열에 하나의 원소만 남을 때까지 쪼갠다.

여기에서 떠올려야 할 것이 재귀 함수이다. 반복되는 구조에서 문제를 축소시킬 수 있는가? 대답은 예스.

MergeSort(0, N) =  Merge(MergeSort(0, N/2) + MergeSort(N/2, N))
즉 0부터 N까지 정렬한 것을 보려면 0부터 N/2까지 정렬한 것과 N/2부터 N까지 정렬한 것을 합치면 된다.

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = (0 + len(array)) // 2
    left_array = merge_sort(array[:mid])   # 왼쪽 부분을 정렬하고
    right_array = merge_sort(array[mid:])  # 오른쪽 부분을 정렬한 다음에
    merge(left_array, right_array)         # 합치면서 정렬하면 된다

 

앞에서 구현한 merge와 이번의 merge_sort를 합쳐 작성하면 다음과 같다.

array = [5, 3, 2, 1, 6, 8, 7, 4]


def merge_sort(array):
	# 탈출 조건
    if len(array) <= 1:
        return array
        
    mid = len(array) // 2
    left_array = array[:mid] #왼쪽부분 정렬
    right_array = array[mid:] #오른쪽부분 정렬
    
    # 값 확인해보기
    print(array)
    print('left_arary', left_array)
    print('right_arary', right_array)
    return merge(merge_sort(left_array), merge_sort(right_array))


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge_sort(array))

 

2. 스택 Stack

스택의 사전적 정의는 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조이다.

빨래통을 떠올리면, 가장 처음에 넣은 빨래는 맨 아래 깔려 가장 늦게 나오고,

가장 마지막에 넣은 빨래는 맨 위에 쌓여 가장 빨리 나온다.

이러한 자료 구조를 Last In First Out (LIFO)이라고 부른다.

스택은 내 행동을 순서대로 기억해야 할 때 사용된다는데 아직 감은 안온다.

 

스택이 구현되는 것은 push, pop, peek, isEmpty로 네 가지를 배웠다.

push는 0번째 인덱스에 데이터를 넣을 때 쓴다.

pop은 0번째 인덱스에 있는 데이터를 뽑을때(없앨 때) 쓴다. 뽑았던 데이터를 리턴한다.

peek은 0번째 인덱스에 있는 데이터를 리턴한다.

isEmpty는 스택이 비었는지 여부를 확인한다.

	def push(self, value):                 # 현재 [4] 밖에 없다면
        new_head = Node(value)             # [3] 을 만들고!
        new_head.next = self.head          # [3] -> [4] 로 만든다음에
        self.head = new_head               # 현재 head의 값을 [3] 으로 바꿔준다.
        
	def pop(self):
        if self.is_empty():                  # 만약 비어있다면 에러!
            return "Stack is empty!"
        delete_head = self.head              # 제거할 node 를 변수에 잡습니다.
        self.head = self.head.next           # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.
        return delete_head                   # 그리고 제거할 node 반환
        
	def peek(self):
        if self.is_empty():
            return "Stack is empty!"

        return self.head.data

	def is_empty(self):
        return self.head is None

 

이러한 스택은 실제 코드에서 리스트를 이용해 구현된다.

stack = []            # 빈 스택 초기화
stack.append(4)       # 스택 push(4)
stack.append(3)       # 스택 push(3)
top = stack.pop()     # 스택 pop
print(top)            # 3!

 

 

맘 같아선 연습문제도 풀고 스택이랑 대비되는 개념인 택도 익히고 싶지만 오늘은 너무 피곤하다.

일찍 공부 끝내고 소화도 시킬 겸 운동 좀 하다 와야겠다. 그리곤 일찍 자야지!