정렬
-
Python QuickSort 최적화에 따른 속도컴퓨터/파이썬 2020. 9. 20. 20:06
인터넷에 있는 QuickSort 중 제일 빠른 방법은 무엇일까라는 생각이 들어 테스트를 진행해보았다. (big-O-calculator와 런타임으로 비교) 결과는 다를 수 있음 (페이스북 코딩 면접 중 한 문제는 quickSort 작성이었다.) - TechLead 0. 속도 테스트 코드 from bigO import BigO lib = BigO() size = 10_000 lib.test_all(quickSort) lib.runtime(quickSort, "random", size) lib.runtime(quickSort, "sorted", size) lib.runtime(quickSort, "reversed", size) lib.runtime(quickSort, "partial", size) lib.ru..
-
파이썬 go-lang sort() 구현컴퓨터/파이썬 2020. 8. 29. 10:13
go-lang.sort() golang/go The Go programming language. Contribute to golang/go development by creating an account on GitHub. github.com 1. 소개 Go언어의 기본 정렬은 quickSort 변형을 사용하고 있다. 계산해보면, 시간 복잡도는 모든 상황에서 $O(nlog(n))$ | 공간 복잡도는 $O(1)$ Pseudo Code # Go Sort procedure sort(A : array): let maxdepth = log2(length(A) - 1) × 2 quickSort(A, 0, len(A), maxdepth) procedure quickSort(A, a, b, maxdepth): n ← b ..
-
파이썬 정렬 알고리즘 모음 + 속도 테스트컴퓨터/파이썬 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 ....
-
파이썬 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..