1. 선택정렬 📕
- 선택정렬은 작은수를 뽑기해서 바꿔준다 생각하면 편한 알고리즘입니다.
1. Logic
- 주어진 배열 중에서 최솟값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체해준다.
- 맨 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체해준다.
- 하나의 원소만 남을때까지 1~3 순서를 계속 반복해준다.
2. code
def selectionSort(input):
for i in range(len(input) - 1):
# assume the min is the first element
idx_min = i
j = i + 1
# test against elements after i to find the smallest
while j < len(input):
if(input[j] < input[idx_min]):
# found new minimum; remember its index
idx_min = j
j = j + 1
if idx_min is not i:
# swap
input[idx_min], input[i] = input[i], input[idx_min]
return input3. 시간 복잡도
시간 복잡도를 계산한다면 다음과 같다 = O(n²)
- 비교 횟수: 두 개의 for문 루프의 실행 횟수
- 외부 루프: (n-1)번
- 내부 루브: n-1, n-2, ... , 2, 1 번
T(n) = (n-1) + (n-2) + ... + n(n-1) / 2 = O(n²)
2. 삽입정렬 📙
1. Logic
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해 자신의 위치를 찾아 삽입해 정렬을 완성합니다.
처음 key 값은 두 번째 자료부터 시작합니다.
2. code
def insertion_sort(input):
for idx, valueToInsert in enumerate(input):
# select the hole position where number is to be inserted
holePosition = idx
# check if previous no. is larger than value to be inserted
while holePosition > 0 and input[holePosition-1] > valueToInsert:
input[holePosition - 1], input[holePosition] = input[holePosition], input[holePosition-1]
holePosition = holePosition - 1
return input3. 시간 복잡도
시간 복잡도를 계산한다면 다음과 같다
- 최선의 경우 = O(n)
- 비교 횟수
- 이동 없이 1번의 비교만 이루어진다.
- 외부 루프: (n-1)번
- 최악의 경우(입력 자료가 역순일 경우) = O(n²)
- 비교 횟수
- 외부 루프 안의 각 반복마다 i번의 비교 수행
- 외부 루프: (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n²)
3. 버블정렬 📒
- 버블정렬은 서로 인접한 두 원소를 검사해 정렬하는 알고리즘입니다.
1. Logic
첫 번째 자료와 두번째 자료를, 두번째와 세번째, 세번째와 네번째, ... 이런식으로 마지막-1번쨰와 마지막 자료를 검사하면서 정렬하는 알고리즘입니다.
2. code
def bubblesort(alist):
for i in range(len(alist)-1):
for j in range(len(alist)-1):
if alist[j] > alist[j+1]:
alist[j], alist[j+1] = alist[j+1], alist[j]
return alist3. 시간 복잡도
시간 복잡도를 계산한다면 다음과 같다
- 최선, 평균, 일반의 경우 다 똑같다 = O(n)
4. 합병 정렬 📗
- 합병 정렬은 분할 정복 알고리즘중 하나입니다.
1. Logic
분할 정복 이란
- 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결 해 나가는 전략입니다. 그리고 합병 정렬은 다음의 단계들로 이루어집니다.
1. 분할(Devide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
- 합병정렬 알고리즘 과정 설명
1. 리스트의 길이가 0 or 1이라면 이미 정렬된 것으로 본다.
2. 그렇지 않은 경우라면, 정렬되지 않은 리스트를 절반으로 나눠 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
2. code
def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf): # 분할 정렬된 list의 합병
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i += 1
else:
alist[k]=righthalf[j]
j += 1
k += 1
while i < len(lefthalf): # 남아 있는 값들 일괄복사
alist[k]=lefthalf[i]
i += 1
k += 1
while j < len(righthalf): # 남아 있는 값들 일괄복사
alist[k]=righthalf[j]
j += 1
k += 1
print("Merging ",alist)
# --------출력을 위한 코드입니다--------- #
alist = [6,2,4,1,3,7,5,8]
mergeSort(alist)
print(alist)3. 시간 복잡도
시간 복잡도를 계산한다면 다음과 같다 = O(nlog₂N)
- 분할 단계
- 비교 연산과 이동 연산이 수행되지 않는다.
- 합병 단계
- 비교 횟수
- 순환 호출의 깊이 = log₂N
- 각 합병 단계의 비교 연산 = 최대 n번
순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = nlog₂N
5. 퀵 정렬 📘
- 퀵 정렬은 분할 정복 알고리즘 중 하나, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법입니다.
1. Logic
- 퀵정렬 알고리즘 과정 설명
1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
- 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다.
- 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
- 리스트의 크기가 0이나 1이 될 때까지 반복한다.
자세하게 다시 말해보자면 퀵정렬은 다음의 단계들로 이루어져 있다.
- 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
- 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
2. 퀵정렬 알고리즘 예제
- 피벗 값을 입력 리스트의 첫 번째 데이터로 하자.
- 2개의 인덱스 변수(low, high)를 이용해서 리스트를 두 개의 부분 리스트로 나눈다.
- 1회전: 피벗이 5인 경우,
- low는 왼쪽에서 오른쪽으로 탐색해가다가 피벗보다 큰 데이터(8)을 찾으면 멈춘다.
- high는 오른쪽에서 왼쪽으로 탐색해가다가 피벗보다 작은 데이터(2)를 찾으면 멈춘다.
- low와 high가 가리키는 두 데이터를 서로 교환한다
- 이 탐색-교환 과정은 low와 high가 엇갈릴 때까지 반복한다.
- 2회전: 피벗(1회전의 왼쪽 부분리스트의 첫 번째 데이터)이 1인 경우,
- 위와 동일한 방법으로 반복한다
- 3회전: 피벗(1회전의 오른쪽 부분리스트의 첫 번쨰 데이터)이 9인 경우,
- 위와 동일한 방법으로 반복한다.
3. code
def quick_sort(list, start, end):
# 하위 목록에 하나의 항목이있을 때까지 반복
# 알고리즘이 in-place 공간을 사용하기 때문에 len(list)를 사용할 수 없습니다.
# 따라서 sublist에 start, end를 사용합니다.
if start < end:
# 분할 방법을 사용하여 피벗 가져오기
pivot = partition(list, start, end)
# 피벗에서 왼쪽으로 정렬 재귀
quick_sort(list, start, pivot-1)
# 피벗에서 오른쪽으로 정렬 재귀
quick_sort(list,pivot+1, end)
return list
def partition(list, start, end):
# 최종 품목을 초기 피벗으로 사용
pivot = end
# 시작을 초기 벽 인덱스로 사용
wall = start
left = start
# 왼쪽 항목이 목록 끝에 도달 할 때까지 반복
while left < pivot:
# 왼쪽 항목이 피벗보다 작으면 왼쪽 항목을 벽으로 바꾸고 벽을 오른쪽으로 이동
# 이렇게하면 피벗보다 작은 항목이 벽에서 왼쪽으로 유지되고
# 피벗보다 큰 항목은 벽에서 오른쪽으로 유지됩니다.
if list[left] < list[pivot]:
list[wall], list[left] = list[left], list[wall]
wall = wall + 1
left = left + 1
# 목록 끝을 왼쪽으로 치면 피벗을 벽으로 바꿉니다.
list[wall], list[pivot] = list[pivot], list[wall]
# 벽의 왼쪽이 벽보다 작은 항목입니다.
# 피벗의 오른쪽은 벽보다 큰 항목입니다.
# 벽은 새로운 피벗입니다.
pivot = wall
return pivot4. 시간 복잡도
시간 복잡도를 계산한다면 다음과 같다
- 최선의 경우 = O(N*log₂N)
- 비교 횟수
- 순환 호출의 깊이 = log₂N
- 각 순환 호출 단계의 비교 연산 = 평균 n번
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.
- 순환 호출의 깊이 X 각 순환 호출 단계의 비교 연산 = N*log₂N
- 최악의 경우(입력 자료가 역순일 경우) = O(n²)
= 리스트가 계속 불균형하게 나눠지는 경우(특히, 이미 정렬된 리스트에 대해 퀵 정렬을 실행하는 경우)
- 비교 횟수
- 순환 호출의 깊이 = n
- 각 순환 호출 단계의 비교 연산 = 평균 n 번
- 순환 호출의 깊이 X 각 순환 호출 단계의 비교 연산 = n²
- 평균의 경우 = O(N*log₂N)
퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문이다.
6. 정렬 알고리즘 시간복잡도 비교
- 단순하지만 비효율적인 방법
삽입 정렬, 선택 정렬, 버블 정렬- 복잡하지만 효율적인 방법
퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬
