![[Algorithm] 정렬 1. Bubble Sort & Counting Sort](/_next/image?url=https%3A%2F%2Fblog.huns.site%2Fimgs%2Fthumbnails%2Fblog%2Fposts%2Fcomputer-science%2Falgorithm.png&w=1200&q=75)
TOC
알고리즘
알고리즘이란?
- 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법.
- 주로 컴퓨터 용어로 사용
- 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법
좋은 알고리즘
< 1순위 >
정확성 : 얼마나 정확하게 동작하는가
< 2순위 >
작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가
메모리 사용량 : 얼마나 적은 메모리를 사용하는가
<3순위>
단순성 : 얼마나 단순한가
최적성 : 더 이상 개선할 여지 없이 최적화되었는가
정렬
2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순: ascending), 혹은 그 반대의 순서대로(내림차순: descending) 재배열하는 것
< 정렬의 종류 >
버블 정렬(Bubble Sort)
카운팅 정렬(Counting Sort)
선택 정렬(Selection Sort)
퀵 정렬(Quick Sort)
삽입 정렬(Insertion Sort)
병합 정렬(Merge Sort)
Bubble Sort
- 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 정렬 방식
- 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하며 맨 마지막 자리까지 이동한다.
- 이 첫 단계가 끝나면 가장 큰 원소가 마지막 자리로 배치
- 교환하며 자리를 이동하는 모습이 거품과 같다고 해서 붙여진 이름
- 시간 복잡도 : O(n^2)
Bubble Sort의 특징
- 사용해야 하는 인덱스 범위를 잘 확인하는 것이 중요하다.
- 두 수를 비교할 때 비교하는 기준이 명확해야 한다.
- 예를 들어 비교 위치의 왼쪽 위치 인덱스는 0부터 N-2까지, 오른쪽은 1부터 N-1까지.
- 코딩이 가장 손쉽지만 수행시간이 O(n^2)이라 지양해야 한다.
Bubble Sort 과정
첫 번째 path를 마치면 가장 마지막 값이 가장 큰 값으로 정렬된다. 어떤 위치에 가장 큰 수가 있었든 인접하고 자리를 바꾸며 맨 나중으로 위치하게 된다. 두 번째 path는 맨 끝 값까지 갈 필요 없이 맨 끝에서 하나를 뺀 구간에서 첫 번째 path처럼 정렬된다. 세 번째 path는 역시 끝 2개의 값을 빼고 구간을 설정한다.
def BubbleSort(a, N): # 정렬할 배열과 배열의 크기
for i in range(N-1, 0, -1): # 정렬될 구간의 끝 결정(미정렬 구간)
for j in range(0, i): # 비교할 원소 중 왼쪽 원소의 인덱스
if a[j] > a[j+1]: # 왼쪽 원소가 더 크면
a[j], a[j+1] = a[j+1], a[j] # 오른쪽 원소와 교환
Counting Sort
- 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
- index 배열인 counts를 만들어야 하기 때문에 data 배열의 최댓값을 알아야 한다. 그것으로 counts 배열을 초기화해서 시작.
- 시간 복잡도 : O(n+k), n은 리스트 길이, k는 정수 최대값 또는 문제에 주어지는 자료값의 범위
- n이 비교적 작을 때만 가능하다.
n이 있고 k가 상수라면 시간 복잡도를 k를 제외한 O(n)으로 표시해야 하는데 Counting Sort에서 O(n+k)로 표시하는 이유는, n(자료의 개수)에 비해 k(카운트 배열 항목의 개수)가 더 큰 경우가 있기 때문이다. 예를 들면 자료의 개수는 10개를 받는데, 값의 범위가 1부터 100까지라면 count 배열의 항목 개수는 최대 100개가 되기 때문에 n에 비해 크기 때문에 무시할 수 없다.
Counting Sort 과정
-
Data에서 각 항목들의 발생 횟수를 센다. 정수 항목들로 직접 인덱스되는 Count 배열
counts에 저장한다. 이 counts는 counts[0]은 Data 배열에서 0의 개수, counts[1]은 Data 배열에서 1의 개수이다. -
counts 배열은 항목의 최대값+1 만큼 항목을 만들어준다. 그래야 값의 최댓값을 인덱스로 넣어도 IndexError가 생기지 않는다.
-
Data의 각 항목 val에 따라 counts[val]+=1 해주자. 항목의 값이 곧 인덱스가 되는 것이다.
-
이후 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 counts의 원소를 누적하여 더한다. counts 배열의 이전값과 현재값을 더한 누적값을 현재값으로 재정의한다. 이후 인덱스로써 재료로 사용된다.
-
Data 배열의 크기와 같은 정렬과 배열 TEMP를 만든다. 이 TEMP 배열은 곧 count 배열을 이용해서 정렬해나갈 배열이다.
-
Data 배열의 마지막 값부터 시작한다. 맨 끝의 값을 x라고 하면 x = Data[-1]이다. -1이 아니라 for문으로 감소시키긴 할 것이다.
-
counts[x]를 1 감소시키고 x를 TEMP[counts[x]]에 삽입. 즉, counts[x]는 그 전까지 누적해온 수들 중에 x+1 이전 마지막 x인 것이다.
-
for i in range(N-1, 0, -1)로 두면, Data를 하나씩 빼며 x를 Data[-1]로 하는 과정을 줄일 수 있다. 때문에 i를 N-1부터 0까지 줄이며 Data[i]을 x로 매번 지정해준다. 이 작업을 반복한다.
def Counting_Sort(A, B, k)
# A [] -- 입력 배열(1 to k)
# k -- 입력 배열 내 항목의 최댓값
# B [] -- 정렬된 배열
# C [] -- 카운트 배열
C = [0] * (k+1) # 입력배열의 크기보다 하나 크게 0으로 초기화(0도 세야하니까)
for i in range(0, len(A)): # 입력배열을 모두 돌며 카운트 배열에 인덱스에 1씩 추가해줌
C[A[i]] += 1
for i in range(1, len(C)): # 카운트배열을 누적값으로 바꿔줌
C[i] += C[i-1]
for i in range(len(B)-1, -1, -1): # len(A)-1로 해도 무방하다. A와 B는 미정렬/정렬 차이
C[A[i]] -= 1 # 입력 배열의 마지막 값부터 처음으로 오면서 카운트 배열에서 해당 값의 개수 빼줌
B[C[A[i]]] = A[i] # 1을 뺀 카운트 누적값 배열의 항목이 정렬 배열의 인덱스가 되고, 이 값이 입력 배열의 현재 인덱스에서의 항목 값이 됨
