정렬 - 삽입정렬(Insertion Sort)

삽입정렬(Insertion Sort) : 리스트의 원소를 정렬이 완료된 부분에서 맞는 자리를 찾아 삽입하여 정렬

 

[python]

 

1) 오름차순

arr = [9,2,1,4,10,3,7,5,6,8]

for i in range(1,len(arr)) :        #정렬할 원소 인덱스 선택
    temp = arr[i]                       #삽입하여 정렬할 원소를 저장
    for j in range(i, -1, -1) :         #정렬된 부분 인덱스 선택
        if arr[j-1] > temp :                #정렬한 원소보다 크면 뒤로 미룸
            arr[j] = arr[j-1]
        else :                              #크지 않다면 멈추고
            break
    arr[j] = temp                           #그 자리에 정렬할 원소를 삽입

print(arr)

 

2) 내림차순

arr = [9,2,1,4,10,3,7,5,6,8]

for i in range(1,len(arr)) :        #정렬할 원소 인덱스 선택
    temp = arr[i]                       #삽입하여 정렬할 원소를 저장
    for j in range(i, -1, -1) :         #정렬된 부분 인덱스 선택
        if arr[j-1] < temp :                #정렬한 원소보다 작으면 뒤로 미룸
            arr[j] = arr[j-1]
        else :                              #작지 않다면 멈추고
            break
    arr[j] = temp                           #그 자리에 정렬할 원소를 삽입

print(arr)