728x90
반응형
velog에 정렬 알고리즘을 정리했지만 다시 조금씩 까먹는 것 같아 다시 한번 정리하려고 한다
컴퓨터 과학 분야에서 정렬 알고리즘은 어떤 자료의 요소를 순서대로 배치하는 방법에 관한 것이다.
검색이나 병합 알고리즘을 사용할 때 입력된 데이터가 효율적으로 정렬되어 있는 것이 중요한데, 이 때 정렬의 효율성에 알고리즘이 고려된다
정렬 알고리즘의 아웃풋은 아래의 두가지 조건을 충족해야 해야 한다
1. 아웃풋은 단조(monotonic)로워야 한다
2. 아웃풋은 인풋의 순열(permutations)이어야 한다
즉, 정렬 알고리즘을 사용해 정렬이 끝난 뒤에 결과물의 각 요소는 (1) 이전 요소보다 작거나 크지 않아야 하며(한가지 흐름을 유지한다는 뜻) (2) 인풋의 모든 요소를 유지해야 한다
위와 같이 다양한 정렬 알고리즘이 있으며 이는 일부에 지나지 않는다.
또한 가장 왼쪽 열을 보면 알 수 있듯이 요소들이 랜덤하거나 거의 정렬이 되어 있거나 반대로 되어 있거나 할 경우에 각각 효율적인 정렬 알고리즘이 다르다
따라서 정렬하고자 하는 raw data의 상황을 정확히 판단하고, 적절한 알고리즘을 사용해 정렬을 할 수 있어야겠다
기본정렬(Normal Sort)
1. 버블 정렬(Bubble Sort)
원소의 움직임이 거품이 올라오는 것처럼 보여서 버블정렬이라고 한다
- 1회 순회 시 가장 큰 마지막 하나가 정렬되고 나머지 원소들은 한칸씩 앞으로 움직이면서 자기 자리를 찾아간다
- 시간복잡도가 O(n²)로 비효율적이나 코드가 단순해 간단한 코딩에는 사용되기도 한다
- 실무에 쓰이지 않는다
알고리즘 진행 순서
1. 0번째 원소와 1번째 원소를 비교 후 정렬
2. 1번째 원소와 2번째 원소를 비교 후 정렬
...
3. n-1번째 원소와 n번째 원소를 비교 후 정렬 ( 1회 순회 완료 )
4. 0번째 원소와 1번째 원소를 비교 후 정렬
5. 1번째 원소와 2번째 원소를 비교 후 정렬
6. n-2번째 원소와 n-1번째 원소를 비교 후 정렬 ( 2회 순회 완료 )
...
코드
"""This is bubble sort example"""
def bubble_sort(arr_list):
"""Bubble Sort"""
length_of_arr = len(arr_list) - 1 # 정렬하고자 하는 배열의 길이
for i in range(length_of_arr):
flag = False # 1회 순회 시 swap이 일어났는지 판단
for j in range(length_of_arr - i): # length_of_arr - i 이후의 값들은 이미 정렬이 되었으므로 범위에서 제외
if arr_list[j] > arr_list[j + 1]: # 현재 요소가 다음 요소보다 크면 swap
arr_list[j], arr_list[j + 1] = arr_list[j + 1], arr_list[j]
flag = True # swap이 일어났으므로 flag activated
if flag is False: # 순회 후에 swap이 일어나지 않았다면 이미 전체 정렬되었다고 판단하고 순회 중단
break
return arr
arr = [1, 5, 11, 4, 2, 6, 8, 4, 9]
print(bubble_sort(arr))[1, 2, 4, 4, 5, 6, 8, 9, 11]
이중 반복문을 사용하므로 시간 복잡도는 O(n²)이다
만약 자료가 이미 정렬되어 있다면 1회 반복 후 flag가 deactivate이고 시간 복잡도는 O(n)이다.
따라서 자료가 거의 정렬되어 있다면 다른 정렬보다 효율적일 수도 있다(보통 그렇지 않다)
2. 선택 정렬(Selection Sort)
- 가장 작은 값을 찾아 자신에게 맞는 위치와 교환한다
- 자료의 정렬 여부와는 관계없이 무조건 1회 순회 시 전체 리스트를 검사하며 가장 작은 값을 찾아내기 때문에 항상 시간복잡도는 O(n²)이다
알고리즘 진행 순서
1. 0번째 원소 ~ n번째 원소 중 가장 작은 값을 찾아 0번째 원소와 swap
2. 1번째 원소 ~ n번째 원소 중 가장 작은 값을 찾아 1번째 원소와 swap
...
3. n-1번째 원소 ~ n번째 원소 중 가장 작은 값을 찾아 n-1번째 원소와 swap
코드
# Selection Sort
def selection_sort(arr):
for i in range(len(arr)):
min_index = i # 바꿔줄 자리
for j in range(i, len(arr)): # j ~ n까지 중에서 가장 찾은 값 찾기
if arr[min_index] > arr[j]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i] # 가장 작은 값의 위치와 i를 바꿔준다
return arr
arr = [1, 5, 11, 4, 2, 6, 8, 4, 9]
print(selection_sort(arr))[1, 2, 4, 4, 5, 6, 8, 9, 11]
3. 삽입 정렬(Insertion Sort)
- 두번째 요소부터 시작해 그 앞의 자료들과 비교해 대소를 따져 자신의 위치를 찾아 삽입한다
- 탐색범위가 점점 넓어진다
- 인간이 카드를 하나씩 받아 정렬하는 방식과 유사하다
- 최선의 경우 하나씩 범위를 늘린 값이 가장 큰 값일 경우 O(n)의 시간복잡도를 가지지만, 최악의 경우 앞의 모든 숫자를 비교해 한칸씩 바꿔주어야 하므로 O(n²)의 시간복잡도를 가진다
알고리즘 진행 순서
1. 0번 원소를 건너뛴다
2. 0~1번 원소 중 1번 원소가 들어가야 할 위치를 찾아서 넣는다
3. 0~2번 원소 중 2번 원소가 들어가야 할 위치를 찾아서 넣는다
...
4. 0~n번 원소 중 n번 원소가 들어가야 할 위치를 찾아서 넣는다
코드
# Insertion Sort
def insertion_sort(arr):
for i in range(1, len(arr)): # 0번 원소는 건너뛴다
j = i # j는 i번 원소부터 시작해 -1되며 앞의 요소를 전부 비교한다
while j > 0 and arr[j - 1] > arr[j]: # i번 요소가 그 전 원소보다 작다면 하나씩 비교해가며 자리를 찾는다
arr[j - 1], arr[j] = arr[j], arr[j - 1]
j -= 1
return arr
arr = [1, 5, 11, 4, 2, 6, 8, 4, 9]
print(insertion_sort(arr))[1, 2, 4, 4, 5, 6, 8, 9, 11]
- i-1번째까지 정렬이 끝난 배열에 i번째 원소가 추가되면 i번째 원소의 위치를 찾기 위해 while문이 돌게 된다
분할 정복 정렬 (Divide and conquer Algorithms)
4. 합병 정렬(Merge Sort)
- 원소를 각각 분할한 후에 작은 값을 왼쪽, 큰 값을 오른쪽으로 넣은 새로운 리스트를 생성해가며 정렬한다
- 분할 이후 병합 단계에서 정렬을 수행한다
- 항상 O(nlogn)의 시간복잡도를 가지지만 원소의 개수만큼 리스트를 쪼개고 저장해두어야 하므로 O(n)의 공간복잡도를 가진다 (메모리로 시간을 사는 방법)
알고리즘 진행 순서
1. [4, 1, 7, 5, 3, 2, 6] 리스트를 받는다
2. 길이가 1이 될 때까지 쪼갠다 ( [4] [1] [7] [5] [3] [2] [6] )
3. 왼쪽과 오른쪽 각각의 첫번째 원소부터 비교해 작은 값을 차례로 넣은 리스트를 만든다
4. 만약 왼쪽, 오른쪽 중 한 곳의 원소를 모두 사용했다면 나머지 값을 전부 병합시킨 후 새로운 리스트를 리턴한다
5. 다시 새로운 리스트끼리 3 - 4과정을 반복해 정렬된 리스트를 얻는다
코드
def merge_sort_divide(arr):
if len(arr) < 2: # arr의 길이가 1이면 arr값을 그대로 리턴
return arr
mid = len(arr) // 2
left = merge_sort_divide(arr[:mid])
right = merge_sort_divide(arr[mid:])
return merge_sort_merge(left, right)
def merge_sort_merge(left, right):
i, j = 0, 0
new_list = []
while (i < len(left)) and (j < len(right)): # 왼쪽과 오른쪽 원소 0번 원소 중 작은 값을 먼저 넣은 새로운 리스트를 생성
if left[i] > right[j]:
new_list.append(right[j])
j += 1
else:
new_list.append(left[i])
i += 1
if i == len(left): # 위 while문에서 left든 right든 한쪽 값을 다 사용했다면 나머지 값을 전부 병합
new_list = new_list + right[j:]
elif j == len(right):
new_list = new_list + left[i:]
return new_list
arr = [4, 1, 7, 5, 3, 2, 6]
print(merge_sort_divide(arr))
public class 병합정렬 {
public static void main(String[] args) {
int[] arr = new int[] {7,12,6,135,1,2,41,4,7623,53,51,41,2,7,23,24,12,23};
int[] result = mergeSort(arr);
System.out.println(Arrays.toString(result));
}
private static int[] mergeSort(int[] arr) {
return divide(arr);
}
private static int[] divide(int[] arr) {
if (arr.length < 2) return arr;
int mid = arr.length / 2;
int[] left = divide(Arrays.copyOfRange(arr, 0, mid));
int[] right = divide(Arrays.copyOfRange(arr, mid, arr.length));
return merge(left, right);
}
private static int[] merge(int[] left, int[] right) {
int[] newArr = new int[left.length + right.length];
int idx = 0;
int lIdx = 0;
int rIdx = 0;
while ((lIdx < left.length) && (rIdx < right.length)) {
if (left[lIdx] > right[rIdx]) {
newArr[idx] = right[rIdx];
rIdx++;
idx++;
} else {
newArr[idx] = left[lIdx];
lIdx++;
idx++;
}
}
if (lIdx == left.length) {
while (rIdx < right.length) {
newArr[idx] = right[rIdx];
rIdx++;
idx++;
}
} else {
while (lIdx < left.length) {
newArr[idx] = left[lIdx];
lIdx++;
idx++;
}
}
return newArr;
}
}[1, 2, 3, 4, 5, 6, 7]
- Divide 과정인 merge_sort_divide()함수와 Merge 과정인 merge_sort_merge()함수로 나뉘어져 있다
5. 퀵 정렬(Quick Sort)
- 병합 정렬과는 반대로 Divide단계에서 중요한 작업들을 전부 수행하고 Merge단계에서는 아무 것도 하지 않는다
- Pivot이라는 기준값을 사용하며 오름차순 정렬 시 Pivot보다 작은 값은 왼쪽에, Pivot보다 큰 값은 오른쪽에 위치시킨다
- 1회 작업 후 Pivot을 기준으로 정렬되지 않은 두 그룹이 나누어지면 다시 각 그룹에서 같은 정렬을 반복한다
- 자료 내에서 정렬이 진행되므로 추가적인 메모리가 필요없다 ( 공간복잡도 O(n) )
알고리즘 진행 순서
* 입력된 자료에서 하나의 원소를 고르고 Pivot이라고 부르기로 한다 (코드에선 마지막 값으로 정함)
* Pivot을 기준으로 왼쪽에서는 Pivot보다 작은 값을 오른쪽에는 피벗보다 큰 값으로 위치시킨다
* i = 다음 검사할 인덱스, b = big value index(Pivot보다 큰 값의 인덱스), p = Pivot, start = small value index(Pivot보다 작은 값의 인덱스)이라고 정의한다
1. 처음 위치는 i, b, start = 0 , p = end로 둔다
2. 이제 i가 한칸씩 오른쪽으로 옮겨가며 아래 조건에 따라 검사한다
2-1. list[i] < list[p]인 경우, i는 Small Group에 들어가야 하므로 list[i]와 list[b]를 swap하고 i와 b를 +1
2-2. list[i] >= list[p]인 경우, i는 Big Group에 들어가야 하므로 i를 +1
3. i가 p가 되면 list[p]와 list[b]를 swap하고 p의 위치를 리턴한다
4. p를 기준으로 나눠진 두 그룹에 다시 1-3을 반복한다
5. start와 end의 위치가 같아지면 반복을 종료한다
코드
def swap_elements(my_list, index1, index2):
"""index1과 index2를 swap하는 함수"""
my_list[index1], my_list[index2] = my_list[index2], my_list[index1]
return my_list
def partition(my_list, start, end):
"""my_list start~end까지 정렬하는 함수"""
p = end
b = start
i = start
while i < len(my_list):
if my_list[i] > my_list[p]:
i += 1
elif my_list[i] < my_list[p]:
swap_elements(my_list, i, b)
b += 1
i += 1
else:
i += 1
swap_elements(my_list, b, p)
p = b
return p
def quicksort(my_list, start, end):
"""재귀함수"""
# base case
if end - start < 1:
return
else:
p = partition(my_list, start, end)
quicksort(my_list, start, p-1)
quicksort(my_list, p+1, end)
return
array = [1,7,5,21,13,35,18]
quicksort(array, 0, len(array) - 1)
print(array)
public class 퀵정렬 {
public static void main(String[] args) {
int[] arr = new int[] { 1, 7, 5, 21, 13, 35, 18 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
/**
* arr의 start ~ end 구간까지 정렬 메서드
*/
private static int partition(int[] arr, int start, int end) {
int p = end; // 마지막을 피벗으로 설정
int i = start, b = start; //
while (i < end) {
if (arr[i] < arr[p]) {
swap(arr, i, b);
b++;
}
i++;
}
swap(arr, b, p);
p = b;
return p;
}
/**
* 재귀 메서드
*/
private static void quickSort(int[] arr, int start, int end) {
if (end - start < 1)
return;
int p = partition(arr, start, end);
quickSort(arr, start, p - 1);
quickSort(arr, p + 1, end);
}
/**
* 두 요소 스왑
*/
private static void swap(int[] arr, int a, int b) {
int cache = arr[a];
arr[a] = arr[b];
arr[b] = cache;
}
}
[1, 5, 7, 13, 18, 21, 35]
- swap_elements()는 두 인덱스 값을 바꿔주는 서브함수
- partition()은 위의 설명에 따라 i값을 한칸씩 움직이면서 p값을 기준으로 작은 값과 큰 값을 나누는 함수
- quicksort()는 end == start가 되는 base case를 구분해주고 partition()의 return인 p를 이용해 나눠서 재귀를 하는 함수
특수 정렬 (Special Sort Algorithms)
6. 계수 정렬(Counting Sort)
- 가장 작은 데이터부터 가장 큰 데이터까지 모두 담을 수 있는 길이의 리스트를 만들어 놓고 정렬한다
- 공간복잡도적으로 매우 불리하지만, 특수한 상황에서 유용한 정렬이다
- 데이터가 양의 정수일 경우, 데이터의 min, max값의 차이가 작은 경우, 중복된 값이 많은 경우에 효과적이다
- 일반적으로 값의 차이가 1,000,000(백만)을 넘지 않는 경우에 사용 가능하다
알고리즘 진행 순서
1. 정렬하고자 하는 자료 A의 가장 작은 값부터 가장 큰 값까지 모두 담길 수 있는 길이의 리스트(C)를 생성한다
2. A의 데이터를 하나씩 확인하며 A의 값 = C의 인덱스면 C의 해당 인덱스를 +1해준다
3. C를 누적합한 Modified C리스트를 만들어준다
4. 정렬된 리스트를 담을 새로운 리스트 B를 만들어준다
4. 다시 자료 A의 데이터를 하나씩 확인하며 정렬을 시작하는데, A의 값 = Modified C의 인덱스인 Modified C의 값이 A의 값이 들어갈 B의 인덱스 위치가 된다
5. 값이 들어갔다면 Modified C의 해당 값을 -1해준다
글로 쓰면 어려운데 실제 과정을 보면 쉽다. step by step으로 확인하고자 한다면 여기로
코드
array = [1, 7, 5, 21, 13, 35, 18]
count_list = [0] * (max(array) + 1)
for i in array: # 카운트 리스트의 인덱스에 해당하는 값 +1씩 카운트
count_list[i] += 1
for j in range(1, len(count_list)): # 카운트 리스트를 누적합으로 만듦
count_list[j] += count_list[j-1]
new_array = [0] * (len(array)) # 정렬된 리스트를 담을 리스트 선언
for k in array: # 기존 배열의 값을 누적합 카운트 리스트의 인덱스에서 찾는다
new_array[count_list[k] - 1] = k
count_list[k] -= 1
print(new_array)[1, 5, 7, 13, 18, 21, 35]
- C대신 count_list 리스트를 만들어서 사용했다
- 누적합된 C의 값이 A의 각 요소가 들어갈 B의 위치라고 생각하자
- 따라서 해당 B의 위치를 어떤 값이 차지했다면 다음에 같은 값이 올 자리를 위해 -1을 해주는 것이다
감상
아직 공부해야 할 알고리즘이 많다
반응형
'프로그래밍 > Computer Science' 카테고리의 다른 글
| [Overview] 01. Data Storage - (4) Data Compression (0) | 2023.07.14 |
|---|---|
| [Overview] 01. Data Storage - (3) The Binary System (0) | 2023.07.11 |
| [Overview] 01. Data Storage - (2) Main Memory (0) | 2023.07.11 |
| [Overview] 01. Data Storage - (1) Bit 그리고 Bit의 저장 (0) | 2023.07.09 |
| [알고리즘] 02. 에라토스테네스의 체 (4) | 2023.05.19 |