PGR21.com
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다.
통합 규정을 준수해 주십시오. (2015.12.25.)
Date 2017/03/19 19:38:47
Name 무민
Subject [질문] [전산지식] stable sort의 장점은 뭔가요?
전산 공부하다가 궁금한점이 있어서 올립니다.


stable , unstable sort의 개념은 알겠습니다만은

: (같은 키값을 가지는 2개의 데이터를 정렬 하면, 그 순서가 뒤바뀌지 않을때, stable sort라 한다.)

stable ,unstable 나누는 이유가 뭔가요?

보기에는 stable이 더 효율적인건 같은데 ( 불필요한 교환? 을 하지 않으니)

그 외에는 다른 장점이 있을까요?





+ 아 그리고 heap sort가 전형적인 unstable sort라 하는데  힙소트는 bst써서 키값이 중복되면 안되지 않나요? (상관없는지.. 제가 잘못알고있는거라면 정정해주세요..)

통합규정 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
17/03/19 22:19
수정 아이콘
아 정말감사합니다.. 조금만생각해봐도되는건데 무릎을 치고갑니다

힙부분도 이해가 되네요

답변감사합니다!!
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
99713 [질문] 헬스 보충제 종류 및 섭취방법에 대해 [8] 햄찌3856 17/03/20 3856
99712 [질문] 16년 3월 입사자인데요 18년12월까지 사용가능한 연차가 15개입니다 [17] 삭제됨4845 17/03/20 4845
99710 [질문] 10살 여자아이 선물 추천 부탁드립니다. [1] 코왕6529 17/03/20 6529
99709 [질문] ○○영어공부에 돈을 얼만큼 투자하실 수 있나요? [3] Ciara.2592 17/03/20 2592
99707 [질문] 면도기 추천 부탁드립니다 [8] 미나연3433 17/03/20 3433
99706 [질문] 트위치 유튜브 영상도네시 저작권 확인 미리 할 수 있나요? [1] HuggingStar12429 17/03/20 12429
99705 [질문] 계란후라이 맛있게 만드는법 [13] 래쉬가드5808 17/03/20 5808
99704 [질문] XBOX ONE의 매력이 어떤게 있을까요? [14] UGH!3462 17/03/20 3462
99703 [질문] 자기소개서를 쓰는데 참 답답하네요.. [17] 정어리고래3925 17/03/19 3925
99702 [질문] 직장인 영어회화 공부 어떻게 해야 할까요? [4] Tristana3662 17/03/19 3662
99701 [질문] [LOL]락스가 무조건 전승해야 플옵 진출 가능한지요? [11] 레이오네3030 17/03/19 3030
99700 [질문] 게임게시판에 있는 김영호vs김민철 경기 스포없이 볼 수 있는 방법 [6] 희열3831 17/03/19 3831
99699 [질문] 변기물 한번 내리는데 수도세가 얼마정도 나갈까요? [16] 三無19901 17/03/19 19901
99698 [질문] 연말정산 서류를 못내서 나중에 할 생각인데.. 1llionaire2074 17/03/19 2074
99697 [질문] '~~~ 천재가 된 홍대리' 시리즈 괜찮은지요...? [2] nexon3037 17/03/19 3037
99696 [질문] 경제공부를 시작하려 하는데 추천 좀 부탁드리겠습니다 [6] 기다리다2513 17/03/19 2513
99695 [질문] k팝스타 심사평 칭찬할떄 브금으로 깔리는 피아노곡이 뭘까요? [6] 레일리2275 17/03/19 2275
99694 [질문] 라이즈 오브 툼레이더 스토리가 어떤가요? [3] sungsik2785 17/03/19 2785
99693 [질문] [던파] 초보유저 질문 드려요. [8] manly_toss3280 17/03/19 3280
99692 [질문] 독산동 VSL 스튜디오 주차 가능한가요? [2] 해병쫓는사도3322 17/03/19 3322
99691 [질문] 서울에서 무엇을 하면 좋을까요? [2] 사구삼진2098 17/03/19 2098
99690 [질문] 경영 시뮬레이션 게임 질문입니다. [6] crutine2926 17/03/19 2926
99689 [질문] 똘똘똘이 방송중에 타는 자전거 시뮬레이터 게임 [1] 하나3655 17/03/19 3655
목록 이전 다음
댓글

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