알고리즘 1 조회 (버블/삽입/퀵)

버블 정렬 : 가장 느린 정렬 방법

순차적으로 앞-뒤 2개의 데이터 쌍을 비교하여 순서를 바꿔서 정렬하는 방법 

무조건 n(n-1)/2의 비교횟수가 발생한다

 

삽입 정렬 : 

순차적으로 자료구조를 순회하면서, 순서에 어긋날 경우, 바른 위치에 바로 삽입

최대 n(n-1)/2의 비교횟수가 발생

최소 n-1의 비교횟수가 발생한다

 

퀵 정렬 : 

기준 요소 선정 -> 분할 반복 

뉴턴 메서드를 정렬에 사용하는 방법

기준 요소 선정에 따라, 그 성능이 좌우된다. 

매우 이상적인 최상의 조건인 경우 log2N번의 재귀호출로 연산이 종료된다 

각 재귀호출 마다, n번의 비교가 발생하므로

Nlog2N의 비교횟수가 발생한다. 

반대로, 최악의 경우 n(n-1)/2의 비교횟수가 발생한다 

 

GitHub - Sukmin-LanternK/Algorithm

 

C언어 stdlib.h에는 qsort()함수가 있다. 

qsort 함수를 통해서 구현도 가능하다 

void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *);