삽입정렬
데이터를 적절한 곳에다가 삽입하는 정렬이다. 삽입정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적이다.
cf. 선택정렬은 현재 데이터의 상태과 상관없이 무조건 모든 원소를 비교한다.
삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 값을 만나면 그 위치에서 멈추면 된다. (특정 데이터의 왼쪽 부분은 이미 정렬이 된 상태이기 때문이다.)
인덱스가 0인 데이터는 이미 정렬되어있다고 가정하고 해당 위치에 고정시킨다.
코드
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):
if array[j] < array[j-1]: array[j], array[j-1] = array[j-1], array[j]
else: break # 자신보다 작은 값을 만나면 정지
print(array) # [0,1,2,3,4,5,6,7,8,9]
시간복잡도
최선의 경우(데이터가 대부분 정렬되어 있는 경우) : Ω(N)
최악의 경우 : O(N^2)
'자료구조 및 알고리즘' 카테고리의 다른 글
[자료구조 및 알고리즘] 계수정렬(Counting Sort) (0) | 2023.07.19 |
---|---|
[자료구조 및 알고리즘] 퀵정렬 (Quick Sort) (0) | 2023.07.19 |
[자료구조 및 알고리즘] 선택정렬 (Selection Sort) (0) | 2023.07.19 |
[자료구조 및 알고리즘] BFS (Breadth First Search, 너비우선탐색) (0) | 2023.07.19 |
[자료구조 및 알고리즘] DFS (Depth First Search, 깊이우선탐색) (0) | 2023.07.13 |
삽입정렬
데이터를 적절한 곳에다가 삽입하는 정렬이다. 삽입정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적이다.
cf. 선택정렬은 현재 데이터의 상태과 상관없이 무조건 모든 원소를 비교한다.
삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 값을 만나면 그 위치에서 멈추면 된다. (특정 데이터의 왼쪽 부분은 이미 정렬이 된 상태이기 때문이다.)
인덱스가 0인 데이터는 이미 정렬되어있다고 가정하고 해당 위치에 고정시킨다.
코드
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):
if array[j] < array[j-1]: array[j], array[j-1] = array[j-1], array[j]
else: break # 자신보다 작은 값을 만나면 정지
print(array) # [0,1,2,3,4,5,6,7,8,9]
시간복잡도
최선의 경우(데이터가 대부분 정렬되어 있는 경우) : Ω(N)
최악의 경우 : O(N^2)
'자료구조 및 알고리즘' 카테고리의 다른 글
[자료구조 및 알고리즘] 계수정렬(Counting Sort) (0) | 2023.07.19 |
---|---|
[자료구조 및 알고리즘] 퀵정렬 (Quick Sort) (0) | 2023.07.19 |
[자료구조 및 알고리즘] 선택정렬 (Selection Sort) (0) | 2023.07.19 |
[자료구조 및 알고리즘] BFS (Breadth First Search, 너비우선탐색) (0) | 2023.07.19 |
[자료구조 및 알고리즘] DFS (Depth First Search, 깊이우선탐색) (0) | 2023.07.13 |