lyzqm   7년 전

quick sort로 구현했는데 시간초과가 나왔습니다..

다른 분들이랑 다를게 없는거 같은데 pivot을 중간으로 잡아서 그런걸까요?

도와주세요

chogahui05   7년 전

퀵 소트 알고리즘은 가져다 쓰시는 게 현명하지 않을까 싶네요.

pivotting 하는 방법은 생각 외로 조금 있긴 한데요. 난수는 잘 모르겠습니다.

구현하기 어렵기도 해서 (솔직하게 말해서) 쓸 지 의문이고요.


중위법은 괜찮습니다.


이건

왼쪽 값, 오른쪽 값, 중앙 값 3개를 가지고 비교합니다.

예를 들어서

1 2 3 4 5 6 7 8 9 10 이 있다고 가정하면요.

왼쪽은 1, 중간은 5, 우측은 10이잖아요. 이 셋을 잘 정렬해서, 크기 순으로 왼쪽, 중앙, 오른쪽에 옮겨 놓습니다.


그리고 나서, 기준값을 왼쪽이나 오른쪽으로 옮깁니다. 예를 들어서 왼쪽으로 옮길 경우

5 2 3 4 1 6 7 8 9 10

이렇게 놓고 5를 기준으로 분할하는 것이지요.


퀵 정렬 코드는 디버깅이 어려워요. 간단하게 코드만 보면..

중앙값을 선택했어요. 기준 값을 선택했으면 왼쪽이나 오른쪽의 값과 바꿔서

좌측, 우측 값을 기준으로 비교해야지요. left나 right가 우측, 혹은 좌측으로 움직이면서

피벗값과 꼬일 가능성이 있어요.


정 어려우시다면 왼쪽과 우측 분할 과정을

배열 2개를 추가로 선언하셔서 넣고, 빼셔도 됩니다.

댓글을 작성하려면 로그인해야 합니다.