선택 정렬이 왜 안정적이지 않습니까?

Question

이것은 사소한 일이지만, 왜 Selection Sort의 기본 구현이 안정적이지 않은지 이해할 수 없습니까?

반복 할 때마다 나머지 배열에서 최소 요소를 찾습니다. 이 최소값을 찾으면 찾을 수있는 첫 번째 최소값을 선택할 수 있으며 요소가 실제로 값보다 작을 때 업데이트합니다. 따라서 각 반복에서 선택한 요소가 첫 번째 최소값입니다. 즉, 이전 정렬 순서에서 첫 번째 요소입니다. 따라서, 내 이해를 위해, 현재의 정렬은 동등한 요소에 대해 이전 정렬에 의해 생성 된 순서를 파괴하지 않습니다.

무엇이 누락 되었습니까?

Answer 1

작은 예 :

하자 (a < B < C)와

< B> < B> < A>, < C>에서 B = B

한 후 시퀀스가 정렬되지만 B 및 b의 순서는 다음과 같이 변경됩니다.

< a>, < b>, < B > < c>

그러나 전환하는 대신 최소값을 삽입하면 선택 정렬이 안정적으로 적용될 수 있습니다. 그러나 효율적이기 위해서는 저렴한 비용으로 삽입을 지원하는 데이터 구조가 있어야합니다. 그렇지 않으면 2 차적인 복잡성으로 끝납니다.

Answer 2

문제는 선택 정렬이 배열의 앞면에서 최소 요소로 비워진 지점으로 스와핑되어 정렬 된 순서가 엉망이 될 수 있다는 것입니다. 예를 들어, 내가 정렬 처음

(4, 0), (4, 1), (1, 0) 

선택 정렬 스왑있어 가정 (1, 0) 전면 :

(1, 0), (4, 1), (4, 0) 

그리고 지금 (4, 0), (4, 1) 그들이 일종의 출발점에서 순서가 맞지 않습니다. 이 작업을 완료하면이 순서로 요소가 남으며 4가 잘못되었습니다.

희망이 도움이됩니다.

Answer 3

안정적 수단은 요소가 이미 정렬 된 경우 더 이상 계산하지 않지만 끝까지 계산하므로 안정적이지 않습니다.