정렬, 정렬 시간복잡도

학습목표
1. 여러 종류의 정렬에 대한 시간복잡도를 요약

stable은 중복된 숫자가 원래 순서를 유지한 상태로 정렬하는지를 의미합니다.

 

In-place는 자료 구조를 그대로 두고 그 안에서 요소들의 위치를 바꾸어 정렬하는 방법입니다.

 

In-place의 반대인 Out-of-place는 모든 데이터를 자료 구조의 복사본에 옮긴 후 순서대로 배열하여 정렬하는 방법입니다.

 

Best는 정렬을 수행할 때 최선의 경우에 해당됩니다. 예를 들어 오름차순으로 정렬하는 경우의 최선의 경우는 이미 오름차순으로 정렬되어 있는 경우입니다.

 

Avg는 정렬을 수행할 때 평균적인 경우에 해당됩니다. 평균적인 경우는 보통 수들이 불규칙하게 섞여 있는 경우에 해당됩니다.

 

Worst는 정렬을 수행할 때 최악의 경우에 해당됩니다. 예를 들어 오름차순으로 정렬하는 경우의 최악의 경우는 내림차순으로 정렬되어 있는 경우입니다.

References

[부스트코스] 자바로 구현하고 배우는 자료구조