[알고리즘] 삽입정렬
3. 삽입정렬
data 정렬시 앞의 data들은 이미 정렬이 완료되었다는 가정으로, 비교연산 등 순회과정을 진행할때마다 적당한 위치에 data를 정렬하는 방식이다.
정렬이 되어있다고 가정하기 때문에 순회과정에서 특정 조건을 만족할 경우, 곧바로 순회를 종료한다. 이 관점에서 특정 조건에서는 삽입정렬이 매우 효율적으로 적용될 수 있다.
예를 들어, 오름차순으로 data를 정렬한다고 가정해보자.
특정 지점의 data(아래 코드에서 array[i])는 한 순회를 할 때마다, 앞서 정렬된 data들과 비교과정을 거친다.
이미 정렬되어있는 배열상태에서 비교연산을 하므로, 특정 조건을 만족한다면(array[i]가 array[i+1]보다 작은 경우, 즉 오름차순 조건이 만족되는 경우) 곧바로 연산을 종료할 수 있다.
3-1. 시간복잡도 관점
시간복잡도 관점에서 O(N^2)이므로 다소 불리한 방법의 알고리즘이긴 하다.
그러나 삽입정렬은 앞선 정렬과는 달리 특정 조건, 즉 필요시에만 data를 바꾸는 정렬이다.
다만, 동일한 O(N^2)의 정렬 알고리즘에서는 가장 빠르고 효율적이며, 특히 데이터가 이미 정렬되어있는 상태에서 사용할 경우 그만큼 빠르게 원하는 결과를 얻을 수 있는 방법이다.
##selected array
## 1 2 3 4 5 6 7 8 9 10
array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
arrayLength = len(array)
for i in range(0, arrayLength-1):
j = i
while array[j] > array[j+1]:
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
j = j-1
print(array)
3-2. 참조강의
삽입정렬
https://www.youtube.com/watch?v=16I9Z7bS1iM&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=4
Author And Source
이 문제에 관하여([알고리즘] 삽입정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gyrbs22/알고리즘-삽입정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)