정렬 삽입
삽입 정렬 (삽입 정렬) — ;입력 시퀀스의 요소를 한 번에 하나씩 조회하고 새로 들어오는 각 요소를 이전에 정렬한 요소 중 적절한 위치에 배치하는 정렬 알고리즘입니다.
정렬 삽입 – 이것은 매우 간단하지만 비효율적인 알고리즘이지만 일반적으로 더 효율적인 다른 많은 알고리즘이 개발된 후에도 관련성이 있는 몇 가지 특정 이점이 있습니다.
삽입 정렬을 사용하면 정렬하기 전에 전체 배열을 앞에 둘 필요가 없습니다. 알고리즘은 정렬하는 동안 한 번에 하나의 요소를 받을 수 있습니다. 이것은 정렬 중에 더 많은 요소를 추가해야 하는 경우 매우 편리합니다. 알고리즘은 "재실행" 없이 올바른 위치에 새 요소를 삽입합니다. 전체 배열 정렬.
삽입 정렬은 작은(~10개 요소) 데이터세트에 대한 효율성으로 인해 실제로 사용할 수 있습니다.
문제는 다음과 같습니다. 이미 정렬된 배열의 일부가 있고 순서를 유지하면서 배열의 나머지 요소를 정렬된 부분에 삽입하려고 합니다. 이를 위해 알고리즘의 각 단계에서 입력 데이터 요소 중 하나를 선택하고 전체 입력 데이터 세트가 정렬될 때까지 이미 정렬된 배열 부분의 원하는 위치에 삽입합니다. 입력 배열에서 다음 요소를 선택하는 방법은 임의적이지만 일반적으로(그리고 안정적인 정렬 알고리즘을 얻기 위해) 요소는 입력 배열에 나타나는 순서대로 삽입됩니다.
이 알고리즘의 알고리즘 구현
<예비>
// null 요소는 이미 정렬된 시퀀스로 간주됩니다.
// 따라서 루프는 1부터 시작합니다.
I=1에서 N-1까지의 루프 1단계
X=A[I]
지=나
WHEN J>0 AND A[J-1]>X //삽입할 곳을 찾는 중
교환 A[J],A[J-1]
J=J-1
END BYE
A[J]=엑스
다음 나
계산 복잡성:
\(\displaystyle O(n^{2})\).