스왑 될 항목에 대한 정보를 반환하는 정렬 알고리즘

Question

스마트 정렬 알고리즘의 일종 (확실하지만 확실하지는 않습니다.)이 있는지 궁금합니다.

스마트 정렬 알고리즘이란 무엇을 의미합니까? 예를 들어 고려하자 :

이

1, 2, 3, 4, 5 

가 그럼 난 2, 4를 교환, 그래서 내가 가진 :

두 번째 단계로

1, 4, 3, 2, 5 

내가 5를 교환하고

을 나는 분류 표에서 5 개 숫자를했습니다 2 그래서 최종 결과는 다음과 같습니다 알고리즘에 대한

1, 5, 3, 2, 4 

내 기대가 입력 (1, 5로 마지막 세트를 배치하는 것입니다, 3, 2, 4), 결과적으로 두 번째와 다섯 번째 항목을 교환해야하고 두 번째와 네 번째 목록을 정렬해야한다는 정보를 얻고 싶습니다.

정렬 네트워크의 사용에 대해 생각해 보았습니다. 특정 크기의 데이터에 대해 필요한 모든 비교 및 ​​스왑 지침을 생성 한 다음 입력 데이터에 대해 수행 할 스왑을 반환 할 수 있지만 다른 방법이있을 수 있습니까?

어떻게해야합니까?

Answer 1

나는 데이터의 실제 스와핑이 매우 비싸다고 생각하지만 비교는 비교적 저렴하다.

먼저 배열의 각 요소 위치를 확인하기 위해 정기적 인 정렬 알고리즘을 사용합니다. 이를 위해 수 많은 알고리즘이 있습니다 (예 : quicksort 또는 bubble 또는 insertionsort).

이제 우리는 각 요소가 어디로 가야하는지 알고 있으며, 여기에서부터 원래의 데이터를 정렬 된 위치로 가져 오기 위해 최적의 일련의 스왑을 찾을 수 있습니다. 의사의

예 :

compare(proxy1, proxy2) 
    return compare(proxy1.data, proxy2.data) 

smartSort(unsorted) 
    swaps = [] 
    count = size(unsorted) 
    // create a proxy for all elements 
    proxiesOrig = [ new proxy(data) | for unsorted as data ] 
    // and make a copy which we are going to sort 
    proxiesSort = shallowCopy(proxiesOrig) 
    sort(proxiesOrig) // Do a regular sort here, using the compare function above 
    // now note the location of each target 
    // because we made a shallow copy, the location will also be marked in the 
    // proxiesOrig list 
    for i = 1 .. count 
    proxiesSort[i].location = i 
    // Now the proxiesOrig is the unsorted list 
    // with location information to where everything needs to go 
    for i = 1 .. count 
    while (proxiesOrig[i].location <> i) 
     // swap the proxy on location i with the one to where i needs to go 
     swap(proxiesOrig, i, proxiesOrig[i].location) 
     // and record it 
     swaps.add(i, proxiesOrig[i].location) 
    return swaps 

Answer 2

최소 스왑의 수를 찾기는 일반적으로 (포인터에 수행 할 수 있습니다 스왑) 정렬 중요하지 않다, 그러나 그것은 자신의 관계에서 잘 알려진 문제입니다.

이 질문에 대해 살펴 유무 : Counting the adjacent swaps required to convert one permutation into another

또는 편집 거리에 연구를 가리 킵니다.