삽입 정렬을 사용하여 계산 비교

Question

배열을 정렬하는 동안 총 비교를 계산하는 임무가 있습니다. 정수 배열 {8, 2, 1, 4, 3, 5}가 주어지면 왼쪽부터 두 번째 요소부터 시작하여 첫 번째 요소와 비교하여 세 번째 요소를 이전 두 요소와 비교하고 각 요소를 어디에 배치해야하는지 결정할 수 있습니다.

총 15 개의 비교를 계산하지만 정확한 비교 횟수는 10입니다. 이 정렬을 선택 정렬로 정렬하는 것은 15 가지 비교이므로이 유형에서 삽입 정렬을 사용하면 어떻게 그리고 왜 비교 수가 달라 집니까? 예?

Answer 1

삽입 정렬이 어떻게 작동하는지 이해하고 있습니다.

mark first element as sorted 
for each unsorted element 
    'extract' the element 
    for i = lastSortedIndex to 0 
    if currentSortedElement > extractedElement 
     move sorted element to the right by 1 
    else: insert extracted element 

초기 배열 : [8, 2, 1, 4, 3, 5]

비교 1 2 < 8 배열 : [2, 8, 1, 4, 3, 5]

비교 2 1 < 8 배열 : [2, 1, 8, 4, 3, 5]

삽입 정렬이 의사 코드를 사용

비교 3 : 1 < 2 어레이 : [1, 2, 8, 4, 3, 5]

비교 4 : 4 < 8 배열 : [1, 2, 4, 8, 3, 5]

비교 5 4 > 2 배열 : [1, 2, 4, 8, 3, 5]

비교 6 3 < 8 배열 : [1, 2, 4, 3, 8, 5]

비교 7 3 < 4 어레이 : [1, 2, 3, 4, 8, 5]

비교 8 : 3 > 2 배열 : 0 1,231,138,264,

비교 9 : 5 < 8 배열 : [1, 2, 3, 4, 5, 8]

비교 10 : 5 > 4 배열 : [1, 2, 3, 4, 5, 8]

결과 순위!