제자리 정렬(Inplace algorithm) - goorm-6th-Als/for_study_Algorithm GitHub Wiki

제자리 정렬이란?

추가적인 메모리 공간을 많이 필요로 하지 않거나 전혀 필요하지 않은 정렬이다

예시

• 위처럼 추가적인 메모리 공간 없이 정렬이 이뤄진다면 Inplace 알고리즘이다!
• 추가적인 공간 없이 현재 배열 안에서 정렬이 다 이뤄진다

• 위처럼 추가적인 공간이 필요한 경우, 공간복잡도가 높다

제자리 정렬의 장점

• 공간 복잡도

제자리 정렬은 현재 배열 내에서만 이뤄지기 때문에 추가적인 공간이 필요하지 않다 따라서 공간 복잡도가 O(1)로 효율적이다

• 공간 지역성

• 컴퓨터는 메모리 할당을 최소 단위인 페이지 기준으로 하므로 여러 페이지에 할당되면 연속되지 않은 메모리에 데이터가 저장된다

• 메모리가 연속적이지 않으면 캐시 메모리를 사용할 때 불이익이 있다

1. 캐시 또한 일정 크기의 단위로 관리가 되는데, 연속적이지 않은 데이터는 캐시 메모리에 함께 관리되지 않는다
2. 즉, 어떤 요소는 캐시에 있을 수도 있고 어떤 요소는 없을 수도 있다는 것이다
3. 그럼 어떤 요소는 캐시에 의해 빠른 접근이 가능하고, 어떤 요소는 그렇지 못하게 되어 속도 차이가 최대 약 10배 가량 발생하게 된다

• 따라서 데이터가 연속된 메모리에 할당되면 이 연속된 데이터가 함께 캐시 메모리에 올라가게 되는데, 이를 공간 지역성이 좋다고 한다
• 제자리 정렬의 경우, 연속된 메모리를 할당받고 이후 더이상 메모리를 할당받지 않기 때문에 한 번에 연속된 메모리에서 데이터들이 저장된다
• 따라서 공간 지역성 덕분에 다른 정렬 알고리즘에 비해 좋은 성능을 보인다