알고리즘 4일차

오늘 알고리즘 정렬 문제를 풀기 전에 부족했던 정렬에 대한 개념을 다시한번 다듬는 시간을 갖었다. 처음에 두루뭉술하게 알고만 있던 지식들을 직접 코드까지 짜보니깐 어느정도 머리에 자리잡아가는 것이 느껴졌다. 역시 코드는 직접 생각하고 짜야 나의 것이 된다는 것을 다시 한번 느낄 수 있었다.

---

오늘 한 일

• 알고리즘 정렬 정리!
• 백준 문제 풀이 및 해설

---

✔정렬

정렬을 하는방법은 여러가지가 있는데 그 중 다음의 항목들에 대해 알아보자.

• 버블정렬
• 선택정렬
• 삽입정렬
• 병합정렬

버블 정렬

• 동작 방식
  N개의 요소를 가진 배열이 존재한다고 가정했을 때, 버블 정렬의 동작 방식은 다음과 같다.

  1. 첫번째 자료와 두번째 자료를 비교한다.
  2. 비교한 값중 더 큰 값이 뒤로가게 서로 자리를 교체한다.
  3. 두번째 자료와 세번재 자료를 비교한다.
  4. 비교한 값중 더 큰 값이 뒤로가게 서로 자리를 교체한다.
     ...
  5. N-1번째 자료와 N번째 자료를 비교한다.
  6. 비교한 값중 더 큰값이 뒤로가게 서로 자리를 교체한다.
  7. 6번까지의 동작으로 N번째 자료는 정렬이 완료된다.
  8. 6번까지의 과정을 N-1번 실행하여 배열을 정렬한다.

• 특징
  버블 정렬의 특징은 다음과 같다.

  • 배열의 가장 뒤에서 부터 순차적으로 정렬된다.
  • N의 제곱만큼의 Big-O를 갖는다.

• 코드

# 다음의 배열을 정렬하시오.
input = [4, 6, 2, 9, 1]

def buble_sort(array):
	n = len(array)
    for i in range(n - 1):	# 마지막으로 주어지는 값은 정렬하지 않아도 이미 정렬되어 있다고 판단할 수 있기 때문에 -1을 한다.
    	for j in range(n-i-1):	# 뒤에서부터 i만큼의 자료가 정렬이 완료되기 때문에 비교횟수에서 i를 뺀다.
        	if array[j] > array[j+1]:
        		array[j], array[j+1] = array[j+1], array[j]	# a,b = b,a 를 사용하면 두 배열의 자료를 서로 바꿀 수 있다.
	return
buble_sort(input)
print(input)
# [1, 2, 4, 6, 9]

선택 정렬

• 동작 방식
  N개의 요소를 가진 배열이 존재한다고 가정했을 때, 선택 정렬의 동작 방식은 다음과 같다.

  1. N개의 자료를 모두 확인해서 가장 작은 자료를 찾아낸다.
  2. 자료는 정렬되지 않은 자료들 중 맨 앞의 자료와 서로 바꾼다.
     ...
  3. 마지막으로 남은 2개의 자료들 중 작은 자료를 찾아낸다.
  4. 자료는 정렬되지 않은 자료들 중 앞의 자료와 서로 바꾼다.

• 특징
  선택 정렬의 특징은 다음과 같다.

  • 배열의 앞에서부터 순차적으로 정렬되어 간다.
  • N의 제곱만큼의 Big-O를 갖는다.

• 코드

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

def selection_sort(array):
	n = len(array)
    for i in range(n-1):
    	min_index = i	# 가장 작은 값이 들어있는 index값을 의미한다.
        for j in range(n-i-1):
        	if array[min_index] > array[i+j+1]: # for문이 돌때마다 비교하는 맨 앞 요소를 하나씩 증가 시켜준다. i+j+1
            	min_index = i+j+1
        array[i], array[min_index] = array[min_index], array[i]
    return
    
selection_sort(input)
print(input)

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

삽입 정렬

• 동작 방식
  N개의 요소를 가진 배열이 존재한다고 가정했을 때, 선택 정렬의 동작 방식은 다음과 같다.

  1. 배열에서 자료를 하나 선택한다. 자료 하나는 정렬되어 있다고 할 수 있다.
  2. 배열에서 자료를 하나 더 선택한다.
  3. 선택한 자료를 정렬되어 있는 배열에 추가한다.
  4. 추가한 자료와 앞에 있는 자료를 서로 비교한다.
  5. 추가한 자료의 값이 정렬되어 있는 자료보다 더 커질때까지 자료를 바꾼다.
     ...
  6. 배열에서 마지막으로 정렬되지 않은 자료 하나를 선택한다.
  7. 추가한 자료의 값이 정렬되어 있는 자료보다 더 커질때까지 자료를 바꾼다.

• 특징
  삽입 정렬의 특징은 다음과 같다.

  • 배열중 첫번째를 정렬되어 있는 상태라 가정하고 하나씩 뒤에서부터 비교해가며 정렬해나간다.
  • 첫번째는 정렬되어 있다 가정하기 때문에 0번째에서는 정렬하지 않는다. range(1, N)
  • 인덱스 값이 뒤인 값을 역순차적으로 비교하기 때문에 i-j 인덱스 값을 이용한다.

• 코드

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

def insertion_sort(array):
	n = len(array)
    for i in range(1, n):	# 배열의 첫번째 자료를 정렬되어 있다 가정하기 때문에 1번부터 정렬한다.
    	for j in range(i):
        	if array[i-j-1] > array[i-j]:	# 배열의 역으로 순차적으로 비교해가기 때문에 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]

병합 정렬

• 특징
  병합 정렬의 핵심 특징은 배열의 자료가 하나만 존재하면 정렬되어 있다고 볼 수 있다라는 특징을 이용했다는 것인데 기존의 배열을 정렬이 될 때까지 쪼갠 뒤에 각 쪼갠 배열들을 병합해 나가면서 정렬하는 방식이다.

• 코드

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

# 병합정렬 : 정렬되어 있는 상태가 될때까지 쪼개서(배열내 요소가 한개 있을 때를 의미) 다시 합치면서 정렬하는 방식
#           Big_O(NlogN)
#           재귀함수를 사용한다.

def merge_sort(array): # 재귀함수를 사용해서 array를 정렬되어 있는 상태가 될때까지 쪼갠다.
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    return merge(left_array, right_array)


def merge(array1, array2): # 정렬되어 있는 두개의 array에 들어있는 자료들을 비교하며 새로운 sorted_list라는 리스트에 넣어준다.
    sorted_list = []
    array1_pointer = 0
    array2_pointer = 0
    while array1_pointer < len(array1) and array2_pointer < len(array2):
        if array1[array1_pointer] < array2[array2_pointer]:
            sorted_list.append(array1[array1_pointer])
            array1_pointer += 1
        else:
            sorted_list.append(array2[array2_pointer])
            array2_pointer += 1
    if array1_pointer >= len(array1):
        while array2_pointer < len(array2):
            sorted_list.append(array2[array2_pointer])
            array2_pointer += 1
    if array2_pointer >= len(array2):
        while array1_pointer < len(array1):
            sorted_list.append(array1[array1_pointer])
            array1_pointer += 1
    return sorted_list

print(merge_sort(array))

---