쉘 정렬 알고리즘에 대해서

-1

나는 abook 알고리즘을 읽고있다. 그것은 일종의 아래 쉘에서 언급쉘 정렬 알고리즘에 대해서

(우리가 증거없이 진술) 셸 정렬의 중요한 속성이 (시간 subscipt의 k)는 다음 (시간 subsciprt입니다 파일을 HK-분류하는 것이 입니다 (K-1)) hk-1-sorted는 hk-sorted로 유지됩니다. 그렇지 않은 경우 단계의 작업이 이후 단계에서 취소되기 때문에 알고리즘은 거의 가치가 없습니다.

제 질문은 위의 진술로 무엇을 의미합니까?

감사합니다.

출처

2011-09-09 venkysmarty

이전 질문을 살펴보면 다음과 같이 생각됩니다.이 "책"에서 많은 것을 우리에게 묻는 것처럼 보입니다. 아마도 당신은 당신이 더 잘 이해할 수있는 다른 것을 얻어야 할 것입니까? – quasiverse

위 진술 중 어느 부분을 이해하고 있습니까? 예를 들어, 어떤 사람이 당신에게 무엇을 말해 줄 수 있습니까? _k -sorted는 의미하지 않습니까? –

셸 정렬의 중간 단계가 안정적인 정렬이라고 말하는 것은 복잡한 방식으로 들립니다. 나는 이것에 대해 답변으로 게시하는 것에 대해 충분히 확신하지 못합니다. 저는 quasiverse에 동의하며, 학문적 전문 용어보다는 영어로 것들을 설명하는 더 좋은 책을 얻습니다. –

쉘 정렬은 다중 패스 정렬 알고리즘입니다. 그것은 특정 정수 "보폭"값 k에서 배열의 서브 세트를 정렬함으로써, 즉 어레이 내의 모든 kth 요소에만 액세스함으로써 작동한다.

처음에는 스트라이드의 큰 값이 사용되며 후속 패스의 경우이 보폭 값은 최종 패스가 보들보 (일반적으로 표준 삽입 정렬 단계 임)로 실행되고 배열이 완전히 정렬 될 때까지 감소됩니다 .

이전에 전달 된 정렬 (더 큰 보폭 값)은 나중에 통과 (더 작은 보폭 값)에 의해 보존된다는 것을 당신이 물었다. 그렇지 않은 경우 셸 정렬에 사용되는 다중 패스 방식에는 아무런 의미가 없습니다.

희망이 도움이됩니다.

출처

2011-09-09 13:48:08

쉘 정렬 알고리즘에 대해서

답변

관련 문제