퀵소트는 최악의 경우 O(N^2)이 걸립니다. 이렇게 pivot의 위치가 가운데, 첫 원소, 끝 원소 등 하나로 정해져 있으면 최악의 경우를 직접 만드는 것도 가능합니다. 자바에서 제공하는 정렬 함수는 퀵소트가 아닌 다른 정렬 알고리즘을 사용합니다.

질문자님이 구현하신 Quick Sort는 아래와 같이 같은 값이 포함되어있으면 무한 루프가 발생하여 시간초과가 나는 것으로 보이네요.

5 

1 1 5 1 1 

5 

1 3 7 9 5

@jh05013

댓글 감사합니다. 그러면 퀵소트에서 pivot은 어떤 값을 정하는것이 가장 좋은 효율을 낼까요?

@wakeupear1y

댓글 감사합니다 !! 다시 수정해야겠네요 감사합니다 ㅎㅎ

퀵소트에서 피벗을 잘 정하는 건 매우 복잡한 문제입니다. 단순히 어떤 규칙에 의해 뽑는다면 데이터의 순서를 바꿔서 여전히 O(N^2)으로 만드는 것이 가능합니다. 다양한 보완책들이 있지만, 피벗 선택을 개선하는 것만으로는 어느 정도 한계가 있고, 최악의 경우를 잘 방어하는 정책일수록 그 피벗 선택 과정에 오버헤드가 많이 생깁니다.

그래서 고안된 많은 퀵소트 업그레이드 버전 중 하나로 gcc의 std::sort가 사용하는 introsort라는 것이 있는데, 구체적인 구현 방식은 모르나 퀵소트에 삽입 정렬이 결합된 구조 정도로 보시면 됩니다. 그럼에도 불구하고 여전히 피벗 선택에 의한 불안정성이 있기에, 자바 등에서는 아예 퀵소트 계열을 포기하고 Timsort를 쓰고 있습니다.

결론은, 퀵소트를 직접 구현해서 쓰는 건 실용적이지 못합니다. 그 원리가 어떤지를 공부하는 데에 의의를 두고, 실제 정렬은 그냥 표준 라이브러리에 있는 걸 쓰시는 게 낫습니다. 정말 좋은 정렬 알고리즘을 직접 구현해보고 싶으시다면 다양한 개선된 알고리즘들을 찾아보시는 게 좋습니다.

@djm03178

좋은 댓글 감사합니다 많은걸 배워가네요 

만약 상황상 표준 라이브러리 정렬을 사용하지 못하는 경우를 대비해서 직접 퀵소트 알고리즘을 짜서 풀려고 했는데 ...

좀더 많은 공부가 필요할꺼같네요 ㅠㅠ

라이브러리를 못 쓰는 경우를 위해서라면 머지 소트를 연습해 두는 편이 낫습니다. 항상 O(nlogn)이고 전반적인 속도도 나쁘지 않습니다.

퀵 소트로만 구현하시는 경우 three of median 이라는 스킬이 이용됩니다.

three of median이란?

처음, 중간, 끝 값을 가지고 옵시다. 예를 들어서

1 2 3 4 6 7 8 9 10

이런 게 있는 경우 시작 = 1 끝 = 10 중간 = arr[(0+8)/2] = arr[4] = 6

이 중에서 중간 값을 가지고 옵니다. 그리고 1과 바꿉니다.

6 2 3 4 1 7 8 9 10

6을 피벗으로 삼아서 위 알고리즘을 수행합니다.

그런데요. 요새 c++ sort를 보면

intro sort라는 걸로 구현이 되어 있어요.

intro sort란?

Quick sort를 쓰는 건 똑같은데요. depth가 일정 수치 이상 초과하면

그것에 대해서는 Quick이 아니라 Heap sort로 돌려버립니다.

예를 들어서

1 2 3 ... 100000

을 돌린다고 쳐 보면. 이 경우에 O(n^2)쯤 걸리겠지요?

그러니까 1부터 50 정도까지만 Quick으로 소팅을 해 놓고

1 ~ 50..

51부터 10만까지는 Heap sort로 수행하는 것이죠.

Merge sort 같은 경우, stable_sort라는 녀석 안에 있는데요.

Merge의 특성상, 안정 정렬이기 때문에 그런 걸로 보이구요.

요건 내부적으로 또 파보면 기저 조건에서는 삽입 정렬을 써버립니다. 데이터 갯수 < 15 ~ 16 정도에서..

