퀵정렬 합병정렬..........

[dsf(183.101)]

퀵정렬이 더 빠른거아님???

시간체크해보는대.. 합병정렬이 훨씬 빨리되는대 왜그러냐..ㅡㅡ 

1만개 이상가니까 퀵은 엄청느려지네...

그래프로 나타내야되는대..퀵 너무느려서  합병은거의 0에 가까움..

[ㅅㅅㅅ(125.128)]

퀵 정렬, 합병 정렬 모두 average할 때의 수행 성능이 O(NlgN)으로 알려져 있지만 실제로는 합병 정렬이 더 성능이 좋다. 퀵 정렬의 경우 O(NlgN)이라고는 하지만 이건 꽤 많은 케이스가 그렇다는 거지 운이 나쁘면 O(N²)의 성능이 된다. 반면 합병 정렬은 평균적인 상황에서도 O(NlgN), 최악의 경우에도 O(NlgN)임을 보장하는 안정된 정렬 알고리즘에 속함. 간단히 정리해서 퀵 정렬은 합병 정렬보다 더 빠른 경우도 있기 때문에 '퀵'이라는 이름이 붙었지만 불안정해서 합병 정렬보다 훨씬 느린 경우(O(N²))가 있고 합병 정렬은 언제나 O(NlgN)임을 보장해서 퀵 정렬보다 약간 느린 경우는 있을 수 있어도 항상 엄청 빠르다.

[asd(98.212)]

개소리죠 시팔. 최악의 케이스 O(n^2) 인건 맞는데 평균적으로 퀵소트가 더 빠르다... O(n^2) 케이스도 randomized 퀵소트 안쓰면 O(n lg n) 됨.

[ㅅㅅㅅ(125.128)]

그래 병신아. 퀵 소트가 빠를 때도 있다고. 근데 종합적으로 볼 때 합병 정렬이 더 빠르잖아 ㅡㅡ

[asd(98.212)]

빠를때도 있는게 아니라 거의 항상 합병 정렬 보다 빠르다 ㅋㅋㅋㅋㅋ 거의 모든 케이스에 O(n) 인 알고리즘이 몇몇 잘 일어나지도 않는 케이스에서 O(n^3) 라고 해서 모든 케이스에 O(n^2) 인 알고리즘보다 느리다고 할거냐? ㅋㅋㅋㅋㅋ

[익명(58.239)]

ㅅㅅㅅ은 stable sort의 의미를 모르는 것 같은데.. 합병정렬이 stable sort가 맞긴 한데. 그리고 퀵소트가 평균의 경우 O(NlgN)이라는 건 말 그대로 평균의 경우, 즉 임의의 데이터를 잡고 돌렸을때 전체적으로 O(NlgN)이 나온다는 거임. 거기다가 왜 최악의 경우를 추가해서 생각하는지 모르겠네

[ㅅㅅㅅ(125.128)]

아 Stable sort의 의미가 그런 의미는 아니었지. 참. 이미 정렬된 상태를 유지하냐가 Stable sort의 개념이었는데. 미안하다. 순간 착각함. 나는 내가 틀린 말 하면 인정할 줄 아는 성격임. ㅇㅇ. 퀵 정렬의 성능이 빠를지 느릴지는 피벗을 어떤 것을 고르느냐에 따라 달린 건데 데이터의 분포를 생각할 때 대충 정규분포라고 치면 가운데 볼록한 부분일수록 성능이 빨라지겠지만 양 끝에 해당하는 최소/최대값에 가까운 값을 고를 수록 성능이 느려지겠지. 피벗을 딱 중간값을 고르는 상황이라면 제일 빠르겠지만 그것 또한 드문 케이스여서 대다수의 경우는 중간값고 극값도 아닌 애매한 값을 고르게 되어 있고 그래서 정확히 O(NlgN)이 되지는 않는다.

[ㅅㅅㅅ(125.128)]

확률 분포까지 고려해서 성능을 계산하면 답이 나올 거 같은데 모르겠다. 평균적인 경우에서는 퀵 정렬이 더 빠르니까 '퀵'이라는 이름이 붙었겠지만 종합적으로 볼 때 나는 머지 소트가 더 빠르다고 평가한다. Read operation도 더 적고.

[asd(98.212)]

확률 분포 고려해서 계산하면 O(n lg n) 나온다고 아오 답답해.

[asd(98.212)]

알고리즘 과목에서 그냥 졸았냐?

[스피드스타(211.203)]

님들 싸우지마여

[익명(58.239)]

랜덤 데이터셋의 크기가 커질 수록 quicksort의 worst case가 나올 확률은 극도로 감소. 데이터셋의 크기가 가상 메모리를 고려해야 할 정도로 커지면 합병정렬이 더 빠를 수도 있지만 1만개 정도에선 글쎄. 퀵이 그 정도로 느리면 implement가 잘못되었거나 입력 데이터셋이 worst case에 가깝거나 둘중 하나가 아닐까.

[?(66.249)]

퀵소트 시작할때 랜더마이즈하면 nlogn이잖아

[jot(39.7)]

구현땜문에 머지가 늘릴수밖에없다