|
:: 게시판
:: 이전 게시판
|
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다. 통합 규정을 준수해 주십시오. (2015.12.25.)
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
17/03/19 21:13
조금 복잡한 정렬 방법들을 빼고 일반론으로 이야기하자면, stable 정렬에 해당하는 일반적인 정렬 방법은 머지, 삽입, 버블 정렬입니다. 이들은 동일 키 값에 대한 순서를 보장하지만, 메모리가 더 필요하거나(머지), 연산량을 더 많이 소모(삽입, 버블=O(n^2)) 합니다. 그런데 굳이 그러한 순서를 상관하지 않는다면 그냥 평균적으로 메모리 덜 먹고 성능이 좋은 알고리즘(예: 퀵, 힙 정렬)을 그냥 사용할 수 있습니다. 글에서는 불필요한 교환을 하지 않아서 효율적일 것 같다고 하셨지만, 순서를 보장하기 위하여 나머지 부분이 더 많이 교환되어야하는 경우(삽입, 버블 정렬)가 많습니다. 쉽게 이해하려면 그냥 순서를 보장하기 위한 제약이 걸려있다고 생각하면 조금 더 이해하기 쉬울겁니다.
stable과 unstable을 나누는 이유는 같은 키 값에 대하여 항상 같은 정렬 결과를 보여주고자 한다면 stable 정렬을 해야 합니다. 웹페이지에서 특정 데이터가 정렬된 결과를 항상 동일하게 보여줘야 한다고 할 때 unstable 정렬은 보여주는 데이터와 연관 없는 데이터가 추가되어도 웹페이지를 새로고침하면 순서가 계속 바뀔 수 있기 때문에 사용자 경험이 안 좋다고 느낄 수 있겠죠. 이러한것을 피하기 위하여 정렬할 때 그냥 unique한 또는 최대한 unique한 키 값으로 정렬하는 경우가 많습니다(예: 게시판 글번호, 시간 등). 이러면 굳이 stable, unstable을 구분할 필요가 없어지겠죠. + 힙정렬은 BST가 아니고 힙을 쓰기 때문에 키 값 중복 가능합니다. 힙과 BST는 다릅니다. (예: Min힙=모든 부모가 자식보다 작거나 같음, BST=모든 좌측 자식은 부모보다 작고 모든 우측 자식은 부모보다 큼) 참고로 읽을거리: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
|
||||||||||