:: 게시판

:: 이전 게시판

- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다.
통합 규정을 준수해 주십시오. (2015.12.25.)

Date	2017/03/19 19:38:47
Name	무민
Subject	[질문] [전산지식] stable sort의 장점은 뭔가요?
https://pgr21.com/qna/99684 삭게로! 전산 공부하다가 궁금한점이 있어서 올립니다. stable , unstable sort의 개념은 알겠습니다만은 : (같은 키값을 가지는 2개의 데이터를 정렬 하면, 그 순서가 뒤바뀌지 않을때, stable sort라 한다.) stable ,unstable 나누는 이유가 뭔가요? 보기에는 stable이 더 효율적인건 같은데 ( 불필요한 교환? 을 하지 않으니) 그 외에는 다른 장점이 있을까요? + 아 그리고 heap sort가 전형적인 unstable sort라 하는데 힙소트는 bst써서 키값이 중복되면 안되지 않나요? (상관없는지.. 제가 잘못알고있는거라면 정정해주세요..)

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."

Unikys

해시 아이콘

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

무민

해시 아이콘

17/03/19 22:19

아 정말감사합니다.. 조금만생각해봐도되는건데 무릎을 치고갑니다

힙부분도 이해가 되네요

답변감사합니다!!

목록 삭게로! 맨위로

번호	제목	이름	날짜	조회
100510	[질문] 모터쇼 보신분들 질문입니다! [5]	럭키루이1849	17/04/04	1849
100509	[질문] 본인이나 지인 중에 남성 수염 제모 해보신 분 있나요? [15]	Mindow4503	17/04/04	4503
100508	[질문] 수박씨는 심으면 싹이 언제 트나요? [1]	로즈마리5493	17/04/04	5493
100507	[질문] 신차 초보 하이패스카드 문의드립니다. [2]	이선빈3980	17/04/04	3980
100506	[질문] 스마트폰 리튬이온 배터리 질문 [6]	Tyler Durden3612	17/04/04	3612
100505	[질문] 병원비 관련 질문입니다. [11]	서낙도2845	17/04/04	2845
100504	[질문] 5월 연휴 휴가를 쓸지 말지 고민입니다 [19]	칼퇴추구자3130	17/04/04	3130
100503	[질문] 투블럭 커트 망했는데 복구방법 있나요? [10]	피스~16408	17/04/04	16408
100502	[질문] 초등학생 선물용 컴퓨터 견적 문의합니다. [29]	완성형폭풍저그가되자3641	17/04/04	3641
100501	[질문] LG올데이그램, 삼성 올웨이즈9 고민입니다. [22]	IcedAmericano5161	17/04/04	5161
100500	[질문] 스타1 유닛생산할때 사운드 이해가 안가네요 [5]	purun2677	17/04/04	2677
100499	[질문] 아프리카 아동 후원 단체 추천 부탁드립니다 [4]	Koscielny3497	17/04/04	3497
100498	[질문] 삿포로오사카도쿄 10박vs 오사카도쿄 9박 [14]	Red Velvet4145	17/04/04	4145
100496	[질문] PS4 Pro와 UHD TV 문의 [5]	숨결3755	17/04/04	3755
100495	[질문] 인천 근교 맛집 문의 [5]	전력질주3479	17/04/04	3479
100494	[질문] 19)성인용 소설 연재하려면 어디가 좋을까요? [16]	하고싶은대로11388	17/04/04	11388
100493	[질문] 부동산 영업직(??)에 관련해서 질문입니다!! [7]	DeStinY....5694	17/04/04	5694
100492	[질문] 이번 하스스톤 운고로 어때보이시나요? [16]	불같은 강속구3835	17/04/04	3835
100491	[질문] 경우의수 질문입니다. 아마도 중복조합과 관련이있는것 같습니다. [3]	ski~2505	17/04/04	2505
100490	[질문] 여자친구를 미친듯이 좋아하다 보니 서운한 마음이 들때 [16]	K515628	17/04/04	15628
100489	[질문] 아이오페 맨 에어쿠션 바른 후 클렌징에 대해 질문드려요 [6]	사구삼진3252	17/04/04	3252
100488	[질문] 정장(기성복)브랜드 추천 좀 해주세요 [9]	어른이유4719	17/04/04	4719
100487	[질문] 더 추가해야할 영양제가 있을까요? [15]	cs3802	17/04/04	3802

목록 이전 다음

+ : 최근 1시간내에 달린 댓글
+ : 최근 2시간내에 달린 댓글

맨 위로

PGR21.com

통합규정 1.3 이용안내 인용