자료구조에 퀵정렬에서 최악의경우는 정렬된상태에서 모든 배열의 값을 다 피벗으로 하는거라고 책에 나와잇는데
그 최악의 경우가 안되는 방법중하나가 배열의 0처음 중간 끝값중 중간값을 피벗으로 하는방법인데
어차피 이렇게해도 배열의 모든 값들이 한번씩 피벗이 되는거아닌가요? ㅠㅠ 헷갈리네요 ㅠ
왜 더 효율적이게되는지 설명 부탁드려요 ㅠㄹ
사진은 배열이 {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}이렇게 저장되있을시 정렬대상의 왼쪽 오른쪽 중간값중 중간에 해당되는값을 피벗으로 결
정해서 퀵정렬한결과 피벗의 선택 결과입니다
정렬된 상태에서 첫번째 값을 피벗으로 설정하면 깊이가 N이 되는데 가운데 값으로 하면 logN이 됨
깊이가 n이된다는 말이 무엇잇지 모르겟네요,,?ㅠ 트리가아닌데 깊이가..
이상적인건 101개 였다면 key위치를 맞추고 거길 중심으로 50개 50개 나뉘어 각각 재귀 하면 되지만
제일 앞/뒤 의 경우 101개 -> 100개 - > 99개 이런식이 되버림돠...
5개를 가운데로 하면 4개짜리 한 번 2개짜리 2번 왼쪽으로하면 4개짜리 한 번 3개짜리 한 번 2개 짜리 한 번 이런식이라 그런거 아님?
이미 답글 달렸네
1. 맥락을 잘 파악해라. 퀵소트는 element들 중에서 중앙값(median)을 피벗으로 골랐을때 nlogn성능이 보장된다. 근데 정렬전에는 찍은 값이 중앙값에 얼마나 근접했는지 알 수가 없다. 2. 그래서 나온 꼼수가 2~3개 정도 element를 무작위로 뽑아서 그 중 가운데 값을 피벗으로 삼는 것..
3. 하지만 이또한 재수없게 가장 작은놈 셋이 무작위로 뽑히면 또 망함. 어치피 그중에서 가운데놈 뽑아봤자 O(N)만큼 반복하니까... 4. 이때문에 반복 횟수를 카운팅해서 O(logN)과 비교를 함으로써 중앙값에서 얼마나 멀리 떨어졌는지 예측하는 꼼수를 또 쓰기도 하는데 점점더 얄고리즘이 복잡해지지.
아!!!덕분에 이헤됫네요ㅎㅎㅎ답글달아주신모든분들감사합니다 ㅎㅎ
이요->이오(요)
되있->돼있
우물안 개구리//되->돼