1
배열이 a1, a2, ..., ak, _, a (k + 1), ..., an으로 주어집니다. 밑줄 (_)은 공백을 나타냅니다. 배열 요소를이 공간으로 옮길 수 있습니다. 우리는이 작업을 여러 번 반복 할 수 있습니다. 하나의 공백 공간으로 모든 배열을 정렬 할 수 있습니까?하나의 임시 변수/공간을 사용하여 배열을 정렬 할 수 있습니까?
A
답변
4
예 가능합니다.
정렬 된 배열은 해당 배열의 특정 순열입니다.
모든 순열은 일련의 개별 스왑에 의해 도달 될 수 있습니다.
스왑은 단일 임시 요소로 구현할 수 있습니다.
(XOR 연산을 사용하여 없이 임시 배열을 정렬 할 수 있습니다.)
0
내부 정렬을위한 알고리즘이 여러 개 있습니다. 가장 주목할만한 것은 quick-sort의 비 재귀 버전입니다 (재귀 버전은 재귀 호출의 수에 비례하여 스택의 공간을 차지하므로) 평균적으로 O (n log n)의 복잡성을 부여합니다.
또 다른 가능성은 O (n^2) 인 삽입 정렬 및 버블 정렬과 같이 덜 효율적인 알고리즘을 사용하는 것입니다.
특정 질문에 대해서는 그 특정 공간을 사용하는 것이므로 Bathsheba에서 말한 것처럼 스와핑에 사용할 수 있지만 이런 종류의 작업을 수행하는 데 시간을 낭비하지 않을 것입니다.
배열의 중간에 "사용되지 않은 공간"이라는 명확한 개념이있는 경우 해당 의미론, 즉 순서면에서 올바른 배치가 무엇인지 이해해야합니다. 당신이하지 않으면, 당신이 그것을 어디에 두어도, 당신은 "깨진"불변성으로 자신을 발견 할 것이고, 당신은 당신의 컬렉션에 바이너리 검색과 같은 알고리즘을 구현하는데 어려움을 겪을 것이다.
0
아직 실제 코드에서는 그러한 컨테이너를 보지 못했지만 구현하기 가장 쉬운 알고리즘 (가장 효율적이지는 않습니다!)은 첫 번째 요소로 빈을 스왑 한 다음 가장 작은 것을 가장 먼저 비어있는 것으로 바꾸는 것입니다. 컨테이너는 두 번째 위치에서 시작하여 빈 위치가 될 마지막 위치까지 반복합니다. 이 경우 스왑은 빈 공간을 채우고 다른 위치를 비어있는 것으로 표시한다는 것을 의미합니다.
감사합니다. 심지어 비 임시 스왑에는 XOR을 사용하는 버전이 있다는 것을 모릅니다. \t a = a^b; \tb = a^b; \t a = a^b; 또는 플러스/마이너스를 통해 : \t a = a + b; \t b = a-b; \t a = a - b; –