728x90
🤔 정렬(sorting) 이란?
순서 없이 나열된 자료를 특정한 키 값에 따라 오름차순이나 내림차순으로 자료를 재배열하는 것이다
정렬은 자료 탐색에 있어 필수적이다
사전에서 단어를 찾을 때 알파벳 순으로 정렬되어 있어 단어를 찾는 것이 수월한 것처럼, 정렬은 자료 탐색에 있어 중요한 부분이다!
✍️ 오늘의 토픽
오늘은 알고리즘 공부를 하다보면 종종 등장하는 제자리 정렬과 안정 정렬에 대해 간단하게 알아보려고 한다!
사실 처음에는 이들이 퀵 정렬, 합병 정렬처럼 정렬 알고리즘의 종류인 줄 알았다..ㅎㅎ
그래서 정리를 하고 넘어가려고 한다!
🚶제자리 정렬 (Inplace algorithm)
추가적인 메모리 공간을 많이 필요로 하지 않거나 전혀 필요하지 않은 정렬이다
예시
- 위처럼 추가적인 메모리 공간 없이 정렬이 이뤄진다면 Inplace 알고리즘이다!
- 추가적인 공간 없이 현재 배열 안에서 정렬이 다 이뤄진다
- 위처럼 추가적인 공간이 필요한 경우, 공간복잡도가 높다
제자리 정렬의 장점
1) 공간 복잡도
- 제자리 정렬은 현재 배열 내에서만 이뤄지기 때문에 추가적인 공간이 필요하지 않다
- 따라서 공간 복잡도가 O(1)로 효율적이다
2) 공간 지역성
- 컴퓨터는 메모리 할당을 최소 단위인 페이지 기준으로 하므로 여러 페이지에 할당되면 연속되지 않은 메모리에 데이터가 저장된다
- 메모리가 연속적이지 않으면 캐시 메모리를 사용할 때 불이익이 있다
- 캐시 또한 일정 크기의 단위로 관리가 되는데, 연속적이지 않은 데이터는 캐시 메모리에 함께 관리되지 않는다
- 즉, 어떤 요소는 캐시에 있을 수도 있고 어떤 요소는 없을 수도 있다는 것이다
- 그럼 어떤 요소는 캐시에 의해 빠른 접근이 가능하고, 어떤 요소는 그렇지 못하게 되어 속도 차이가 최대 약 10배 가량 발생하게 된다
- 따라서 데이터가 연속된 메모리에 할당되면 이 연속된 데이터가 함께 캐시 메모리에 올라가게 되는데, 이를 공간 지역성이 좋다고 한다
- 제자리 정렬의 경우, 연속된 메모리를 할당받고 이후 더이상 메모리를 할당받지 않기 때문에 한 번에 연속된 메모리에서 데이터들이 저장된다
- 따라서 공간 지역성 덕분에 다른 정렬 알고리즘에 비해 좋은 성능을 보인다 → Tim sort
제자리 정렬의 종류
- 삽입 정렬
- 선택 정렬
- 버블 정렬
- 퀵 정렬
- 힙 정렬
😊 안정 정렬 (Stable Sort)
중복된 값을 입력 순서와 동일하게 정렬하는 알고리즘
안정 정렬
- 위처럼 정렬 후에도 같은 값인 요소들의 순서가 보장되는 정렬 방식이다
불안정 정렬
- 불안정 정렬은 정렬 후에 같은 값인 요소들의 순서가 보장되지 않는 정렬 방식이다
- 위처럼 값이 같음에도 불구하고 두 값의 순서가 바뀔 수 있는 것이다!
안정 정렬이 중요한 이유
- 안정 정렬을 하는 알고리즘의 순서는 항상 똑같기 때문에 항상 결과가 같음을 보장할 수 있다
- 안정 정렬은 입력 데이터에서 동일한 값이 있는 경우 출력 데이터에서 원래 순서를 유지하므로, 정렬된 데이터를 이용해 다른 작업을 수행할 때 유용하다
- 숫자를 sorting할 때는 stability가 중요하지 않을 수 있지만, 첫 문자를 기준으로 문자열 정렬하는 경우에서는 항상 안정적으로 같은 리스트가 리턴되는 것이 바람직할 것이다
- 예시
- 만약 사용자가 등록한 데이터를 날짜순으로 정렬한다고 가정해보자
- 이 때 두 사용자가 동일한 날짜에 등록을 한다면, 입력한 순서가 보장되어야 한다
- 따라서 안정 정렬을 사용하면 입력 데이터의 등록 순서가 유지되므로, 등록한 순서대로 정렬됨을 보장할 수 있다
안정 정렬의 종류
- 삽입 정렬
- 버블 정렬
- 병합 정렬
불안정 정렬의 종류
- 선택 정렬
- 퀵 정렬
- 힙 정렬
- 인트로 정렬 (퀵 정렬 + 힙 정렬)
🎰 정렬 알고리즘 비교
알고리즘 | 최선 | 평균 | 최악 | 안정 정렬 | 제자리 정렬 |
삽입 정렬 | O(n) | O(n^2) | O(n^2) | O | O |
선택 정렬 | O(n^2) | O(n^2) | O(n^2) | X | O |
버블 정렬 | O(n) | O(n^2) | O(n^2) | O | O |
퀵 정렬 | O(nlogn) | O(nlogn) | O(n^2) | X | O |
힙 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | X | O |
병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | O | X |
인트로 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | X | X |
🍏 마무리
대략적으로 정렬 알고리즘들을 비교 및 정리해보았다!
이전부터 궁금했고 한번쯤 정리하고 싶은 내용이었는데 드디어 정리해서 뿌듯하다ㅎㅎ
그럼 오늘도 야미한 코딩!
[참고]
https://hellowoori.tistory.com/48
728x90
'야미스터디 > Algorithm' 카테고리의 다른 글
[알고리즘] DFS/BFS 📌 (0) | 2022.10.02 |
---|---|
[알고리즘] Tree 구조 📌 (1) | 2022.09.13 |
[알고리즘] 동적 계획법(DP) 📌 (0) | 2022.08.28 |
[알고리즘] 빅 오(Big-O) 표기법 📌 (0) | 2022.08.26 |
[알고리즘] 시간 복잡도 vs 공간 복잡도 📌 (2) | 2022.08.26 |
댓글