정렬알고리즘 시간복잡도 정리

Space Complexity = 필요한 메모리

stability = 정렬되기 이전의 동일한 데이터끼리의 순서를 정렬 후에도 유지하고 있는가?

---

선택정렬 : 최소값을 찾아서 제일 앞으로

삽입정렬 : 앞쪽에 데이터를 넣으면서 정렬을 시킨다 그래서 정렬된 =>이미 정렬된 부분에 이 값이 어디에 들어갈 것인가

버블정렬 : 인접한 값을 비교 교환

쉘 : 자료가 역순으로 정렬되어있어 속도가 많이 떨어지는 삽입정렬의 단점을 보완한 정렬 기법

추가 메모리 공간 소요가 없으면서도 정렬중에서도 속도가 빠르다

퀵소트 : 의 평균성능은 NlogN 이지만 최악의 경우 N^2 로 간다 => 추가 메모리를 비교적 필요로 하는 상황이 벌어진다

힙소트 : 최대값이 루트에 있다 , 추가 메모리를 필요하지 않는다 , => 힙소트 자체로 정렬 할 경우 NlogN 중에서는 비교적 조금 느린 성능을 보인다

특성을 잘 활용하는 것이 중요

병합정렬 : 순차적인 접근방식이라 순차적 접근방식에서 사용될만 한 방식=> stability 가 유지 되면서 추가 메모리가 필요 없다

Radix(기수) 들과 Distrubtion(분포수세기) 은 양의정수만을 또는 이진수를 정렬 할 수 있는 정렬 => 속도가 빠르다