주요 알고리즘인 정렬 알고리즘에 대해 알아보자.
정렬 (Sorting) 알고리즘
- 데이터를 순서대로 정렬하는 알고리즘
버블정렬 (bubble sort)
- 서로 인접한 데이터를 비교하여 정렬하는 알고리즘 [ 버블정렬 동작방식 ]
- 앞에서 부터 두개씩 비교하여 정렬이 되어있지 않으면 스와핑하는 방식을 택한다.
알고리즘
- 1번 원소와 2번 원소를 비교, 2번 원소와 3번 원소를 비교 .. (n -1) 번 원소와 n 번 원소를 비교
즉 한 턴에서 n - 1 만큼 비교 한다. ( 이때 n은 데이터의 길이 )- 첫 번째 턴이 끝나면 가장 큰 원소가 맨 위로 정렬되기 때문에 다음 턴에는 비교해야 할 원소의 길이가 -1 된다.
- 위의 과정을 반복하여 n - 1 번의 턴을 돌면 모든 원소가 정렬된다.
- 추가적으로 swap 변수를 추가하여 복잡도를 줄일 수 있다.
파이썬으로 구현해 보기
def bubble_sort(data):
for idx1 in range(len(data) - 1):
swap = False
for idx2 in range(len(data) - idx1 - 1):
if data[idx2] > data[idx2 + 1]:
data[idx2], data[idx2 + 1] = data[idx2 + 1], data[idx2]
swap = True
# 턴이 실행되면 true로 바뀐다.
if swap == False:
break
# 스왑이 이루어 지지 않았으니 이미 정렬이 완료된 상태로 반복문을 탈출한다.
return data버블정렬의 시간복잡도는 O(n^2) 이다.
선택정렬 (selection sort)
- 제자리 정렬 알고리즘 [ 선택정렬 동작방식 ]
- 주어진 데이터 중 최솟값을 찾아 맨 앞의 값과 교환하는 방식을 택한다.
알고리즘
- 데이터 중 최솟값을 찾는다.
- 최솟값을 맨 앞에 위치한 값과 바꿔준다.
- 두번째 위치부터 위와 동일한 방법으로 정렬한다.
- n - 1 번의 턴을 돌면 정렬이 완료된다. (n = 데이터의 길이)
파이썬으로 구현해 보기
def selection_sort(data):
for stand in range(len(data) - 1):
lowest = stand # 맨 앞의 인덱스로 초기화
for idx in range(stand + 1, len(data)):
if data[lowest] > data[idx]: # 더 작은 수를 발견하면 lowest 인덱스를 바꿔준다.
lowest = idx
# 한 번 턴을 돌면 최솟값의 인덱스가 lowest에 담겨있고 이를 맨 앞과 바꿔준다.
data[lowest], data[stand] = data[stand], data[lowest]
return data선택정렬의 시간복잡도는 O(n^2) 이다.
삽입정렬 (insertion sort)
- 이미 정렬된 앞 데이터를 거슬러 올라가며 탐색하여 해당원소가 들어갈 수 있는 자리에 삽입하는 알고리즘 [ 삽입정렬 동작방식 ]
알고리즘
- 두 번째 인덱스 부터 시작한다.
data[0]의 값은 이미 정렬되어 있는 상태라고 가정한다.- 해당 인덱스 앞의 값 (이미 정렬되어 있는 값) 과 비교하여 인덱스 값이 들어갈 수 있는 위치를 찾으면 삽입한다.
- 스왑이 일어나지 않으면 더이상 앞으로 거슬러 올라가지 않아도 된다.
- 총 n -1 번의 턴을 돌면 정렬이 완료된다.
파이썬으로 구현해 보기
def insertion_sort(data):
for idx in range(len(data) - 1):
for idx2 in range(idx+1, 0, -1):
if data[idx2] < data[idx2 - 1]:
data[idx2], data[idx2 - 1] = data[idx2 - 1], data[idx2]
else:
# 스왑이 일어나지 않으면 더이상 앞의 수와 비교 필요없음
break
return data삽입정렬의 시간복잡도 역시 O(n^2) 이다.
