똑똑한 코드 작성을 위한 실전 알고리즘

156

똑똑한 코드 작성을 위한 실전 알고리즘

for j in range(i,0,-1):

➋

if A[j-1] <= A[j]:

➌

break

A[j],A[j-1] = A[j-1],A[j]

➍

➊

i

에 대한

for

루프를 한 번 수행할 때마다

A[0 .. i

-

1]

이 정렬됨을 알 수 있다.

➋

j

는 인덱스 위치

i

에서

1

까지 감소한다.

➌

A[j

-

1]≤A[j]

일 때

A[j]

는 알맞은 위치를 찾았으므로 멈춘다.

➍

그렇지 않으면 해당 비순차적인 값들을 교환한다.

삽입 정렬은 삽입하려는 각 값이 이미 정렬된 모든 값보다 작을 때 가장 많은 작업을 한다. 삽

입 정렬에 대한 최악의 경우는 내림차순으로 정렬된 배열을 정렬할 때다. 각 하위 단계에서 비

교 (및 교환 ) 횟수가

1

씩 증가해 합계는 앞서 언급한 삼각수가 된다.

5.4

삽입 정렬과 선택 정렬의 성능

선택 정렬로

N

개 값을 정렬할 때 항상

1

/

2

×

N

2

-

1

/

2

×

N

회 비교와

N

–

1

회 교환이 일어난다.

삽입 정렬은 값 자체의 순서에 따라 성능이 다르므로 수행 횟수를 계산하기가 조금 더 복잡하

다. 평균적으로 삽입 정렬은 선택 정렬보다 성능이 좋다. 삽입 정렬에 대한 최악의 경우에는 값

이 내림차순으로 값으로 구성되어 있고 비교 횟수와 교환 횟수는

1

/

2

×

N

2

-

1

/

2

×

N

회가 된다.

무엇을 하든 간에 삽입 정렬과 선택 ...