정렬 알고리즘 - 삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.

시간 복잡도는 O(N^2)이며 최선의 경우 O(N)

 

 

 

 

 

 

답안 예시

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1) # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break
            
print(array)

 

작성한 답안

numList = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(numList)):
    for j in range(0, i):
        if numList[j] > numList[i]:
            numList[j], numList[i] = numList[i], numList[j]
            
print(numList)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

출처 : https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4