버블 정렬 알고리즘
버블 정렬 알고리즘은 인접한 두 요소를 비교하여 잘못된 순서일 경우 교환하는 방식으로 정렬하는 알고리즘이다. 이 과정이 배열의 끝까지 반복되며, 큰 값이 계속 뒤로 밀려나는 형태를 보인다. 이 과정을 배열이 정렬될 때까지 반복한다. 인접한 두 요소를 비교하여 교환하는 방식이라 구현이 간단하지만 최악의 경우 비교할 때마다 교환해주어 시간복잡도가 O(n^2)이 나와 비효율적인 알고리즘이다. 다음은 버블 정렬 알고리즘을 python에서 구현한 코드이다.
import sys
input=sys.stdin.readline
arr=list(map(int,input().split()))
# 맨 뒤에서부터 정렬하니까 len(arr)부터 1번째까지
for i in range(len(arr),1,-1):
# 바로 뒤의 요소와 비교해야하니 처음부터 i-2번째까지 들어가야한다.
for j in range(i-1):
# 오름차순 정렬이니까 인접한 요소 중 뒤에께 크면 교환
if arr[j]>arr[j+1]:
arr[j],arr[j+1]=arr[j+1],arr[j]
print(", ".join(map(str,arr)))
Input :
3 2 5 4 1
Sort Order
1 bubble sort later arr = 2, 3, 4, 1, 5
2 bubble sort later arr = 2, 3, 1, 4, 5
3 bubble sort later arr = 2, 1, 3, 4, 5
4 bubble sort later arr = 1, 2, 3, 4, 5
Output :
1, 2, 3, 4, 5삽입 정렬 알고리즘
삽입 정렬 알고리즘은 배열을 순차적으로 탐색하면서 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 방식이다. 삽입 정렬은 두 번째 요소부터 시작하며, 이전 요소들과 비교하여 자신의 위치를 찾아 삽입하는 알고리즘이다. 현재 요소보다 큰 요소들을 오른쪽으로 한 칸씩 밀어내고, 그 자리에 현재 요소를 삽입한다. 이미 정렬된 리스트에서 대해서는 빠르게 동작하나 그렇지 않는 경우 효율성이 상대적으로 낮은 알고리즘으로 시간복잡도는 O(n^2)이다. 다음은 삽입 정렬 알고리즘을 python에서 구현한 코드이다.
import sys
input=sys.stdin.readline
arr=list(map(int,input().split()))
# 처음 요소부터 마지막에서 두번째 요소까지만 비교하면 된다.
for i in range(len(arr)-1):
# 최소값과 최소값의 index를 저장할 변수 초기화
min_value,index=arr[i],i
# i+1번째부터 마지막까지 비교
for j in range(i+1,len(arr)):
# min_value와 비교하여 min_value보다 작은 arr[j]가 나오면
if arr[j]<min_value:
# 최소값과 index 다시 초기화
min_value,index=arr[j],j
# arr[i]와 최소값의 위치 변환
arr[i],arr[index]=arr[index],arr[i]
print(", ".join(map(str,arr)))
Input :
3 1 4 2 5
Sort Order
1 insertion sort later arr = 1, 3, 4, 2, 5
2 insertion sort later arr = 1, 2, 4, 3, 5
3 insertion sort later arr = 1, 2, 3, 4, 5
4 insertion sort later arr = 1, 2, 3, 4, 5
Output :
1, 2, 3, 4, 5퀵 정렬 알고리즘
퀵 정렬 알고리즘은 기준이 되는 피벗을 설정하고, 피벗보다 작은 값들은 피벗의 왼쪽에, 큰 값들은 피벗의 오른쪽에 위치시키는 방식으로 정렬하는 알고리즘이다. 배열에서 하나의 요소를 피벗으로 선택하여 피벗보다 작은 요소들은 피벗의 왼쪽에, 큰 요소들은 오른쪽에 위치시킨다. 이 작업이 끝난 후 피벗을 기준으로 왼쪽 부분과 오른쪽 부분에 대해 재귀적으로 동일한 작업을 반복한다. 이 알고리즘은 평균적으로 O(n log n)의 시간의 복잡도를 가지고 최악의 경우 O(n^2)의 시간 복잡도를 가지는 것을 보아 피벗을 설정하는 것이 매우 중요하다. 다음은 퀵 정렬 알고리즘을 python으로 구현한 코드이다.
import sys, random
input=sys.stdin.readline
arr=list(map(int,input().split()))
def quick_sort(array):
if len(array)<=1:
return array
else:
# 피벗을 랜덤하게 선택
pivot_index=random.randint(0,len(array)-1)
pivot=array[pivot_index]
# 피벗보다 작은 값, 같은 값, 큰 값으로 구분하여 리스트 생성
smaller=[x for x in array if x<pivot]
equal=[x for x in array if x==pivot]
bigger=[x for x in array if x>pivot]
# 피벗을 기준으로 왼쪽과 오른쪽의 리스트를 다시 퀵 정렬하여 리스트 합치기
return quick_sort(smaller)+equal+quick_sort(bigger)
arr=quick_sort(arr)
print(", ".join(map(str,arr)))
Input :
3 6 8 10 1 2 4
Output :
1, 2, 3, 4, 6, 8, 10병합 정렬 알고리즘
병합 정렬 알고리즘은 배열을 절반씩 나누어 각각을 정렬한 후, 두 개의 정렬된 배열을 병합하는 알고리즘이다. 분할 정복 알고리즘에 기반하며, 퀵 정렬 알고리즘과는 달리 안정적인 O(n log n) 성능을 보장한다. 먼저 정렬하고자 하는 배열을 더 이상 나눌 수 없을 때까지 반으로 나눈다. 이후 나눈 부분 배열을 정렬하여 병합한다. 이 병합 과정에서 정렬이 이루어진다. 이 알고리즘은 안정적인 정렬 알고리즘으로 최악의 경우에도 O(n log n) 성능을 유지한다. 다음은 병합 정렬 알고리즘을 python에서 구현한 코드이다.
import sys
input=sys.stdin.readline
arr=list(map(int,input().split()))
def merge_sort(array):
if len(array)<=1:
return array
# 원래 배열을 반으로 나누어 left, right 서브 리스트로 계속해서 분할
left=merge_sort(array[:len(array)//2])
right=merge_sort(array[len(array)//2:])
# left, right 서브 리스트를 병합하여 저장할 변수 res
res=[]
# left, right 내에서 병합시 정렬할 때 사용할 변수
left_index,right_index=0,0
# left, right 둘 중 하나의 리스트에 있는 변수를 다 사용할 때까지 반복
while left_index<len(left) and right_index<len(right):
# 작은 쪽의 값을 res에 추가하고 index를 올려준다.
if left[left_index]<right[right_index]:
res.append(left[left_index])
left_index+=1
elif left[left_index]>right[right_index]:
res.append(right[right_index])
right_index+=1
# 두 값이 같은 경우 둘다 res에 추가하고 index를 각각 올려준다.
else:
res.append(left[left_index])
res.append(right[right_index])
left_index,right_index=left_index+1,right_index+1
# 최종적으로 남은 값들을 res에 추가
res=res+left[left_index:]+right[right_index:]
# 합병 정렬한 리스트 반환
return res
arr=merge_sort(arr)
print(", ".join(map(str,arr)))
Input :
3 6 8 10 1 2 4
Output :
1, 2, 3, 4, 6, 8, 10