대체 선택 대체 정렬 선택

Question

대체 선택 정렬에 대한 연구를 해왔습니다. 교체 구현 정렬에 대한 구현이나 좋은 구현을 찾을 수 없습니다! 어쩌면 나는 충분히 열심히보고 있지 않다, 그러나 Google는 선택 선택을 가진 보충 선택 선택을 혼동하고있다 ... 그래서 이것은 궁금하게 생각했다 :

선택 정렬과 교체 선택 정렬의 실제 차이점은 무엇입니까?

대체 선택 정렬 (또는 작성 가이드)의 구현은 어디에서 찾을 수 있습니까?

대체 정렬 선택의 특징은 다른 정렬 알고리즘보다 더 바람직합니까?

이 알고리즘은 다른 이름으로 알려져 있습니까?

Answer 1

나는이 알고리즘을 전에 자세히 설명하지 않았으며, 내가 수집 한 내용을 기초로하여 this set of lecture notes을 수집했다.

필자가 알기로, 선택 정렬과 대체 선택 정렬의 주요 차이점은 선택 정렬이 주 메모리에 저장된 전체 시퀀스를 정렬하도록 설계되었지만 대체 선택 정렬은 정렬되지 않은 시퀀스를 너무 커서 메인 메모리를 외부 메모리에 저장 될 수있는 정렬 된 일련의 "가닥"으로 변환합니다. 그런 다음 이러한 외부 가닥을 병합하여 전체 정렬 된 순서를 형성 할 수 있습니다. 이름의 유사성과 알고리즘 작동의 한두 가지 주요 단계에도 불구하고 근본적으로 다른 문제를 해결하도록 설계되었습니다.

선택 정렬

가 온라인으로 분류 가능한 선택에 대한 많은 좋은 자습서, 그래서 그것을 논의 너무 많은 시간을 소비하지 않습니다. 직관적으로 알고리즘은 다음과 같이 작동합니다.

• 가장 작은 요소를 찾아 배열의 0 위치로 바꿉니다.
• 두 번째로 작은 요소를 찾아 배열의 위치 1로 바꿉니다. 배열 정보 1 -
• 는
• n 번째 가장 작은 요소를 찾아 해당 위치로 교환 ... 세 번째로 가장 작은 요소를 찾아 어레이
• 의 2 위치로 교체.

이 배열 메모리에 완전하게 유지 될 수 있다고 가정하고, 그런 경우에는이 알고리즘 Θ (N 2) 시간에서 실행. 매우 빠르지 않으며 대용량 데이터 세트는 바람직하지 않습니다.

교체 선택은 정렬

