정렬 알고리즘

안정정렬(Stable Sort)란 중복된 값을 입력 순서와 동일하게 정렬하는 것을 의미한다.

중복된 값을 입력 순서와 동일하게 정렬이라는 말은 기존의 다른 요소로 정렬이 된 값을 정렬 할 때, 기존의 정렬 형태를 유지한 상태에서 정렬하는 것을 의미한다.

안정 정렬 종류

1. 삽입정렬-> 최악 시간복잡도 O(n**2)
2. 버블정렬-> 최악 시간복잡도 O(n**2)
3. 병합정렬 -> 최악 시간복잡도 O(nlogn) 메모리 n

불안정 정렬

불안정 정렬(UnStable Sort)란 중복된 값을 입력 순서와 상관없이 무작위로 뒤섞인 상태에서 정렬이 이루어 지는 것을 의미한다.

불안정 정렬 종류

1.퀵(Quick) 정렬 (최악 시간 복잡도 : O(n**2))
2. 힙(Heap) 정렬 (최악 시간복잡도 : O(nlogn))

3. 선택 정렬 (최악 시간복잡도 : O(n**2))
4. 인트로(Intro) 정렬
   퀵 정렬에 힙정렬을 더한 형태로 기본적으로 퀵정렬을 하지만 재귀가 깊어지는 경우 힙 정렬을 사용한다.
   (최악 시간복잡도 : O(nlogn)) 메모리 logn