정렬
선택정렬
선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
- 주어진 리스트 중에 최솟값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
- 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
def selection(list):
length = len(list)
for i in range(length-1):
min_index = i
for j in range(i+1, length):
if list[min_index] > list[j]:
min_index = j
if i != min_index:
list[min_index], list[i] = list[i], list[min_index]
return list
버블정렬
거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 {\displaystyle O(n^{2})} O(n^{2})로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
def bubble(list):
length = len(list)
for i in range(length,0,-1):
for j in range(i):
if list[j]>list[j+1]:
list[j],list[j+1] = list[j+1], list[j]
return list
삽입정렬
삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
def insertion(list):
length = len(list)
for i in range(1,length):
curr_value = list[i]
index = i
while index > 0 and list[index-1] > curr_value:
list[index] = list[index-1]
index -=1
list[index] = curr_value
return list
재귀함수
피보나치 수열
def fibonacci(index):
if index < 2:
return index
return fibonacci(index-1) + fibonacci(index-2)
피보나치 수열 - for문
def fibonacci_con_recuresive(index):
if index <2:
return index
value = 1
prev1 = 1
prev2 = 1
for i in range(index-2):
value = prev1+prev2
prev2 = prev1
prev1 = value
return value
피보나치 수열 -다이나믹 프로그래밍
memory = [0]*101
def dynamic(index):
if index < 2:
return index
if memory[index]:
return memory[index]
else:
memory[index] = dynamic(index-1) + dynamic(index-2)
return memory[index]
퀵정렬
quick_sort_easy
- 파이썬을 이용한 퀵정렬
- 매개변수로 받은 list를 사용하는 것이 아니라 새로운 list를 생성해서 메모리 문제가 있다.
def quick_sort_pythonic(list):
# 재귀 함수의 종료 조건을 항상 먼저 쓴다.
if len(list)<=1:
return list
else:
# 피봇은 맨 앞 숫자 (*임의로 정의)
pivot = list[0]
# 피봇보다 작은 숫자들 모음
less = [i for i in list[1:] if i <= pivot]
# 피봇보다 큰 숫자들 모임
greater = [i for i in list[1:] if i > pivot]
# 재귀호출
return quick_sort_pythonic(less) + [pivot] + quick_sort_pythonic(greater)
quick_sort_classic
# partition() : 피봇을 정하고, 피봇에 따라 작은 수, 큰수로 분류 후, 피봇의 원래 자리를 리턴
def partition(list, start,end):
# 피봇값 설정
pivot = list[start]
# 앞에서부터 뒤로 가면서 pivot보다 큰 값을 찾아갈 index
left = start + 1
# 뒤에서부터 앞으로 오면서 pivot 보다 작은 값을 찾아갈 index
right = end
# pivot기준으로 분류가 다 되었는지 확인하는지 flag
# 분류가 어떻게 다 되었는지 아는가? right과 left가 교차할때
done = False
while not done :
# left는 큰 값의 인덱스를 찾는다.
while left <= right and list[left]<=pivot:
# 작은 값을 찾으면 그다음으로 넘어간다.
left += 1
while left <= right and list[right] > pivot:
right-=1
if left > right:
done = True
else:
# 분류가 안끝났으면 swap
list[right], list[left]= list[left], list[right]
# 분류 끝, 피봇을 제자리로 !!!!! 피봇은 작은 값들의 인덱스 중에서 가장 큰 값과 바꾸면 된다.
list[start], list[right] = list[right], list[start]
# 파티션의 마지막 임무 - 피봇 인덱스 넘기기
return right
# quick_sort_classic()
def quick_sort_classic(list,start,end):
# 재귀함수 종료조건
if start > end:
return list
else:
# 제자리를 찾은 피봇의 인덱스를 partition에게 받는다.
pivot = partition(list, start, end)
# 피봇보다 작은 것
quick_sort_classic(list,start, pivot -1)
# 피봇보다 큰 것
quick_sort_classic(list,pivot+1, end)
# 모든 정렬 마치고 리턴
return list
# quick_sort_classic(numbaser, 0, len(numbers-1))
# 파티션이 얼마나 둘로 잘 쪼개느나냐가 bast케이스 worst의 경우 한쪽만 움직이는 것 - 완전히 역순이거나, 정렬이되어있거나 n^2
# 시간복잡도 앤로그앤
# 캐시메모리쪽에서 사용하기 때문에 빠르다.
병합정렬(merge sort)
- 실행시간 nlon(n)
- 별도의 리스트를 만들어 사용하기 때문에 공간복잡도 O(n)
- Timsort: 삽입 + 병합 정렬 -> python sort()사용하는 알고리즘
- 적당히 작은 단위로 나눔 (적당히 = 캐시메모리 안에서 정리 될 수 있는 만큼)
- 작은 단위의 리스트에서는 삽입정렬을 진행
def merge_sort(list):
length = len(list)
# divide 상황
if length > 1:
# // 소수점 아랫자리는 버리는 연산자
# 리스트 반으로 자르기
mid = length//2
left_list = list[:mid]
right_list = list[mid:]
#length == 1이 될때까지 재귀적으로 나눈다.
merge_sort(left_list)
merge_osrt(right_list)
# divide 가 끝난 뒤, 정렬(conquer)
# i = lest_list에 사용할 인덱스
# j = right_list에 사용할 인덱스
# k = list에서 사용할 인덱스
i = 0
j = 0
k = 0
# 나뉘어진 리스트들의 len
length_left = len(left_list)
length_right = len(right_list)
# 정렬
while i < length_left and j < length_right:
if left_list[i] < right_list[j]:
list[k] = left_list[i]
i +=1
k +=1
else:
list[k] = right_list[j]
j +=1
k +=1
# 남은 숫자들 정리
while i < length_left:
list[k] = left_list[i]
i +=1
k +=1
while j < length_right:
list[k] = right_list[j]
j +=1
k +=1
return list