16
코드가 실행되는 대상 구현이 무엇인지 알지 못하는 JavaScript (일부 적용 가능)에서는 기본 정렬 알고리즘 (Array.sort)이 안정적인지 여부를 감지하는 기능이 있습니다. 다음은 the specification입니다.정렬 알고리즘이 안정적인지 감지하는 블랙 박스 방법이 있습니까?
나는 웹킷 (1)(2) 2 개 테스트를 찾을 수 있지만, 이러한 테스트는 어떻게 믿을 수 있습니까? (이 검사는 PCP으로 끝날 수 있습니까?) 나는 수학적으로 소리가 나올 해결책을 찾고 있습니다.
고급 정렬 알고리즘은 소스 배열의 길이 (예 : Timsort)에 따라 부분 알고리즘을 변경할 수 있으므로 까다로운 문제입니다. 나는 실행 한 모든 테스트가 Google 크롬의 종류를 안정적으로 보여 주었기 때문에 혼란 스러웠지만, 필자가 본 모든 문서에서 불안정하다고 말했습니다 (the source).
(일반적으로, 나는 안정적인 나의 종류를 만들기 위해 this strategy를 사용, 그것은 작은 그러나 때때로 눈에 띄는 성능에 미치는 영향가) 다양한 구현에 정렬 소스 코드 :
이러한 결정은 확률 론적으로 만 가능합니다. 예를 들어 입력 'I'을 사용하는 정렬 알고리즘 'S'를 정의 할 수 있습니다. 보통'S'는 실제 sorting 작업을 안정된 sortalgorithm'T' *로 바꾸지 만,'I'는 특별한 값'I'와 같을 때 비 안정 정렬'U'를 대신 사용합니다.당신은 운이 좋으면'S'가 비 안정적이라는 것을 결코 증명할 수 없을 것입니다. 좀 더 현실적으로,'S'는'I'가 아주 길지 않으면 안정된 정렬을 사용합니다. 다시 말하지만, 적절한 긴 입력을 테스트 할 경우 비 안정적인 정렬 만 관찰하게됩니다. – apsillers
사양에서 안정적이지 않다고 말하면 어레이를 정렬 할 때 항목을 바꿀 수 있다고 생각할 수는 없지만 그다지 신뢰할 수는 없습니다. 약속이 없습니다. (현재) 구현이 안정적이라고해도 그것이 항상 존재할 것이라는 의미는 아니며 크롬이 실행되는 모든 플랫폼에 적용된다는 의미는 아닙니다. – frozenkoi
@MarZab에 동의합니다.이 문제는 중단 문제입니다. '[computer-science]'및/또는'[computer-science-theory]'태그를 붙이면 좀 더주의를 기울일 수 있습니다. – apsillers