Quicksort가

Question

과 같은 벡터를 반환 함 최근에 나는 R을 사용하기 시작했으며 quicksort를 구현하는 연습으로 사용하고 있습니다. "Introduction to Algorithms (3rd ed)"책을 사용하고 있습니다.

나는 RStudio을 사용하고 있으며 오류는 보이지 않지만 전달 된 것과 동일한 벡터를 반환합니다. 내 코드가 책의 의사 코드와 일치한다고 생각합니다. 들의 유사 코드는 다음과 같다 :

R에서 같은 두 가지 기능을 썼다 I보다

Partition(A, p, r) 
    x = A[r] 
    i = p - 1 
    for j = p to r - 1 
    if A[j] <= x 
     i = i + 1 
     swap(A[i], A[j]) 
    swap(A[i+1], A[r] 
    return i + 1 

Quicksort(A, p, r) 
    if p < r 
    q = Partition(A, p, r) 
    Quicksort(A, p, q - 1) 
    Quicksort(A, q + 1, r) 

: RStudio에서

partition <- function(a, p, r) { 
    x = a[r] 
    i = p - 1 
    for (j in p:(r-1)) { 
     if (a[j] <= x) { 
      i = i + 1 
      t = a[i] 
      a[i] = a[j] 
      a[j] = t 
     } 
    } 
    t = a[i+1] 
    a[i+1] = a[r] 
    a[r] = t 
    i+1 
} 

quicksort <- function(a, p, r) { 
    if (p < r) { 
     q = partition(a, p, r) 
     quicksort(a, p, q-1) 
     quicksort(a, q+1, r) 
    } 
    a 
} 

, 내가 파일을 소스와 내가 만든 벡터로 전화 :

> v 
[1] 8 5 6 7 4 1 3 2 
> quicksort(v, 1, length(v)) 
[1] 8 5 6 7 4 1 3 2 

지금까지 내가 R에서 재귀 함수를 수행 할 수 있다는 것을 읽었을 때 참조로 전달할 수 없다는 것을 알고 있지만이 함수는 변경된 벡터? 나는 왜 그것이 같은 벡터를 반환하는지에 관해 혼란 스럽다. 어떤 도움을 주시면 감사하겠습니다.

Answer 1

함수를 사용하여 개체를 변경하려면 반환하고 반환해야합니다. 코드를 두 곳에서 바꿨습니다 : partition 함수는 벡터 a과 위치 i이라는 두 항목의 목록을 반환합니다. quicksort에서 : 의 결과는 temp에 저장되고 그 항목은 a 및 q에 할당됩니다. 또한 각 변경 결과를 다시 a에 할당해야합니다.

partition <- function(a, p, r) { 
    x = a[r] 
    i = p - 1 
    for (j in p:(r-1)) { 
    if (a[j] <= x) { 
     i = i + 1 
     t = a[i] 
     a[i] = a[j] 
     a[j] = t 
    } 
    } 
    t = a[i+1] 
    a[i+1] = a[r] 
    a[r] = t 
    list(i = i+1, a = a) 
} 

quicksort <- function(a, p, r) { 
    if (p < r) { 
    temp = partition(a, p, r) 
    a <- temp$a 
    q = temp$i 
    a = quicksort(a, p, q-1) 
    a = quicksort(a, q+1, r) 
    } 
    a 
} 

v = c(8, 5, 6, 7, 4, 1, 3, 2) 
quicksort(v, 1, length(v)) 
## [1] 1 2 3 4 5 6 7 8 

건배,

알렉스

Answer 2

quicksort 또는 partition 함수 내에서 a을 수정하지 않았기 때문입니다. R은 사실상 값을 전달합니다. 함수 내에서 값을 수정하면 사본을 수정하게됩니다. 이 수정은 함수가 반환 된 후에도 지속되지 않습니다.

이렇게하려면 parition을 수정하는 대신 분할 된 값을 반환해야합니다.

예를 들어 partition은 두 벡터의 목록 인 두 개의 파티션을 반환 할 수 있습니다. 그런 다음 각 반환 된 벡터에 quicksort을 호출 할 수 있습니다.