삽입 정렬

📌삽입 정렬

특정한 데이터를 적절한 위치에 삽입

삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 효율적

선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸어서 비효율적

 

삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정

 

삽입 정렬은 두 번째 데이터부터 시작, 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단

삽입하는 과정을 N-1번 반복하게 되면 모든 데이터가 정렬(첫 번째 데이터는 이미 정렬이므로 N번이 아닌 N-1번)

 

📌삽입 정렬의 특징

정렬이 이루어진 원소는 항상 오름차순 유지

따라서 특정한 데이터가 삽입될 위치를 정할 때(삽입될 위치를 찾기 위해 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 됨

 

자신보다 왼쪽에 있는 데이터들은 이미 정렬된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 살펴볼 것도 없이 그 자리에 삽입

 

📌삽입 정렬의 시간 복잡도

삽입 정렬: O(N²)

 

선택 정렬: O(N²)

 

동일하지만 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작

최선의 경우 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까지 감소하며 반복
        if array[j] < array[j - 1]:  # 자신 왼쪽과 크기를 비교하여 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else:  # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