누구든지 되돌릴 수있는 정렬 알고리즘을 알고 있습니까? 그래서 주어진 :가역 정렬 알고리즘?
5,39,196,0,15,243
정렬 만들 것입니다 : 다음
0,5,15,39,196,243
그리고 반전을 어떤 지식을 알 필요없이, 다른 아마도 이는보다 정렬 알고리즘을 사용하고 많은 반복이 실행 된 방법이 돌아갈 것 :
5,39,196,0,15,243
그것은 m에 발생 그 버블 정렬은 아마도 작동 할 것입니다. 정렬이 몇 번이나 실행되어야 하는지를 알기 만하면, 그 단계를 원래대로 돌아가는 횟수만큼 되돌릴 수 있습니다. 다른 사람들이 있습니까?
시간의 복잡성이 문제가되지 않도록 실험용입니다 (속도가 느려지는 것은 신경 쓰지 않습니다).
런타임 효율성과 관련이 없다면 Permutation Sort을 사용할 수 있습니다.
목록의 모든 순열을 생성하고 어떤 순열에 목록이 정렬되어 있는지 확인합니다. 정렬 된 목록을 찾기 전에 얼마나 많은 라운드를 실행했는지 알면, 거기에 도달하기 위해 스왑 된 값이 무엇인지 정확히 알 수 있습니다.
정렬되지 않은 목록에서 실행하고 정렬 된 목록을 얻으려면 50 라운드를 실행해야한다면 정확히 어떤 요소가 바뀌 었는지 알 수 있고 정렬을 되돌릴 수 있습니다.
미리 알려진 데이터에 대한 특별한 구조가 없으면 이보다 더 잘할 수없고 여전히 원하는 효과를 얻을 수 없다는 점에 유의하십시오. 이는 원래 목록의 모든 순열이 같은 결과로 정렬되기 때문에 1과 순열 수 사이의 숫자를 유지해야하기 때문입니다. 그게 당신이 여기서 지키고있는 바로 그 것입니다. 물론, 질문에 대한 의견에서 알 수 있듯이 더 나은 (더 빠른) 정렬 알고리즘을 사용하고 원래의 전체 목록을 저장할 수는 있지만 OP 이후의 내용이 아니라고 가정합니다. – David
나는 이것을 아주 많이 의심한다. 실제로 해봤습니까? 정렬 된 목록의 순열을 생성하면 원본에서 생성 된 순열의 순서와 관계없이 순서대로 순열을 제공합니다. –
@DonRoby, 매번 같은 순서로 모든 순열을 적용하고 어느 것이 올바른 정렬을했는지 확인한 다음 정렬을하면 정렬 된 목록 만 처리 과정을 추적해야합니다. 어떤 순열이 성공적으로 정렬되었는지 (전체 순열을 유지하는 것보다는 색인으로 유지할 수 있음). – David
일반적으로 정렬 알고리즘은 n 개 항목 (예 : O (nlogn))을 정렬하여 n 개 항목을 정렬합니다. 즉, 복사본을 유지하는 것이 더 낫다는 것을 의미합니다 (단지 n < O (nlogn) 임).
복사본이 너무 많으면 (개체가 너무 크면) 처음 순서로 참조 (포인터 또는 ID) 배열을 유지하면됩니다.
전혀 불가능한 것 같습니다. 그리고 왜 그게 필요할까요? 원래 주문을 어딘가에 기록하십시오. – Mat
배열을 복사하고 정렬하는 것은 어떻습니까? 그런 다음 정렬 된 원본 복사본이 있습니다. 정렬 후 요소의 원래 위치를 알아야 할 경우 요소에 색인 번호를 첨부 할 수 있습니다. – nhahtdh
당연히 원래 주문은 사라집니다. 제가 자주하는 일은 0 .. length-1의 키 배열을 정렬하여 정렬 된 액세스에 사용하는 것입니다. – harold