정렬 알고리즘 (naive sort, insert sort, quick sort, merge sort)

알고리즘

: 어떤 문제를 해결하기 위한 정해진 절차

 

정렬 알고리즘

: 데이터를 특정 기준에 따라 순서대로 나열

---

naive sort : 선택 정렬

• 가장 작은 원소를 찾아 맨 앞으로 이동
• 그 다음 작은 원소를 찾아 두 번째로 이동
  • 위 과정의 반복
• 시간복잡도: O(n²)

L=[4,2,1,0,5,3,6]

def sort_list_naive(L):
	nlen= len(L)
	for i in range(0, nlen):
		idx = i
		for j in range(i+1, nlen):
			if L[idx]>L[j]:
				idx = j
		L[i], L[idx] = L[idx], L[i]
	return L
print(sort_list_naive(L))

---

insert sort : 삽입 정렬

• 현재 위치 이전은 정렬되어 있다 가정하고, 이후의 원소를 정렬
  • 데이터를 하나씩 확인해서 적절한 위치에 삽입
• 시간복잡도: O(n²)

L=[4,2,1,0,5,3,6]
def insert_sort(L):
		nlen = len(L)
		for i in range(1, nlen):
			for j in range(i, 0 , -1):
				if L[j]<L[j-1]:
					L[j], L[j-1] = L[j-1], L[j]
		return L
print(insert_sort(L))

---

quick sort : 퀵 정렬

• 기준 데이터(pivot) 설정, 기준보다 큰 데이터와 작은 데이터 위치 변경
• Setup
  • Pivot을 마지막 값으로 설정
  • Index 2개를 사용
    • j : 시작
    • i : 시작 -1
• 방법
  • Index j 에서의 값이 pivot 값 보다 작은 지 확인
    • Index j > pivot → j =j+1
    • Else → i=i+1 and swap index i and j
• 시간복잡도: O(nlogn)

A = [8,2,5,3,9,4,7,6,1]

def partition_list(L, start, end):
	pivot = L[end]
	i = start -1

	for j in range (start, end): #end-1
		if L[j] <pivot:
		    i = i+1
		    L[i] , L[j] = L[j], L[i]
	i=i+1
	L[i], L[end] = L[end], L[i]

	return i

def quick_sort(L, start, end):
	if end<=start:
		return L
	pivot = partition_list(L, start, end)
	quick_sort(L, start, pivot -1)
	quick_sort(L, pivot+1, end)
	
	return L

print(quick_sort(A,0,len(A)-1))

• 최악의 경우
  • 배열이 오름차순 정렬 되어있거나, 내림차순 정렬 되어있는 경우
    • ex. [1,2, … , 500] 의 경우
  • 퀵 정렬은 pivot 기준 값의 위치에 따라 수행시간의 차이가 생김
  • 최악의 경우의 시간 복잡도는 **O(n²)**이다.

import time
import random

cnt =0
L=[]
while cnt <500:
	a = random.randrange(0, 500)
	if a not in L:
		L.append(a)
		cnt = cnt+1
start = time.time()
quick_sort(L,0,len(L)-1)
end = time.time()

print(f"QUICK SORT : {end - start:.5f} sec") # 일반 퀵 정렬 소요 시간

###########
## 퀵정렬 최악의 경우
C = list(range(1,501)) # 순차적인 배열 생성

start2 = time.time()
quick_sort(C,0,len(C)-1)
end2 = time.time()

print(f"QUICK SORT (최악) : {end2 - start2:.5f} sec") # 최악의 경우

---

merge sort : 합병 정렬

• 배열을 작은 배열로 나누어서, 작은 배열에서 정렬한 뒤 합함
• 분할 정복 (divide and conquer) 활용
• 시간복잡도: O(nlogn)

B = [8,2,5,3,9,4,7,6,1]

def merge(L, R, B):
	nleft = len(L)
	nright = len(R)
	l=0
	r=0
	i=0
	while l<nleft and r<nright:
		if L[l]< R[r]:
			B[i] = L[l]
			i = i+1
			l = l+1
		else:
			B[i] = R[r]
			r=r+1
			i=i+1
	while l<nleft:
		B[i] = L[l]
		i=i+1
		l=l+1
	while r<nright:
		B[i] = R[r]
		i=i+1
		r=r+1

def merge_sort(B):
	nlen = len(B)
	if nlen <=1:
		return B
	middle = nlen>>1
	L = B[:middle]
	R = B[middle:]

	merge_sort(L)
	merge_sort(R)
	merge(L, R, B)
	return B

print(merge_sort(B))

---

 

시간 비교

• 랜덤하게 생성된 길이가 1000인 배열 이용

import time
import random

cnt =0
L=[]
while cnt <1000:
	a = random.randrange(0, 1000)
	if a not in L:
		L.append(a)
		cnt = cnt+1
start = time.time()
quick_sort(L,0,len(L)-1)
end = time.time()

print(f"QUICK SORT : {end - start:.5f} sec")