임시 변수가없는 스와핑 함수에서 빠른 정렬이 올바르게 작동하지 않습니다.

Question

정렬 알고리즘을 사용하여 작업 중이며 quicksort가 임시 변수없이 스왑 함수에서 올바르게 작동하지 않는다는 것을 알았습니다. 아래 코드를 첨부했습니다. 신속하게 작성된 신속한 놀이터에서이 코드를 실행할 수 있습니다. This is the link to execute this code online. 이 정보를 정리하는 데 필요한 기타 정보를 알려주십시오. 누군가가 이것을 설명 할 수 있다면 정말 감사 할 것입니다.

주 - 스왑 기능에서 두 가지 코드를 주석으로 작성했습니다. 하나는 임시 변수가없고 다른 하나는 임시 변수입니다. 이 코드는 임시 변수가있는 스왑 함수와 완벽하게 작동합니다.

func swap(_ a:inout Int , _ b:inout Int) 
{ 

    a = a+b 
    b = a-b 
    a = a-b 

    /* 

    let x = a 
    a = b 
    b = x 
    */ 
} 

func partition(_ arr : inout [Int], _ low : Int, _ high : Int)->Int 
{ 
    let pivot = arr[high] 
    var i = low-1 
    var j = low 
    while(j<high) 
    { 
     if(arr[j]<=pivot) 
     { 
      i=i+1 
      swap(&arr[i],&arr[j]) 
     } 

     j = j+1 
    } 
    swap(&arr[i+1],&arr[high]) 
    return i+1 
} 
func quickSort(_ arr : inout [Int], _ low : Int, _ high : Int) 
{ 
    if low < high 
    { 
     let pi = partition(&arr,low,high) 
     quickSort(&arr,low,pi-1) 
     quickSort(&arr,pi+1,high) 
    } 
} 

var arr = [11 , 40 ,50 ,20 ,30,77,90,77,14,8,897,765,34,0,89] 
print(arr) 
quickSort(&arr,0,arr.count-1) 
print(arr) 

Answer 1

모두 인수가 동일한 배열 요소를 가리키는 경우 "임시 변수없이 스왑"이 작동하지 않습니다

func swap(_ a:inout Int , _ b:inout Int) { 
    a = a+b 
    b = a-b 
    a = a-b 
} 

var a = [5, 6, 7] 
swap(&a[0], &a[0]) 
print(a) // [0, 6, 7] 

참고도 같은 배열의 두 다른 요소를 통과 함수에 대한 inout 인수가 정의되지 않은 동작입니다. 스위프트에서 4/엑스 코드 (9) 당신은 컴파일러 경고 얻을 것입니다 :

var a = [5, 6, 7] 
swap(&a[0], &a[1]) 
// warning: overlapping accesses to 'a', but modification requires exclusive access; consider copying to a local variable 

및 런타임 오류 :

Simultaneous accesses to 0x1005e4f00, but modification requires exclusive access.

왜 swapAt() 방법 (복용이 개 지수 인수로는) 가 추가되었습니다입니다 Swift에서 MutableCollection으로 변경하십시오.

자세한 내용은 SE-0176 Enforce Exclusive Access to Memory을 참조하십시오.

Answer 2

a 및 b이 같은 요소를 가리키면 스왑 기능이 중단됩니다. 가독성이 높고 모든 데이터 유형 및 모든 값에 대해 올바르게 작동하는 임시 변수가있는 버전을 선호하십시오.

두 개의 높은 값을 추가 할 때 함수가 오버플로 될 수 있으며 부동 소수점 값이 완전히 깨질 수 있습니다.