sorting (정렬)
정렬(sorting)이란?
어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
- 정렬은 프로그램 작성 시 빈번하게 필요로 함
- 다양한 알고리즘이 고안되어 있음. 위키피디아에 sorting algorithm 문서를 보면 거의 30개 가까이 있음
1. 버블 정렬(bubble sort)
앞에서부터 인접한 두 원소를 보면서 앞 원소가 뒤 원소보다 클 경우, 자리를 바꾸는 것을 반복함
→ 자연스럽게 제일 큰 것부터 오른쪽에 쌓이게 됨
def bubbleSort(array):
length = len(array)
for i in range(length-1):
for j in range(0, length-i-1):
if array[j] > array[j+1] :
array[j], array[j+1] = array[j+1], array[j]
1) 과정
1 - 비교 연산이 필요한 루프 범위를 설정한다
2 - 인접한 데이터 값을 비교한다
3 - swap 조건에 부합하면 swap 연산을 수행한다
4 - 루프 범위가 끝날 때까지 2~3을 반복한다
* 루프에서 swap이 한번도 일어나지 않았다면 break. (이미 정렬 완료된 것)
5 - 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다
6 - 비교 대상이 없을 때까지 1~5를 반복한다
2) 장단점
장점 : 간단한 구현
단점 : 시간 복잡도가 O(n^2)로, 다른 정렬 알고리즘보다 속도가 느린 편
3) 분석
반복문이 두개니 O(n^2), 최악은 (n*n-1)/2
완전 정렬이 되어 있으면, 최선은 O(n)
2. 삽입 정렬 (Insert sort)
이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 것
def insertionSort(arr):
for i in range(1, len(arr)):
tmp = arr[i]
j = i - 1
while j >= 0 and tmp < arr[j]:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = tmpdef insertionSort2(arr):
for i in range(len(arr)-1):
for j in range(i+1,0,-1):
if arr[j] < arr[j-1]:
arr[j],arr[j-1] = arr[j-1],arr[j]
else:
break
return arr
1) 과정
1 - 현재 idx에 있는 데이터 값을 선택한다
2 - 선택한 데이터부터 앞 데이터들과 비교해 삽입할 위치를 탐색한다(여기서 이진 탐색 등과 같은 탐색 알고리즘을 사용하면 효율 up)
3 - 삽입 위치까지 swap을 수행한다
4 - 삽입 위치에 데이터 삽입 후 idx+1 연산을 수행한다
5 - 선택할 데이터가 없을 때까지 반복한다
2) 분석
반복문이 두개니 O(n^2), 최악은 (n*n-1)/2
완전 정렬이 되어 있으면, 최선은 O(n)
3. 선택 정렬 (selection sort)
대상 데이터에서 최대나 최소 데이터를 찾아 선택해 바꾸는 정렬
def selectionSort(arr, n):
for stp in range(n):
min = stp
for i in range(stp + 1, n):
if arr[i] < arr[min]:
min = i
(arr[stp], arr[min]) = (arr[min], arr[stp])
1) 과정
1 - 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다
2 - 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap
3 - stp +1 후 남은 정렬 부분의 범위를 축소한다
4 - stp이 데이터 끝까지 갈 때까지 반복한다(남은 정렬 부분이 없을 때까지)
2) 분석
반복문이 두개니 O(n^2), 최악은 (n*n-1)/2
4. 퀵 정렬 (quick sort) - 코테에서 라이브러리 없이 구현해야 한다면, 퀵 정렬은 하지말 것
기준값(pivot)을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것
# 코드 1
def quickSort(data):
if len(data) <= 1:
return data
left,right = [],[]
pivot = data[0]
for idx in range(1,len(data)):
if data[idx] < pivot:
left.append(data[idx])
else:
right.append(data[idx])
return quickSort(left)+[pivot]+quickSort(right)# 코드 2 : list comprehension을 사용해 깔끔하게
def quickSort(data):
if len(data) <= 1:
return data
pivot = data[0]
left = [item for item in data[1:] if item < pivot]
right = [item for item in data[:1] if item >= pivot]
return quickSort(left)+[pivot]+quickSort(right)1) 과정
1 - 데이터를 분할하는 기준점(pivot)을 설정한다
2 - pivot을 기준으로 다음 a~e 과정을 거쳐 데이터를 2개의 집합으로 분리한다 (pivot을 기준으로, 작은 데이터는 왼쪽에 큰 데이터는 오른쪽에 모으는 함수를 작성한다)
a - start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다
b - end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다
c - start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start, end가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다
d - start와 end가 만날 때까지 a~c를 반복한다
e - start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교해 pivot이 가리키는 데이터가 크면 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다
3 - 분리 집합에서 각각 다시 pivot을 선정한다
4 - 분리 집합이 1개 이하가 될 때까지 과정 1~3을 반복한다
2) 분석
평균 O(nlogn)이며 최악은 O(n^2)
5. 병합 정렬 (merge sort) - 정렬 관련 문제에서 자주 등장함
가장 작은 데이터 집합으로 분할한 뒤, 병합하면서 정렬하는 것
*2개의 그룹을 병합하는 과정 : 투포인터 개념 활용(왼쪽 포인터와 오른쪽 포인터의 값을 비교해 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다)
# 코드 1
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):
i,j = 0,0
merged = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i +=1
else:
merged.append(right[j])
j +=1
while i < len(left):
merged.append(left[i])
i +=1
while j < len(right):
merged.append(right[j])
j +=1
return merged# 코드 2
def mergeSort(arr):
if len(arr) > 1:
r = len(arr)//2
leftArr = arr[:r]
rightArr = arr[r:]
mergeSort(leftArr)
mergeSort(rightArr)
i = j = k = 0
while i < len(leftArr) and j < len(rightArr):
if leftArr[i] < rightArr[j]:
arr[k] = leftArr[i]
i += 1
else:
arr[k] = rightArr[j]
j += 1
k += 1
while i < len(leftArr):
arr[k] = leftArr[i]
i += 1
k += 1
while j < len(rightArr):
arr[k] = rightArr[j]
j += 1
k += 1→ 기능을 크게 나누면 split, merge(left,right)
출처 : 바킹독, 잔재미코딩, Do it! 알고리즘 코딩테스트(Python)