혼새미로의 블로그

[실험환경] CPU : AMD Ryzen 7 1700 8-Core Processor Memory : 32.0 GB OS : Windows 10 Pro 데이터 개수 : 2천만개 ~ 3억 2천만개 스레드 개수 : 16개 값의 범위 : 0 ~ 1,000,000,000 [분석] 데이터 개수가 적을 때는 Node.js 가 가장 느린 성능을 보여주었으며, 데이터 개수가 증가함에 따라 Node.js가 Go를 제치고 더 빠른 성능을 보여주었다. Node.js는 멀티스레드를 사용하기 위해 worker_thread를 사용하는데, 각 스레드들이 수행할 작업이 적힌 스크립트 파일 (js)을 읽어서 수행하기 때문에 초반에 지연이 걸리게 되었다. 모든 경우에서 C++가 가장 빠른 속도를 보여주었다. 데이터 개수가 1억 6천만개 ..

재귀 없는 퀵정렬을 JS와 C++로 구현하면서 수행속도를 측정하고자 하였다. C++은 정수형 타입이더라도 1바이트, 2바이트, 4바이트, 8바이트로 개발자가 선택하여 사용해야 하는 반면, JS는 정수형과 실수형 타입 모두 number로 사용되고 있다. 다만, JS의 경우 ArrayBuffer를 통해 원하는 바이트 크기의 버퍼를 생성할 수 있고, Int32Array() 함수로 해당 버퍼를 래핑하여 배열 원소의 크기를 4바이트로 사용할 수 있다. [기본 배열 사용시] JS에서 1억개 할당 시 기본 배열은 최대 6.8GB의 메모리 공간을 차지하였다. 정렬 시 시간은 13.452초 소요되었다. 메모리 할당 시간은 36.656초 소요되었다. [고정 크기 배열 사용시] JS에서 1억개 할당 시 고정 크기 배열은 4..

실험환경 값의 범위 : 0~1억 데이터 개수 : 천만개 ~ 3천만개 반복횟수 : 3회 Note : 합병정렬은 기본 배열의 두배 크기로 메모리 공간을 사용합니다. 실험결과 1000만 1500만 2000만 2500만 3000만 기본정렬 4.16초 6.845초 9.142초 11.421초 14.021초 합병정렬 2.632초 3.881초 5.225초 6.589초 8.358초 퀵정렬 2.129초 3.172초 4.261초 5.487초 6.557초 /** INFO: 파라미터 만큼 배열을 생성하고 랜덤값 입력 */ function generateRandomArray(numData){ let arr = new Array(numData).fill(0); for(let i=0;i= high){ //INFO: 한개밖에 없으면 ..

12345678910111213141516n = high - low + 1;b = (low + high) >> 1;//middle elementif (n>7) { a = low; c = high; if (n > 40) { d = n >> 3; a = MED3(a, a + d, a + 2 * d); b = MED3(b - d, b, b + d); c = MED3(c - 2 * d, c - d, c); } b = MED3(a, b, c);}if (b != high) { tmp = arr[high]; arr[high] = arr[b]; arr[b] = tmp;}Colored by Color Scriptercs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include #define N 10000000#define R 100000#define STKSIZE N unsigned int arr[N]; int top = 0;int stack[STKSIZE]; void init_stack() { top = 0;} void push(int i) { if (top 0) { p = arr[r]; i = l - 1; j = r; while (1) { while (arr[++i]..

제가 알고 있기로 정렬 알고리즘의 복잡도는 nlogn 이하로 나올 수 없다고 알고 있습니다. 다름이 아니라 궁금한건 퀵정렬과 힙정렬의 복잡도는 각각 nlogn이고 최악의 경우 퀵정렬은 n^2, 힙정렬은 nlogn으로 알고 있습니다. 최악의 상황까지 고려했을 때는 힙정렬이 훨씬 좋아보이는데 실제 돌려보면 퀵정렬이 퍼포먼스가 더 좋게 나옵니다. 왜 퀵정렬이 더 빠른지 궁금하고 덧붙여서 퀵정렬과 힙정렬의 차이점에 대해 자세히 알고 싶습니다. ---------------------------------------------- 퀵정렬은 배열구조를 그대로 이용할 수 있는 특징이 있습니다. 알고리즘에 상관없이 계산에 필요한 데이터를 다루는 과정은 반드시 필요합니다. 퀵정렬이 배열구조를 그대로 쓸 수 있다는 것은 데이..

퀵정렬 실행파일과 소스입니다. 자유롭게 사용하세요