필요한 도움 이해 삽입 종류

Question

이 작품 (자바)를 수행하는 방법이 코드는 :

/** Move A[A.length-1] to the first position, k, in A such that there 
* are no smaller elements after it, moving all elements 
* A[k .. A.length-2] over to A[k+1 .. A.length-1]. */ 

static void moveOver (int A[]) { 
    moveOver (A, A.length-1); 
} 

/** Move A[U] to the first position, k<=U, in A such that there 
* are no smaller elements after it, moving all elements 
* A[k .. U-1] over to A[k+1 .. U]. */ 

static void moveOver (int A[], int U) { 
    if (U > 0) { 
    if (A[U-1] > A[U]) { 
     /* Swap A[U], A[U-1] */ 
    moveOver (A, U-1); 
    } 
    } 
} 

나는 나 자신을 가르치고, 온라인을 통해 갈거야 버클리 CS 클래스에서이 있어요. 그것은 숙제가 아니다 (나는 바란다. 그러나 그것은 운이 좋다). 내가 이해할 수없는 것은 다음과 같다.

A []의 숫자가 8, 2, 10, 5, 4, 12라고 가정 해 보자. 위의 내용을 사용할 때, 나는 이것을 반복하면서 추적한다.

1. 상부 가장 첨자는이 케이스 (12), U-1, 더 스왑 는
가
2. U 이제 4 (재귀 U-1) 및 수는 그것이 이상 수행되지 4 U, 또는에 5 (다른 U-1). 그들은 교환된다.
3. 4 명이 방금 올라 갔고 10 명이 교체 되었기 때문에 U는 4입니다.

내 시퀀스는 이제 8,2,4,10,5,12입니다.

내 질문은 내가 이미 통과 한 번호를 얻는 방법입니다. 테스트를 위해 위 첨자로 돌아 가지 않으면 어떻게 올라갈 수 있습니까?

나는 프로그램을 올바르게 추적하고 있고 재귀와 혼동을 느끼고 있다고 생각지 않는다. 이를 위해 스왑이 올바르게 수행되었다고 가정하십시오.

감사합니다.

자체 귀하의 추적에 관해서는

Answer 1

다음 if 조건이 그래서 재귀 호출은 지금까지 만들어진되지 않습니다, 보유하지 않기 때문에이 점 2에서 잘못된 것입니다. 재귀 당신을 혼동하는 경우

, 그것은 반복적 인 형태로 재 작성하는 데 도움이 될 수 있습니다 :

static void moveOver (int A[], int U) { 
    while (U > 0 && A[U-1] > A[U]) { 
    /* Swap A[U], A[U-1] */ 
    --U; 
    } 
} 

지금은 루프가 즉시 작은 요소가 발생으로 중단됩니다 것을 쉽게 알 수있다. 완전한 정렬 알고리즘이 되려면 더 많은 작업이 필요합니다. 어느 쪽이든, 이것은 삽입 정렬이 아닙니다. 그것은 나에게 부분적인 거품 정렬과 비슷해 보인다.

이제이 코드를 어디에서 가져 왔습니까?

Answer 2

나는 일종의

알고리즘은 실제로 단지 정렬 문제의 당신 잘못 이해하는 열쇠가 실제로 도움 이해를 삽입을 필요로하는 질문

의 제목에 숨겨진 생각 현재 요소이지만 요소가 배열에 추가 될 때마다 실행된다는 아이디어가 있습니다. 그런 식으로 어레이의 나머지 부분을 호출 할 때마다 이미 순서대로 진행됩니다. 즉, 마지막 요소의 위치를 ​​정렬하려고하는 것입니다.

예제 번호 (8, 2, 10, 5, 4, 12)를 사용하고 한 번에 하나씩 배열에 순서대로 추가/정렬하면 순서는 다음과 같습니다 (각 단계에서 정렬이 발생합니다 정확히 설명하는 방법) :

To be added   | old array  | after push  | Result (after moveOver()) 
(8, 2, 10, 5, 4, 12)| []    | [8]   | [8] 
(2, 10, 5, 4, 12) | [8]   | [8,2]   | [2,8] 
(10, 5, 4, 12)  | [2,8]   | [2,8,10]  | [2,8,10] 
(5, 4, 12)   | [2,8,10]  | [2,8,10,5]  | [2,5,8,10] 
(4, 12)    | [2,5,8,10]  | [2,5,8,10,4] | [2,4,5,8,10] 
(12)    | [2,4,5,8,10] | [2,4,5,8,10,12]| [2,4,5,8,10,12]