데이터 구조 및 알고리즘 삽입 정렬

이것은 내부 비교 기반 정렬 알고리즘입니다. 여기에서는 항상 정렬되는 하위 목록이 유지됩니다. 예를 들어 배열의 아래쪽 부분은 정렬되도록 유지됩니다. 이 정렬 된 하위 목록에 '삽입'될 요소는 적절한 위치를 찾아서 삽입해야합니다. 따라서 이름,insertion sort.

배열은 순차적으로 검색되고 정렬되지 않은 항목은 이동하여 정렬 된 하위 목록 (동일한 배열에 있음)에 삽입됩니다. 이 알고리즘은 평균 및 최악의 경우 복잡성이 0 (n ² )이므로 대규모 데이터 세트에는 적합하지 않습니다 .n 항목 수입니다.

삽입 정렬은 어떻게 작동합니까?

예를 들어 정렬되지 않은 배열을 사용합니다.

삽입 정렬은 처음 두 요소를 비교합니다.

14와 33이 모두 이미 오름차순임을 발견합니다. 현재 14는 정렬 된 하위 목록에 있습니다.

삽입 정렬은 앞으로 이동하여 33과 27을 비교합니다.

33이 올바른 위치에 있지 않음을 발견합니다.

33과 27을 교환합니다. 또한 정렬 된 하위 목록의 모든 요소를 확인합니다. 여기에서 정렬 된 하위 목록에는 14 개의 요소 만 있고 27은 14보다 큽니다. 따라서 정렬 된 하위 목록은 교체 후에도 정렬 된 상태로 유지됩니다.

이제 정렬 된 하위 목록에 14와 27이 있습니다. 다음으로 33과 10을 비교합니다.

이러한 값은 정렬 된 순서가 아닙니다.

그래서 우리는 그것들을 교환합니다.

그러나 스와핑은 27과 10을 정렬되지 않게 만듭니다.

따라서 우리는 그것들도 교환합니다.

다시 우리는 정렬되지 않은 순서로 14와 10을 찾습니다.

다시 교환합니다. 세 번째 반복이 끝날 때까지 4 개 항목의 정렬 된 하위 목록이 있습니다.

이 프로세스는 정렬되지 않은 모든 값이 정렬 된 하위 목록에 포함될 때까지 계속됩니다. 이제 삽입 정렬의 몇 가지 프로그래밍 측면을 살펴 보겠습니다.

연산

이제이 정렬 기술이 어떻게 작동하는지 더 큰 그림을 얻었으므로 삽입 정렬을 수행 할 수있는 간단한 단계를 도출 할 수 있습니다.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

의사 코드

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

C 프로그래밍 언어의 삽입 정렬 구현에 대해 알아 보려면 여기 를 클릭하십시오 .