알고리즘의 시작 정렬 알고리즘(sort Algorithm) 3. 삽입 정렬

 

 

 

세 번째 시간입니다.

 

오늘은 삽입 정렬 가지고 왔습니다.

마지막에 앞서서 봤던 선택, 버블 정렬과

오늘 볼 삽입 정렬들을 비교 해보겠습니다ㅎ

 

 

삽입 정렬

---

삽입 정렬은 앞선 정렬들 보다는 더 나은(?) 정렬 알고리즘이라고 볼 수 있는데요.

 

삽입정렬은 말 그대로

각 숫자를 들어가야 할 곳에 삽입하는 알고리즘입니다.

 

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

자 똑같은 데이터가 있습니다.

 

처음으로 인덱스 1에 있는 숫자를 가지고 왼쪽의 있는 수 와 비교합니다.

 

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

 

그 자리에 그대로 있겠네요.

인덱스 2에 있는 수와 왼쪽의 있는 데이터들과 비교하면

들어갈 자리가 명확하죠.

 

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

 

이런 식으로

 

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

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

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

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

.

.

.

정리가 됩니다.

왜 이 삽입 정렬이 앞서서 본 두 개의 정렬보다 더 낫다고 했냐면

비교해 볼 숫자의 왼편은 이미 정렬이 되어있기 때문에

비교한 숫자를 그냥 적절한 위치에 넣기만 하면 되거든요.

 

코드로 보시죠

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

for i in range(len(data)-1):
    j=i
    while(j>=0 and data[j]>data[j+1]):
        temp = data[j]
        data[j] = data[j+1]
        data[j+1] = temp
        j-=1
print(data)

전체 반복문을 하나 해주고요값을 비교할 수 있게 i를 사용할 변수 j에 넣고j옆에 있는 모든 변수랑 비교해서 그 자리에 넣는 거예요.

 

삽입 정렬 또한 big O notation은 O(N^2)입니다.

 

 

 

세 가지 비교

---

이제까지 배운 정렬 알고리즘은 모두 O(N^2)의 복잡도를 가지고 있는데요.

 

예를 들어[2,3,4,5,6,7,8,9,10,1]와 같은 데이터가 있다고 해보겠습니다.

 

선택 정렬의 경우다른 데이터를 가지고 있을 때와 같은 동작을 반복하죠전체를 비교하고뒤의 하나를 뺀 전체를 비교하고뒤에서 하나 빼고 전체를 비교하고반복

 

버블 정렬일 경우도 마찬가지입니다.차례대로 전체 비교하고뒤에 하나를 빼고 전체를 비교하고반복

 

삽입 정렬의 경우한 번씩만 보면 됩니다.인덱스 0과 1 비교인덱스 1과 2 비교 쭈욱 바뀌지 않다가마지막에 1을 발견하고는 바뀌는 거죠.

 

이와 같이 좌측이 정렬이 되어있을 경우에 삽입 정렬은 엄청난 파워를 보여줍니다.

 

이해가 안 가신다면 갓 '동빈나' 유튜브에 가서 동영상을 시청하세요!

 

오늘은 여기까지!태클은 언제나 환영입니다!