제자리 정렬 & 안정 정렬

🤔 정렬(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

[정렬 알고리즘(sorting algorithm)] 1. 정렬(sorting)의 뜻, 정렬 알고리즘 분류 방법 및 성능 비교

https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=wjdwoaud159&logNo=222365210954&categoryNo=0&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView 

[Algo] 안정 정렬 stable sort, 제자리 정렬 in-place sort