이건 함수 호출 오버헤드 때문이기도 하고.. 암튼 여러 이유가 있어요.

굳이 버블이나 선택을 안 쓰고 왜 삽입을 쓸까? 라는 의문도 가져보세요. 

궁금하시다면 찾아보셔도 무난할 거 같습니다.

P.s

Quick sort에서 pivotting 방식을 물어봤는데.. 이런 식으로 답하시는 분들도 계셨습니다..

random하게 피벗을 뽑는다~

이 경우에는 안정성도 Random이고. 수행 시간도 말 그대로 Random이기 때문에

좋지 못한 해결책입니다~

*median of three

으읔.. 영어 ㅠㅠ

뭔가 구글링 해 봐도 안 나온다 싶었는데.. ㅠㅠ

영어 공부 많이 해야 겠네요.. ㅠㅠ

random pivot 방식에서는 안정성도 Random 이고 수행 시간도 Random 이라고 말씀하셨는데, pivot 을 정하는 방법이 딱딱 정해져 있는 경우에는 항상 최악의 pivot 을 고르게끔 하는 입력을 얼마든지 줄 수 있다는 점에서 random pivot 이 안좋다 라고 말하기는 힘들 것 같습니다. (물론 random 도 정말 임의는 아니지만..) 

three of median 이 일반적으로 random pivot 보다 성능면에서 약간의 이득을 가져올 수 있는 건 맞지만 random pivot 을 사용한다고 해서 안정성이나 수행 시간이 random이 되어버린다고 주장하기는 힘들 것 같네요.

random은.. 너무..

물론 left 값을 pivot으로 줄 때 보다는 확실히

좋은 성능을 기대할 수 있는 건 맞긴 해요. 다만.. 보통 random 값을 줄 때 코드를 찾아보면

제일 작은 것 ~ 제일 큰 것 사이로 나오게끔 돌려버리던데요.

데이터가

y = log(x) 같이 뭐라고 해야 할까요? 증가하긴.. 증가하는데 기울기가 감소하는 경우.

최악의 경우가 이런 경운데.. (오름차로 정렬해버리는 경우)

O(n^2)가 되게 만들어 버리려면..

2 q q+r q+r+r2

에서 2-q >>> r>>>r2>>>r3... 이여야 하니.. 랜덤은 너무 오버친 건 맞는 거 같네요..

전 아예 그냥 중간값으로만 구현해 버립니다.. rand()도 있고.. 느리긴 좀 느리거든요.

미디언도 최악의 경우에는 O(n^2) 짜리를 만들 수 있긴 한데.. 

만들기가 그리 쉽진 않을 거 같네요. ㅎㅎ

하여튼.. 요새는 Quick + Heap을 쓰거나 Merge로 구현하심이.. 실제로 Quick 같은 경우 뎁스 초과해 버리면

Heap을 호출하는 것두.. 이유가 있어요.

원소의 대소 관계를 미리 정해 놓지 않고 처음 호출될 때마다 알맞게 정할 수 있으면, 거의 모든 퀵정렬이 O(n^2)이 걸리도록 할 수 있습니다.

http://www.cs.dartmouth.edu/~d...

음.. 데이터에서 증가의 기울기가 의미가 있나요?

그리고 random pivot의 값이 제일 작은 것과 제일 큰 것 사이에 있는 건 당연한거 아닌지요 제가 잘 못 이해한것같기도 하구요.

어쨌든 제가 말씀드리려고 했던 것은 quick sort only가 좋다 랜덤피봇이 median 보다 우월하다 

뭐 그런게 아니라 랜덤피봇 방식이라고 해서 안정성이나 실행속도가 완전 랜덤으로 산으로 가는 건 아니다 그런 거 였습니다.

사실 따지고 보면 모든 알고리즘의 실행속도는 어느 정도의 랜덤성이 있어서 Big O 표기법을 사용 하는 것이기도 하니깐요.

종이에 그림 코딩 하면서 돌려보니..

인터넷에 나와있는 미디언 방식도 데이터에 따라서는 O(n^2)가 나올 수도 있네요. (mid 위치를 랜덤하게 뽑아버리면 모를까..)

생각보다 어렵지 않게 나오네요..

물론 랜덤이 n^2가 안 나온다는 보장은 없지만.. 확률이 미디언보다는 적네요.