이 알고리즘은 도널드 크 누스에 의해 1965 년에 기술되었다, 그래서 우리가 현재 사용하고있는 것과 매우 다른 컴퓨팅 환경에서 작동하도록 설계되었습니다. 컴퓨터는 메모리가 거의없고 (일반적으로 고정 된 수의 레지스터) 큰 외장 드라이브에 액세스 할 수 있습니다. 레지스터에 값을로드하고 처리 한 다음 외부 저장소로 직접 플러시하는 알고리즘을 만드는 것이 일반적입니다. (흥미롭게도 이것은 외부 저장 장치 대신 메인 메모리를 제외하고 현재 프로세서가 작동하는 방식과 유사합니다.

의 우리가 두 개의 배열을 저장할 메모리에 충분한 공간이 있다고 가정하자 : 값의 무리를 저장할 수있는 크기 n의 첫 번째 배열 Values 및 부울 값을 보유 크기 n의 두 번째 배열 Active을. Active 및 Values 배열을 저장하기위한 메모리 공간과 저장 공간에 대한 몇 가지 추가 변수가있는 경우 정렬되지 않은 값의 큰 입력 스트림을 가져 와서 정렬하기 위해 최선을 다할 것입니다.

알고리즘의 배경은 다음과 같습니다. 먼저 Values 배열에 정렬되지 않은 시퀀스가 ​​들어있는 외부 소스의 n 값을로드합니다. 그런 다음 Active 값을 모두 true으로 설정하십시오. 반복 Values 배열에서 가장 낮은 값을 찾고 출력 스트림에 그것을 기록하여

Values: 4 1 0 3 
Active: Yes Yes Yes Yes 

교체 선택 정렬 알고리즘의 작동 예를 들어, n = 4 경우, 우리는이 설정을 가지고 있습니다. 이 경우 0 값을 찾아서 스트림에 쓰는 것으로 시작합니다. 이것은 우리가 우리의 Values 배열에 빈 자리가 지금

Values: 4 1   3 
Active: Yes Yes Yes Yes 

Output: 0 

을 제공합니다, 그래서 우리는 외부 소스에서 다른 값을 가져올 수 있습니다. 이제 우리는이 경우 2를 얻을 가정하자, 우리는이 설정을 가지고 :

Values: 4 1 2 3 
Active: Yes Yes Yes Yes 

Output: 0 

공지 사항 2> 0, 0부터 여기에 가장 작은 요소는, 우리는 우리가에 0을 쓴 것을 보장하는 것을 결과가 나오면 2가 나오면 안된다. 좋습니다. 따라서 알고리즘의 다음 단계로 이동하여 여기에서 가장 작은 요소를 다시 찾습니다. 즉, 1, 그래서 우리는 출력 장치로 전송 : 외부 소스에서 다른 값을 읽어

이제

Values: 4   2 3 
Active: Yes Yes Yes Yes 

Output: 0 1 

:

Values: 4 -1 2 3 
Active: Yes Yes Yes Yes 

Output: 0 1 

이제 우리는 문제에있어. 이 새로운 값 (-1)은 1보다 낮습니다. 즉,이 값을 정렬 된 순서로 출력에 넣으려는 경우,이 값이 1보다 커야합니다. 그러나 다시 읽을 메모리가 충분하지 않습니다. 출력 장치를 고쳐 그것을 고쳐라. 대신, 우리는 다음을 할 것입니다. 지금은 -1을 기억하십시오. 우리는 남은 원소들을 정렬하기 위해 최선을 다할 것입니다. 그러나 그렇게 할 때, 우리는 두번째 순열을 생성 할 것이고, -1을 그 순서에 넣을 것입니다. 즉, 하나의 정렬 된 시퀀스를 생성하는 대신 두 개를 생성합니다.

메모리에 -1을 쓰고 싶지 않다는 것을 표시하려면 -1을 유지하는 슬롯을 비활성으로 표시해야합니다. 이 여기에 표시됩니다 : 지금부터

Values: 4 -1 2 3 
Active: Yes NO Yes Yes 

Output: 0 1 

, 우리는 단지 -1 여기에없는 척 수 있습니다.

계속하겠습니다. 우리는 지금 아직 (2) 활성 메모리에서 가장 작은 값을 찾아 장치에 쓰는 :

Values: 4 -1  3 
Active: Yes NO Yes Yes 

Output: 0 1 2 

우리는 지금 입력 장치에서 다음 값을 당깁니다.7 :

Values: 4 -1 7 3 
Active: Yes NO Yes Yes 

Output: 0 1 2 

7> 2이므로 출력 결과 2가 나오므로 아무 것도하지 않습니다. 다음 반복에

, 우리는 가장 낮은 활성 값 (3)을 발견하고 그것을 밖으로 쓰기 :

Values: 4 -1 7  
Active: Yes NO Yes Yes 

Output: 0 1 2 3 

우리는 입력 장치로부터 다음의 값을 당깁니다. 또한입니다. 3.이 경우 3이 가장 작은 값이므로 3을 출력 스트림에 직접 쓸 수 있습니다. 3은 여기에있는 값 중 가장 작기 때문에 반복적으로 저장할 수 있습니다. :

이제 입력 장치에서 다음 값을 가져옵니다. 이 경우, 이전과 같이 2가 3보다 먼저 나온다는 것을 알 수 있습니다. 이전 -1과 마찬가지로 지금은 2를 메모리에 유지해야합니다. 우리는 나중에 그것을 쓸 것이다. 이제 우리의 설정은 다음과 같습니다

Values: 4 -1 7 2 
Active: Yes NO Yes NO 

Output: 0 1 2 3 3 

을 이제, 우리는 작은 활성 값 (4)을 찾아 출력 장치에 기록 :

Values:   -1 7 2 
Active: Yes NO Yes NO 

Output: 0 1 2 3 3 4 

우리가 지금 우리의 다음과 같은 1에서 읽은 것으로 가정 해 보겠습니다 입력. 따라서 우리는 Values에 넣어하지만, 비활성 상태 표시 : 7 만 하나의 활성 값,있다

Values: 1 -1 7 2 
Active: NO NO Yes NO 

Output: 0 1 2 3 3 4 

, 그래서 우리는 그것을 밖으로 쓰기 :

Values: 1 -1  2 
Active: NO NO Yes NO 

Output: 0 1 2 3 3 4 7 

이의 우리가 지금 5를 읽어 가정하자. 이 경우, 이전과 같이, 우리는 그것을 저장하지만, 슬롯 비활성 표시 : 값이 현재 비활성 모든 것을

Values: 1 -1 5 2 
Active: NO NO NO NO 

Output: 0 1 2 3 3 4 7 

공지 사항. 즉, 현재 출력 실행에 들어갈 수있는 모든 값을 메모리에서 플러시했습니다. 이제 우리는 우리가 가지고 있었던 모든 가치를 나중에 기록해야합니다.

Values: 1 -1 5 2 
Active: Yes Yes Yes Yes 

Output: 0 1 2 3 3 4 7 

-1 가장 작은 값이기 때문에, 우리는 그것을 출력 : 이렇게하려면, 우리는 모든 값이 활성으로, 다음, 이전과 반복 표시

Values: 1   5 2 
Active: Yes Yes Yes Yes 

Output: 0 1 2 3 3 4 7 -1 

우리가 3를 읽을 수 있다고 가정하자. -1 < 3이므로 Values 배열에로드합니다.

Values: 1 3 5 2 
Active: Yes Yes Yes Yes 

Output: 0 1 2 3 3 4 7 -1 

1은 여기에 작은 값이기 때문에, 우리는 그것을 제거 :

Values:   3 5 2 
Active: Yes Yes Yes Yes 

Output: 0 1 2 3 3 4 7 -1 1 

이의 우리가 입력 값에서 지금 걸 가정하자.

Values: --- --- --- --- 
Active: Yes Yes Yes Yes 

Output: 0 1 2 3 3 4 7 -1 1 2 3 5 

그리고 우리 : 마지막으로

Values: --- --- 5 --- 
Active: Yes Yes Yes Yes 

Output: 0 1 2 3 3 4 7 -1 1 2 3 

5 :

Values: --- 3 5 2 
Active: Yes Yes Yes Yes 

Output: 0 1 2 3 3 4 7 -1 1 

이 다음에 온다 : 그런 다음 3

Values: --- 3 5 --- 
Active: Yes Yes Yes Yes 

Output: 0 1 2 3 3 4 7 -1 1 2 

우리는 다 같이이 슬롯을 표시합니다 끝났어! 결과 시퀀스는 이 아니고으로 정렬되어 있지만 이전보다 훨씬 좋습니다. 이제 정렬 된 순서로 두 가닥으로 구성됩니다. 함께 병합하면 (같은 방법으로 mergesort 병합을 수행합니다) 결과 배열을 정렬합니다. 이 알고리즘은 잠재적으로 훨씬 더 많은 가닥을 생성 할 수 있었지만 샘플 입력이 작았 기 때문에 우리는 두 개 밖에 없었습니다.

---

이렇게 빠르기 때문에? 음, 루프의 각 반복은 합계 최대 n 개의 비교 (메모리에서), 하나의 읽기 및 하나의 쓰기를 수행합니다. 따라서 스트림에 총 N 개의 값이있는 경우 알고리즘은 O (nN) 비교와 O (N) 메모리 연산을 수행합니다. 메모리 연산에 비용이 많이 든다면, 이것은 나쁘지 않습니다. 모든 것을 다시 병합하려면 두 번째 패스가 필요합니다. 의사에서

이 알고리즘은 다음과 같습니다

Make Values an array of n elements. 
Make Active an array of n booleans, all initially true. 

Read n values from memory into Values. 
Until no values are left to process: 
    Find the smallest value that is still active. 
    Write it to the output device. 
    Read from the input device into the slot where the old element was. 
    If it was smaller than the old element, mark the old slot inactive. 
    If all slots are inactive, mark them all active. 

지금이 알고리즘을 코딩 할 이유가 있다면 내가 충격을받을 것입니다. 수십 년 전에 기억이 정말로, 정말로 작았을 때 이것은 의미가있었습니다. 요즘에는 external sorting algorithms을 사용할 수있는 편이 훨씬 뛰어나며이 알고리즘보다 성능이 우수합니다.

희망이 도움이됩니다.

Answer 2

병합 할 문자열의 수가 가장 적기 때문에 병합 정렬이 여전히 외부 정렬에 사용되며 병합은 병합에서 가장 비용이 많이 드는 부분입니다. 사용 된 접근법은 templatetypedef가 제공하는 우수한 예제보다 조금 복잡하지만 기본적으로 많은 레코드를 버퍼링하고 정렬하며 -1 1 등과 같은 순서 레코드를 수집하여 버퍼에 보관하고 하위 순서 부분을 작성합니다 비어있는 공간을 채우고, 다시 정렬하고, 버퍼에서 병합 된 모든 레코드를 병합하고, 시퀀스를 계속할 수 없을 때까지 반복 한 다음 시퀀스를 덤프하고 버퍼링 된 시퀀스 레코드와 새로운 입력 레코드를 취합니다. 다음 문자열에서 시작합니다. 입력이 끝날 때까지 반복하십시오.

일부 응용 프로그램에서는 정렬 순서를 벗어난 레코드를 스윕 한 후 나중에 올바른 위치에 다시 삽입하므로 병합이 필요하지 않습니다. 하니웰과 IBM이 이러한 종류의 도입을 발표 한 1964 년에 많은 상업 고객에게 놀라운 결과였습니다.