퀵소트에서 파티셔닝을 어떻게 하면 좋을까요?
글쓴이: lacovnk / 작성시간: 화, 2003/10/28 - 2:03오후
퀵소트에서 pivot을 기준으로 나누게 되는데
어떻게 나누어서 저장해야 할지 모르겠습니다 :(
sort할 array를 받아서 파티셔닝 해서 다시 각각을 퀵소트로 불러주는건데
파티셔닝할때 각각의 크기를 모르니 array를 선언할수가 없지 않습니까?
그래서 생각에는
일단 pivot보다 작은 item의 개수를 센다음에, 이를 기준으로 배열을 선언하고
그다음에 파티셔닝을 해줄까 했는데
그러면 불필요하게 두번이나 for문이 돌아가는셈이니까 -_-;
속도 저하에 좀 영향이 미치지 않을까 해서요...
(어차피 상수배 - 2배 - 니까 관계가 없으려나...)
sort할 item을 확 linked list로 구현해버릴까 -_-;;;;
Forums:
파티셔닝하면서 양쪽 사이즈를 다 알게 되지 않나요..?파티셔닝이란게
파티셔닝하면서 양쪽 사이즈를 다 알게 되지 않나요..?
파티셔닝이란게 피벗 아이템을 기준으로 작은 쪽은 앞으로, 큰 쪽은 뒤로 옮기고 다시 recursive하게 퀵소트를 호출해 주는 걸 말씀하시는 거 아닌가요? 그럼 그 과정에서 양쪽 배열 사이즈도 알게 되고 그걸 넘겨주면 되는걸로 아는데 무슨 말씀이신지 잘 모르겠군요...
제가 아는 퀵소트랑 다른 건 아니겠죠...? -_-
노루가 사냥꾼의 손에서 벗어나는 것 같이, 새가 그물치는 자의 손에서 벗어나는 것 같이 스스로 구원하라 -잠언 6:5
제말은...
파티셔닝한 array를 일단 만들어야 하는데
선언할때는 크기를 모르지 않나요?
퀵소트(array) { pivot = 첫번째 원소 L=array를 파티셔닝한 왼쪽 R=array를 파티셔닝한 오른쪽 퀵소트(L) 퀵소트(R) return L+pivot+R }이런식인데
L을 어레이로 선언하려면 크기를 알아야 하는데
그러면
퀵소트(array) { pivot = 첫번째 원소 size = array중 pivot보다 작은것의 개수 L[size] 선언 R[array의 size - size] 선언 L=array를 파티셔닝한 왼쪽 R=array를 파티셔닝한 오른쪽 퀵소트(L) 퀵소트(R) return L+pivot+R }이렇게 짜야 된다면
위에 pivot보다 작은 것의 개수를 세는데 input array size만큼의 루프가 필요하고
밑에 파티셔닝할때 또 input array size만큼의 루프가 필요하니
두번을 돌리는셈이 되지 않나요?
이걸 피하고 싶은데...그럼 어떻게 해야 할까 궁금했던겁니다 :)
partition 하면서 세세요.
대답이 되었나요?
C에서 하시는 거 아닌가요?우선 퀵소트 뿐만 아니라 대부분의 소트
C에서 하시는 거 아닌가요?
우선 퀵소트 뿐만 아니라 대부분의 소트 함수들은 기본적으로 (배열, 배열 길이)의 두 가지 인자를 받습니다.
그리고 C에서는 파티셔닝한 배열의 시작 포인터만 넘겨주믄 되므로 따로 배열 선언이 필요치 않습니다.
포인터만 선언하고 끝에 다시 recursive하게 호출하는 시점에서 배열길이만 파티션 길이만큼 넘겨주면 되는 거죠.
노루가 사냥꾼의 손에서 벗어나는 것 같이, 새가 그물치는 자의 손에서 벗어나는 것 같이 스스로 구원하라 -잠언 6:5
아차차
참, 자바를 씁니다. 으음 (중요한걸 빠뜨렸군요;) )
C를 쓰면 포인터를 써서 어떻게 될것같다...는게 감이 잡히는데 :)
자바에서 배열을 쓰려면 크기를 안주고는 안되지 않나요? 으음.
Re: 아차차
그러셨군요...ㅡㅡ;;
자바라면... 편하게 하려면 따로 클래스 하나 만들고 어레이를 멤버로 하나 갖고 있는게 편할 것 같지만...
단순히 메써드 호출만으로 해결하신다면 배열, 시작 인덱스, 최종 인덱스 이렇게 세 개의 인자를 넘겨주셔야 될 것 같습니다. C에서 포인터를 넘기는 대신에 자바에선 시작 인덱스를 넘겨주는 걸루요.
노루가 사냥꾼의 손에서 벗어나는 것 같이, 새가 그물치는 자의 손에서 벗어나는 것 같이 스스로 구원하라 -잠언 6:5
댓글 달기