# 정렬
# 가장 작은 순서부터 큰 순서대로 나열하는 것.
# 선 설명 -> 후 코딩
# 거품 정렬
# 인접한 두 항목을 비교해서 정렬하는 방식
# 항목이 거품처럼 올라오는 듯해서
# 거품 정렬입니다
list_a = [11, 3, 28, 43, 9, 4]
def bubble_sort(seq):
length = len(seq) - 1
for num in range(length, 0, -1):
for i in range(num):
if seq[i] > seq[i+1]:
seq[i], seq[i + 1] = seq[i+1], seq[i]
print(seq)
return seq
def test_bubble_sort():
seq=[4, 5, 2, 1, 6, 2, 7, 10, 13, 8]
assert(bubble_sort(seq) == sorted(seq))
print("통과")
if __name__ == "__main__":
test_bubble_sort()
>>>
[4, 2, 5, 1, 6, 2, 7, 10, 13, 8]
[4, 2, 1, 5, 6, 2, 7, 10, 13, 8]
[4, 2, 1, 5, 2, 6, 7, 10, 13, 8]
[4, 2, 1, 5, 2, 6, 7, 10, 8, 13]
[2, 4, 1, 5, 2, 6, 7, 10, 8, 13]
[2, 1, 4, 5, 2, 6, 7, 10, 8, 13]
[2, 1, 4, 2, 5, 6, 7, 10, 8, 13]
[2, 1, 4, 2, 5, 6, 7, 8, 10, 13]
[1, 2, 4, 2, 5, 6, 7, 8, 10, 13]
[1, 2, 2, 4, 5, 6, 7, 8, 10, 13]
통과# 선택정렬
# 리스트에서 가장 크거나 작은 항목은 찾아서 첫번째 항목과 위치를 바꿉니다.
# 그다음 항목을 찾아서 두번째 항목과 위치를 바꿉니다.
# 리스트 끝까지 과정이 반복됩니다.
list_a = [11, 3, 28, 43, 9 , 4]
def selection_sort(seq):
length = len(seq)
for i in range(length-1):
min_j = i
for j in range(i+1, length):
if seq[min_j] > seq[j]:
min_j = j
seq[i], seq[min_j] = seq[min_j], seq[i]
print(seq)
return seq
def test_selection_sort():
assert(selection_sort(list_a) == sorted(list_a))
print("테스트 통과")
if __name__ == "__main__":
test_selection_sort()
>>>[3, 11, 28, 43, 9, 4]
[3, 4, 28, 43, 9, 11]
[3, 4, 9, 43, 28, 11]
[3, 4, 9, 11, 28, 43]
[3, 4, 9, 11, 28, 43]
테스트 통과
# 삽입정렬
# 배열 맨 처음 정렬된 부분에 정렬되지 않은 다음 항목을 반복적으로
# 삽입하는 방식입니다.
def insertion_sort(seq):
for i in range(1, len(seq)):
j = i
while j > 0 and seq[j - 1] > seq[j]:
seq[j-1], seq[j] = seq[j], seq[j-1]
j -= 1
print(seq)
return seq
def test_insertion_sort():
seq = [11, 3, 28, 43, 9, 4]
assert(insertion_sort(seq) == sorted(seq))
print("테스트 통과!")
if __name__ == "__main__":
test_insertion_sort()
>>>
[3, 11, 28, 43, 9, 4]
[3, 11, 28, 43, 9, 4]
[3, 11, 28, 43, 9, 4]
[3, 9, 11, 28, 43, 4]
[3, 4, 9, 11, 28, 43]
테스트 통과!# 놈정렬
# 앞으로 이동해서 잘못 정렬된 값을
# 찾은 후 올바른 위치로 값을 교환하며
# 뒤로 이동합니다.
def gnome_sort(seq):
# 값을 찾아줄 변수
i = 0
# 변수가 내가 찾고자하는 리스트의 길이보다
# 작을때만 무한반복
while i < len(seq):
# 만약에 인덱스가 0 또는
# 현재 인덱스보다 전 인덱스가 더 작으면
# 현재 인덱스 + 1
if i == 0 or seq[i-1] <= seq[i]:
i += 1
print(seq, i)
# 그게 아니라 i도 0보다 크고, 현대 인덱스 전 인덱스보다 크다면
# 현재 인덱스 - 1
else:
seq[i], seq[i-1]= seq[i-1], seq[i]
i -= 1
print(seq, i)
# 출력
# print(seq)
return seq
def test_gnome_sort():
seq=[5, 3, 2, 4]
assert(gnome_sort(seq) == sorted(seq))
print("테스트 통과!")
if __name__ == "__main__":
test_gnome_sort()
>>>
[5, 3, 2, 4] 1
[3, 5, 2, 4] 0
[3, 5, 2, 4] 1
[3, 5, 2, 4] 2
[3, 2, 5, 4] 1
[2, 3, 5, 4] 0
[2, 3, 5, 4] 1
[2, 3, 5, 4] 2
[2, 3, 5, 4] 3
[2, 3, 4, 5] 2
[2, 3, 4, 5] 3
[2, 3, 4, 5] 4
테스트 통과!# 카운트 정렬
# 작은 범위의 정수를 정렬할 때 사용합니다.
# 숫자 발생 횟수를 계산하는 누적 카운트를 사용하며
# 누적 카운트를 갱신해서 순서대로 숫자를
# 직접 배치하는 방식입니다.
from collections import defaultdict
# 딕셔너리에서 기본적인 형식은 딕셔너리이다.
# collections.defaultdict 모듈에서 제공하는
# 추가적인 딕셔너리 타입니다.
# 내장 딕셔너리의 모든 연산좌 메서드를 사용할 수 있습니다.
pairs = {("a", 1), ("b", 2), ("c", 3)}
d1 = defaultdict(list)
for key, value in pairs:
d1[key].append(value)
print(d1)
>>>defaultdict(<class 'list'>, {'b': [2], 'c': [3], 'a': [1]})
def count_sort_dict(seq):
b, c = [], defaultdict(list)
for x in seq:
c[x].append(x)
print(c)
print("min =",min(c))
print("max =", max(c))
for k in range(min(c), max(c) + 1):
b.extend(c[k])
print(b)
return b
def test():
seq = [3, 5, 2, 6, 8, 1, 0, 3, 6, 2, 5, 4, 1, 5, 3]
assert(count_sort_dict(seq) == sorted(seq))
print("통과!")
if __name__ == "__main__":
test()
>>>
defaultdict(<class 'list'>, {3: [3]})
defaultdict(<class 'list'>, {3: [3], 5: [5]})
defaultdict(<class 'list'>, {3: [3], 5: [5], 2: [2]})
defaultdict(<class 'list'>, {3: [3], 5: [5], 2: [2], 6: [6]})
defaultdict(<class 'list'>, {3: [3], 5: [5], 2: [2], 6: [6], 8: [8]})
defaultdict(<class 'list'>, {3: [3], 5: [5], 2: [2], 6: [6], 8: [8], 1: [1]})
defaultdict(<class 'list'>, {3: [3], 5: [5], 2: [2], 6: [6], 8: [8], 1: [1], 0: [0]})
defaultdict(<class 'list'>, {3: [3, 3], 5: [5], 2: [2], 6: [6], 8: [8], 1: [1], 0: [0]})
defaultdict(<class 'list'>, {3: [3, 3], 5: [5], 2: [2], 6: [6, 6], 8: [8], 1: [1], 0: [0]})
defaultdict(<class 'list'>, {3: [3, 3], 5: [5], 2: [2, 2], 6: [6, 6], 8: [8], 1: [1], 0: [0]})
defaultdict(<class 'list'>, {3: [3, 3], 5: [5, 5], 2: [2, 2], 6: [6, 6], 8: [8], 1: [1], 0: [0]})
defaultdict(<class 'list'>, {3: [3, 3], 5: [5, 5], 2: [2, 2], 6: [6, 6], 8: [8], 1: [1], 0: [0], 4: [4]})
defaultdict(<class 'list'>, {3: [3, 3], 5: [5, 5], 2: [2, 2], 6: [6, 6], 8: [8], 1: [1, 1], 0: [0], 4: [4]})
defaultdict(<class 'list'>, {3: [3, 3], 5: [5, 5, 5], 2: [2, 2], 6: [6, 6], 8: [8], 1: [1, 1], 0: [0], 4: [4]})
defaultdict(<class 'list'>, {3: [3, 3, 3], 5: [5, 5, 5], 2: [2, 2], 6: [6, 6], 8: [8], 1: [1, 1], 0: [0], 4: [4]})
min = 0
max = 8
[0]
[0, 1, 1]
[0, 1, 1, 2, 2]
[0, 1, 1, 2, 2, 3, 3, 3]
[0, 1, 1, 2, 2, 3, 3, 3, 4]
[0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5]
[0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6]
[0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6]
[0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 8]
통과!# 병합 정렬
# 리스트를 반으로 나눕니다.
# 정렬안되어져 있는 리스트가 크기가 각각 1이 될때까지
# 계속 리스트를 반으로 나누어 병합 정렬 알고리즘을 호출해서
# 리스트를 정렬하고 병합니다.
"""pop()을 이용한 병합 정렬"""
def merge_sort(seq):
# 들어오는 전체 리스트의 길이가 2보다 안되면
# 1개 그대로 다시 돌려준다.
if len(seq) < 2:
return seq
# 분할
mid = len(seq) // 2
left, right = seq[:mid], seq[mid:]
if len(left) > 1:
left = merge_sort(left)
if len(right) > 1:
right = merge_sort(right)
# 병합
res = []
while left and right:
print("left = ", left)
print("right = ", right)
if left[-1] >= right[-1]:
res.append(left.pop())
else:
res.append(right.pop())
print(res)
res.reverse()
return (left or right) + res
merge_sort([4,3,6,7,3,2,6,8,8,2,3,5])
"""두 함수로 나누어서 구현합니다.
한 함수에서 배열을 나누고 또 다른 함수에서는 배열을 병합"""
def merge_sort_sep(seq):
if len(seq) > 2:
return seq
mid = len(seq) // 2
left = merge_sort_sep(seq[:mid])
right = merge_sort_sep(seq[mid:])
return merge(left, right)
def merge(left, right):
if not left or not right:
return left or right
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <=right [i]:
result.append(left[i])
i += 1
else:
result.append(right[i])
j += 1
if left[i:]:
result.extend(left[i:])
if right[j:]:
result.extend(right[j:])
print(result)
return result
>>>
left = [3]
right = [6]
[6]
left = [4]
right = [3, 6]
left = [4]
right = [3]
[6, 4]
left = [3]
right = [2]
[3]
left = [7]
right = [2, 3]
[7]
left = [3, 4, 6]
right = [2, 3, 7]
left = [3, 4, 6]
right = [2, 3]
left = [3, 4]
right = [2, 3]
left = [3]
right = [2, 3]
[7, 6, 4, 3]
left = [8]
right = [8]
[8]
left = [6]
right = [8, 8]
left = [6]
right = [8]
[8, 8]
left = [3]
right = [5]
[5]
left = [2]
right = [3, 5]
left = [2]
right = [3]
[5, 3]
left = [6, 8, 8]
right = [2, 3, 5]
left = [6, 8]
right = [2, 3, 5]
left = [6]
right = [2, 3, 5]
[8, 8, 6]
left = [2, 3, 3, 4, 6, 7]
right = [2, 3, 5, 6, 8, 8]
left = [2, 3, 3, 4, 6, 7]
right = [2, 3, 5, 6, 8]
left = [2, 3, 3, 4, 6, 7]
right = [2, 3, 5, 6]
left = [2, 3, 3, 4, 6]
right = [2, 3, 5, 6]
left = [2, 3, 3, 4]
right = [2, 3, 5, 6]
left = [2, 3, 3, 4]
right = [2, 3, 5]
left = [2, 3, 3, 4]
right = [2, 3]
left = [2, 3, 3]
right = [2, 3]
left = [2, 3]
right = [2, 3]
left = [2]
right = [2, 3]
left = [2]
right = [2]
[8, 8, 7, 6, 6, 5, 4, 3, 3, 3, 2]# 퀵정렬
# 리스트에서 기준이 되는 하나의 요소를 고르는 데 이를 피벗이라고 합니다.
# 피벗앞에는 피벗보다 작은값이오고 피벗뒤에는 피벗보다 큰값이 오도록
# 피벗을 기준으로 리스트를 둘로 나눕니다.
# 두 함수를 나누어서 구현하는 방법
def partition(seq, start, end):
pivot = seq[start]
left = start + 1
right = end
done = False
while not done:
while left <= right and seq[left] <= pivot:
left += 1
class Heap(object):
def __init__(self, data=None):
self.data = data or []
for i in range(len(data) // 2, -1, -1):
self.__max_heapify__(i)
def __repr__(self):
return repr(self.data)
def parent(self, i):
if i & 1:
return i >> 1
else:
return (i >> 1) -1
def left_child(self, i):
return (i << 1) + 1
def right_child(self, i):
return (i << 1) + 2
def __max_heapify__(self, i):
largest = i
left = self.left_child(i)
right = self.right_child(i)
n = len(self.data)
# 왼족 자식
largest = (left < n and self.data[left] > self.data[i] and left or i)
# 오른쪽 자식
largest = (right < n and self.data[right] > self.data[largest] and right or largest)
# 현재노드가 자식들보다 크다면 skip, 작다면 swap
if i is not largest:
self.data[i], self.data[largest] = self.data[largest], self.data[i]
self.__max_heapify__(largest)
def extract_max(self):
n = len(self.data)
max_element = self.data[0]
self.data[0] = self.data[n - 1]
self.data = self.data[:n - 1]
self.__max_heapify__(0)
return max_element
def insert(self, item):
i = len(self.data)
self.data.append(item)
while (i != 0) and item > self.data[self.parent(i)]:
print(self.data)
self.data[i] = self.data[self.parent(i)]
i = self.parent(i)
self.data[i] = item
# 힙정렬
# 선택정렬과 비슷합니다.
# 루트가 아닌 다른 모든 노3드는 부모 노드의 값ㄷ보다
# 작은(또는 큰)값을 갖습니다.
# 가장 작은 요소는 루트에 저장되고 루트의 하위트리에는 루트보다
# 더 큰 값들이 포함도비니다.\
# heapq
import heapq
def heapq_sort(seq):
h = []
for value in seq:
heapq.heappush(h, value)
print("heapq = ",h)
return [heapq.heappop(h) for i in range(len(h))]
heapq_sort([3,5,2,6,8,1,0,3,5,6,2])
1
# heap
def heap_sort(seq):
s = list(seq)
heap = Heap(s)
res = []
for _ in range(len(s)):
res.insert(0, heap.extract_max())
print(res)
return res
heap_sort([3,5,2,6,8,1,0,3,5,6,2])
# 그냥 맨땅에 헤딩
>>>
heapq = [3]
heapq = [3, 5]
heapq = [2, 5, 3]
heapq = [2, 5, 3, 6]
heapq = [2, 5, 3, 6, 8]
heapq = [1, 5, 2, 6, 8, 3]
heapq = [0, 5, 1, 6, 8, 3, 2]
heapq = [0, 3, 1, 5, 8, 3, 2, 6]
heapq = [0, 3, 1, 5, 8, 3, 2, 6, 5]
heapq = [0, 3, 1, 5, 6, 3, 2, 6, 5, 8]
heapq = [0, 2, 1, 5, 3, 3, 2, 6, 5, 8, 6]
[8]
[6, 8]
[6, 6, 8]
[5, 6, 6, 8]
[5, 5, 6, 6, 8]
[3, 5, 5, 6, 6, 8]
[3, 3, 5, 5, 6, 6, 8]
[2, 3, 3, 5, 5, 6, 6, 8]
[2, 2, 3, 3, 5, 5, 6, 6, 8]
[1, 2, 2, 3, 3, 5, 5, 6, 6, 8]
[0, 1, 2, 2, 3, 3, 5, 5, 6, 6, 8]
[0, 1, 2, 2, 3, 3, 5, 5, 6, 6, 8]# 퀵 정렬을 이용해서 리스트에서
# k개의 가장 큰 항목을 찾아보세요.
# list = [ 3, 10, 4, 5, 1, 8, 9, 11, 5]
# k = 3
# [9, 10, 11]
import random
def swap(seq, x, y):
seq[x], seq[y] = seq[y], seq[x]
def quick_select(seq, k, left=None, right=None):
left = left or 0
right = right or len(seq) - 1
ipivot = random.randint(left, right)
pivot = seq[ipivot]
# 피벗을 정렬 범위 밖으로 이동시킵니다.
swap(seq, ipivot, right)
swapIndex, i = left, left
while i < right:
if seq[i] < pivot:
swap(seq, i, swapIndex)
swapIndex += 1
i += 1
# 피벗의 위치를 확정합니다.
swap(seq, right, swapIndex)
# 피벗의 위치를 확인합니다.
rank = len(seq) - swapIndex
if k == rank:
return seq[swapIndex]
elif k < rank:
return quick_select(seq, k, left=swapIndex+1, right=right)
else:
return quick_select(seq, k, left=left, right=swapIndex-1)
def find_k_largest_seq(seq, k):
# k번째로 큰 값 찾기
k_largest = quick_select(seq, k)
# k번째 보다 큰 값 저장
result = []
for item in seq:
if item >= k_largest:
result.append(item)
return result
if __name__ == "__main__":
seq = [3, 10, 4, 5, 1, 8, 9, 11, 5]
k = 3
print(find_k_largest_seq(seq, k))
>>>[9, 10, 11]
반갑습니다