정렬
원소들을 번호 순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.
다른 알고리즘을 최적화하는데 중요하게 이용됨.
정규화나 의미있는 결과물을 생성하는 데 유용됨.
정렬 결과 조건
- 출력은 비 내림차순이다.
- 출력은 입력을 재배열하여 만든 순열이다.
종류
1. 버블 정렬 Bubble sort
두 인접한 데이터를 비교하여 앞 데이터가 뒤 데이터보다 크면 자리를 바꾸는 알고리즘
한 번 순회시 마지막 하나가 정렬됨.
원소들이 거품처럼 올라오는 것처럼 보여 버블 정렬
작동
1. 0번째와 1번째 비교 후 정렬
2. n-1번째와 n번째를 비교 후 정렬(두 원소를 change)
구현 코드
def bubblesort(data):
for index in range(len(data) - 1):
swap = False
for index2 in range(len(data) - index - 1):
if data[index2] > data[index2 + 1]:
data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
swap = True
if swap == False:
break
return data시간복잡도
최악 : O(n^2)
최선 : O(n) (이미 정렬된 자료에서는 1번만 순회하면 됨)
2. 선택 정렬 Selection sort
현재 위치에 맞는 자료를 찾아 위치를 교환하는 알고리즘
한 번 순회하면 가장 작은 자료가 0번째 인덱스에 위치하므로 다음 순회는 1번 인덱스부터 순회한다.
작동
1. 주어진 데이터 중 최소값을 찾음
2. 해당 최소값을 데이터 맨 앞 위치와 교체
3. 맨 앞을 제외한 나머지 데이터를 동일한 방법으로 반복
구현 코드
def selection_sort(data):
for stand in range(len(data) - 1):
lowest = stand
for index in range(stand + 1, len(data)):
if data[lowest] > data[index]:
lowest = index
data[lowest], data[stand] = data[stand], data[lowest]
return data시간복잡도
O(n^2) -> n(n-1)/2
- 배열의 크기가 작을수록 효과적임. 퀵, 병합 정렬보다 빠르게 된다.
3. 삽입 정렬 Insertion sort
모든 요소를 앞에서부터 차례대로 정렬된 자료 부분과 비교하여 자신의 위치를 찾아 삽입
인간과 가장 유사한 정렬법
작동
1. 0번 인덱스 건너 뛰고
2. 0~1번 인덱스 중 1번 인덱스가 들어갈 위치 찾기
3. 0~2번 인덱스 중 2번 인덱스가 들어갈 위치 찾기
구현 코드
def insertion_sort(data):
for index in range(len(data) - 1):
for index2 in range(index + 1, 0, -1):
if data[index2] < data[index2 - 1]:
data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
else:
break
return data시간복잡도
최악 : O(n^2)
최선 : O(n) - 완전 정렬되어있는 상태
4. 병합 정렬 Merge sort
분할 정복법 중 하나로 큰 문제를 여러 문제로 쪼갠 후 해결한 후 결과를 모아 원래 문제를 해결
쪼갠 뒤 합치는 과정에서 정렬
작동
1. 리스트를 절반으로 나눠 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
➡️ 재귀함수로 구현하게 됨
구현 코드
def mergesplit(data):
if len(data) <= 1:
return data
medium = int(len(data) / 2)
left = mergesplit(data[:medium])
right = mergesplit(data[medium:])
return merge(left, right)
def merge(left, right):
merged = list()
left_point, right_point = 0, 0
# case1 - left/right 둘다 있을때
while len(left) > left_point and len(right) > right_point:
if left[left_point] > right[right_point]:
merged.append(right[right_point])
right_point += 1
else:
merged.append(left[left_point])
left_point += 1
# case2 - left 데이터가 없을 때
while len(left) > left_point:
merged.append(left[left_point])
left_point += 1
# case3 - right 데이터가 없을 때
while len(right) > right_point:
merged.append(right[right_point])
right_point += 1
return merged시간복잡도
O(nlogn) : 총 단계 수 (logn) -> 각 단계마다 정렬 (n)
공간 복잡도 : O(n) : 원소의 개수만큼 리스트를 쪼개고 따로 저장해야함. 메모리를 팔아 수행속도를 얻음
5. 퀵 정렬 Quick sort
분할 정복.
병합 정렬과 차이점은 병합은 분할 단계에서 아무것도 하지 않고 병합시 정렬하지만, 퀵은 분할 단계에서 정렬하고, 병합시 아무것도 하지 않는다.
작동
1. 하나의 원소를 고른다. 이를 pivot이라 함
2. pivot을 기준으로 리스트를 둘로 분할
3. pivot을 기준으로 작은 원소를 모두 왼쪽으로, 큰 원소를 모두 오른쪽으로 옮긴다.
4. 왼쪽과 오른쪽 리스트에 대해 같은 방식을 적용한다.
구현코드
def qsort(data):
if len(data)<=1:
return data
left,right=list(),list()
pivot=data[0]
for index in range(1,len(data)):
if pivot > data[index]:
left.append(data[index])
else:
right.append(data[index])
return qsort(left)+[pivot]+qsort(right)시간복잡도
[참고]
