알고리즘
-
파이썬 정렬 알고리즘 모음 + 속도 테스트컴퓨터/파이썬 2020. 8. 10. 16:34
15개 정렬 알고리즘 소개 0. 정렬 알고리즘 속도 테스트 코드 big-O-calculator 이용 @설치 링크 import bisect import heapq import inspect from random import randint, shuffle from statistics import mean from timeit import default_timer, repeat import matplotlib.pyplot as plt from bigO import BigO from win10toast import ToastNotifier # timeit.repeat 이용 def runAlgorithm(algorithm, array, timeResults): setup_code = f"from __main__ ..
-
파이썬 Smooth Sort (부드러운 정렬 알고리즘)컴퓨터/파이썬 2020. 8. 3. 13:12
Smooth Sort 소개 : 부드러운 정렬은 길 찾기로 유명한 데이크스트라분이 1981년에 발표한 정렬 알고리즘이다. HeapSort의 변형 중 하나이며, in-place, not stable 시간 복잡도는 최고 : O($n$) = (대부분 정렬된 상태일 경우) 평균 : O($nlogn$), 최악 : O($nlogn$) 공간 복잡도는 총 O($n$), 보조(O($1$)) 특이한 점은 Leonardo number라는 수학 개념을 Heap Sort에 적용시킨 점이다. 1. Leonardo Number 피보나치 수열과 비슷한데, 다음과 같이 진행된다. $1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361 ....
-
파이썬 A* (A-star) 최단 경로 찾기 알고리즘컴퓨터/파이썬 2020. 7. 20. 16:02
A* 길 찾기 알고리즘은 1968년에 Peter Hart, Nils Nilsson, Bertram Raphael에 의해 최초 공개됐다.우선 Node 클래스는 아래와 같이 구현될 것이며, 아래 클래스를 보고 글을 읽으면 좀 더 편할 것이다.class Node: def __init__(self, parent=None, position=None): self.parent = parent # 이전 노드 self.position = position # 현재 위치 self.f = 0 self.g = 0 self.h = 0ex) 노드의 현재 위치는 xy좌표계를 사용한다.start = (0, 0), end = (9,9)aSta..
-
파이썬 Introspective Sort (내성 정렬) 알고리즘컴퓨터/파이썬 2020. 7. 17. 15:31
Introspective Sort IntroSort (Introspective Sort) 인트로 정렬은, Quick Sort의 장점을 유지하면서, 최악 시나리오 O(n^2)를 해결하려 만들어진 (Quick Sort + Heap Sort + Insertion Sort) 하이브리드 알고리즘이다. (C++ 기본 정렬 알고리즘, std::sort) 모든 상황에서 시간 복잡도 : O(nlogn), 공간 복잡도는 O(logn)이며, inplace, not stable한 알고리즘이다. (in-place란, 보조 데이터 구조를 사용하지 않고, 작동하는 알고리즘) Quick Sort로 시작해서, Recursion max-depth (log(len(array)) 에 도달하면 Heap Sort로 정렬하고, 그리고, 파티션 ..
-
파이썬 array.sort(), TimSort 알고리즘컴퓨터/파이썬 2020. 7. 16. 21:34
Tim Sort 소개 (Insert + Merge) TimSort 는 파이썬, 자바, Swift, Rust stable에서 기본으로 탑재된 sort() 함수의 알고리즘이다. 최고 O(n) 시간 복잡도를 갖고, stable 하며, 다양한 데이터에 적합한 정렬 알고리즘이다. (시간 복잡도 : 최상(n), 평균(nlogn), 최악(nlogn), 공간 복잡도 : n) (이 글에서 구현된 timSort는 계산해보면 모든 케이스에서 nlogn이 나온다) (정렬 알고리즘에서 안정성(stability)란 값이 원래 순서(order)를 갖고 정렬을 할 수 있냐, 없냐이다.) TimSort 는 두 가지 정렬 알고리즘을 섞은 것인데, 바로 Insertion과 Merge이다. (Quick Sort는 unstable, Merg..