제자리 정렬

Last updated - 2023년 04월 25일 Edit Source

제자리 정렬(in-place sort) : 메모리 공간과 관련된 것으로, 원소들의 개수에 비해 충분히 무시할만한 저장 공간만을 더 사용하는 정렬 알고리즘을 의미

• 주어진 공간 외에 자료구조를 이용하는 것과 같이 추가적인 공간을 사용하지 않는 정렬 알고리즘
• 약간의 추가 공간 정도는 허용한다
• 대표적인 제자리 정렬은 삽입 정렬, 선택 정렬, 버블 정렬, 힙 정렬, 퀵 정렬
• 합병 정렬은 별도의 추가적인 메모리(임시 배열)을 사용하므로 제자리 정렬 ❌
• 추가적인 메모리가 필요하다면 고려할 수 있는 것은 내부정렬, 외부정렬