저희 스터디는 이번에 대략적으로 자료구조에 대한 강의를 마치고 정렬 알고리즘에 대해서 공부하게 되었습니다.
그리고 이제부터 Java 대신 Python을 사용하여 코딩 테스트를 준비하게 되었습니다.
기본적인 Python 강의도 같이 들었는데, 확실히 Java를 사용할 줄 알기 때문에 이해가 안되는 부분은 전혀 없었습니다. 그리고 Python에 대해 드는 느낌은 자유도가 정말 높은 언어라는 것을 느꼈습니다. 아직 익숙하진 않지만 Java를 배울 때보다 쉬운 것은 확실하다.
정렬
정렬이라는 것은 간략히 어떤 데이터가 주어지면, 그 데이터들을 정해진 순서대로 나열하는 것을 의미합니다.
이러한 정렬 알고리즘에는 기본적으로 버블 정렬, 선택 정렬, 삽입 정렬이 있고, 이러한 알고리즘들보다 효율적인 합병 정렬, 퀵 정렬, 힙 정렬 등이 있습니다.
일단 강의에서는 버블 정렬, 선택 정렬, 삽입 정렬에 대해서 설명했습니다.
버블 정렬
이 버블 정렬은 인접한 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복하여 정렬하는 알고리즘입니다. 정렬하는 과정에서 작은 수가 마치가 거품 처럼 위로 올라가는 것을 연상한다고 하여 버블 정렬입니다.
이 버블 정렬을 의사 코드(Pseudo Code)로 작성하면 다음과 같습니다.
Input : 크기가 N인 배열 arr
Output : 정렬된 배열 arr
for i = 1 to N-1 // (N-1)번 수행
for j = 1 to N-i // arr[0]부터 arr[N-i]까지 비교하기 위해
if(arr[j-1] > arr[j])
swap(arr[j-1], arr[j]) // 서로 위치를 바꾼다.
return arr위의 의사 코드를 보면 2중 for 문을 사용하는데, 이를 통해 시간복잡도가 O(N^2)인 것을 알 수 있습니다.
선택 정렬
선택 정렬은 배열 전체에서 최솟값을 '선택'하여 배열의 0번 원소와 자리를 바꾸고 다음에는 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여 배열의 1번 원소와 자리를 바꾸는 방식으로 정렬합니다.
이 선택 정렬을 의사 코드를 사용하여 표현하면 다음과 같습니다.
Input : 크기가 N인 배열 arr
Output : 정렬된 배열 arr
// arr[i]에서부터 arr[n-1]까지 숫자들 중에서 최솟값을 찾기 위해
// n-2 까지만 하는 이유는 n-1까지 수행할 경우, 다음 for 문의 j 값이 범위를 넘어서기 때문
for i = 0 to n-2
min = i // arr[i]를 최솟값으로 지정
for j = i+1 to n-1
if(arr[j] < arr[min])
min = j
swap(arr[i], arr[min]) // for문에서 찾은 최솟값을 교환
return arr선택 정렬 또한 마찬가지로 시간복잡도는 O(N^2)입니다.
선택 정렬의 특징은 입력이 거의 정렬되어 있든, 역으로 정렬되어 있든지, 랜덤하게 되어 있든지를 구분하지 않고 항상 일정한 시간복잡도를 나타낸다는 것입니다.
삽입 정렬
삽입 정렬은 배열을 정렬된 부분과 정렬이 안된 부분으로 나누고, 정렬이 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복합니다.
이 삽입 정렬을 의사 코드를 사용하여 표현하면 다음과 같습니다.
Input : 크기가 N인 배열 arr
Output : 정렬된 배열 arr
for i = 1 to n-1 { //
element = arr[i] // 정렬이 안 된 부분의 가장 왼쪽에 있는 원소
j = i - 1 // 정렬이 된 부분의 가장 오른쪽 인덱스가 되어 왼쪽 방향으로 삽입할 곳 탐색
// element가 삽입될 곳을 탐색
// arr[j]가 element보다 크면 오른쪽으로 1칸 이동시키면서 비교
while (j >= 0) and (arr[j] > element) {
arr[j+1] = arr[j] // 자리 이동
j = j - 1
}
arr[j+1] = element
}
return arr이 삽입 정렬은 입력의 상태에 따라 수행 시간이 달라질 수 있습니다.
즉, 입력이 이미 정렬되어 있으면 시간복잡도는 O(N)입니다. 따라서 삽입 정렬은 거의 정렬된 입력에 대해서 다른 정렬 알고리즘보다 빠르다는 장점을 가지고 있습니다.
반면에 역으로 정렬된 입력에 대해서는 시간복잡도는 O(N^2) 시간이 걸립니다.
여기까지 기본적인 정렬 알고리즘이며, 각 언어에서 제공해주는 정렬 메서드가 있기 때문에 편리하게 배열이나 리스트 등을 정렬해줍니다. 그래도 이번에 정렬을 배웠기 때문에 이를 구현하는 문제를 Leetcode에서 풀었습니다.
이 문제를 요약하자면 제공되고 있는 정렬 메서드를 사용하지 않고 시간 복잡도가 O(N logN)인 정렬을 구현하는 문제입니다.
이에 대한 정렬 알고리즘은 여러 가지 있지만 저는 바로 합병 정렬(Merge Sort)이 생각났습니다.
합병 정렬
합병 정려은 데이터들이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘(Divide and Conquer)입니다.
즉, N개의 숫자들을 N/2 개씩 2개의 부분문제로 분할하고, 각각의 부분 문제를 재귀적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬합니다.
아래의 코드는 위의 Leetcode 문제를 Python으로 합병 정렬을 통해 구현된 코드입니다.
class Solution(object):
def sortArray(self, nums):
if len(nums) < 2:
return nums
mid = len(nums) / 2 # 중간 인덱스
pivot_left = nums[:mid] # 중간 인덱스를 기준으로 왼쪽 부분
pivot_right = nums[mid:] # 중간 인덱스를 기준으로 오른쪽 부분
# 1개만 남을 때까지 왼쪽, 오른쪽 부분 각각 분할
left = self.sortArray(pivot_left)
right = self.sortArray(pivot_right)
# 합병
return self.mergeSort(left, right)
# 병합 정렬
def mergeSort(self, left, right):
sorted_list = [] # 합병된 결과를 저장할 공간
i, j = 0, 0
# 왼쪽과 오른쪽 부분의 인덱스가 넘어서지 않도록
while i < len(left) and j < len(right):
# 오른쪽 부분의 원소가 크면 왼쪽 원소를 먼저 저장
if left[i] <= right[j]:
sorted_list.append(left[i])
i += 1
# 왼쪽 부분의 원소가 크면 오른족 원소를 먼저 저장
else:
sorted_list.append(right[j])
j += 1
# 왼쪽 또는 오른쪽 원소가 남았으면 그대로 저장
while i < len(left):
sorted_list.append(left[i])
i += 1
while j < len(right):
sorted_list.append(right[j])
j += 1
return
}합병 정렬의 시간 복잡도는 O(N logN) 입니다.
여태까지 기본적인 자료구조에 대해서 공부했는데, 완전히 이해하지 않았지만 어쨋든 자료구조를 마치고 알고리즘에 진입했는데, 자료구조를 배웠을 때보다 이제 훨씬 더 어려워질 것이라고 생각합니다. 항상 말할 때마다 열심히 노력하겠다고 했는데, 제가 느끼는 거지만 지금 열심히 노력하고 있는게 맞나 생각이 듭니다. 이런 생각이 들지 않게끔 더 노력하는 수 밖에 없을 것 같습니다.
이상으로 이번주에 공부했던 정렬 알고리즘에 대해서 알아봤습니다. 감사합니다
