그래서 저는 현재 자바를 배우고 있으며, 왜 삽입 - 정렬 방법이 스왑 연산을 사용할 필요가 없는지 스스로에게 묻고있었습니다. 필자가 이해하는 한, 요소는 스왑 핑되어서이 정렬 알고리즘에서 스왑 연산을 사용하는 것이 유용하지 않겠습니까?왜 삽입 정렬에 스왑 작업이 필요하지 않습니까?
는 나는이 새로운 오전하지만 난 그들이 실제로 길을 왜, 이러한 알고리즘의 배경을 이해하려고 말했듯이
통찰력 : B.
위키 백과의 article for Insertion sort 상태
각각의 반복, 삽입 정렬은 입력 데이터에서 하나 개의 요소를 제거는 정렬 된 목록 내에 속하는 위치를 찾아 내고,이 삽입을. 입력 요소가 없어 질 때까지 반복됩니다. [0123] 이 작 으면 정렬 된 목록에서 올바른 위치를 찾은 은 큰 값을 공백으로 채우고 올바른 위치에 을 삽입합니다.
이 교대를 극단적 인 스왑으로 간주 할 수 있습니다. 실제로는 값이 자리 표시 자에 저장되고 다른 값과 비교하여 확인됩니다. 이 값이 더 작 으면 간단히 이동됩니다. 목록/배열에서 이전 (또는 다음) 위치를 바꿉니다. 자리 표시 자의 값은 요소가 이동 된 위치에 놓입니다.
감사합니다. 대단히 도와 줬어! – user3084311
스왑 작업이 많지 않다면 어떻게 효율적으로 구현할 수 있는지 알 수 없습니다. –
@Marko 스왑 할 필요없이 방향에 따라 이전 또는 다음 위치의 요소를 덮어 씁니다. 귀하의 가치는 자리 표시 자에 저장되므로 잃어 버리지 않습니다. 이동을 마쳤 으면 마지막 처리 인덱스의 자리 표시 자에 값을 배치합니다. –
삽입 정렬은 스와핑을 수행하지 않습니다. 삽입중인 요소에 대한 공간을 만들기 위해 요소를 순차적 목록에서 이동하여 삽입을 수행합니다.
이것이 O (N^2) 알고리즘 인 이유입니다. N의 각 요소에 대해 O (N) 교대가있을 수 있습니다.
디버거를 사용하여 소스를 통해 스왑 작업을 사용하지 않았는지 확인 했습니까? 여기에 코드를 붙여 넣을 수 있습니까? – Zavior
코드를 제공 할 수 있습니까? 또는, 당신은 무엇을 묻고 있습니까? –
목록의 정렬되지 않은 부분을 통해 실행되고 가장 작은 나머지 요소를 찾은 다음 해당 위치로 바꾸는 * 선택 정렬 *을 생각할 수도 있습니다. –