참고:이것은 Ruby로 다양한 정렬 알고리즘을 구현하는 방법을 살펴보는 시리즈의 4부입니다. 1부에서는 버블 정렬, 2부에서는 선택 정렬, 3부에서는 병합 정렬을 살펴보았습니다.
데이터 정렬을 위한 다양한 방법론을 계속 탐색하면서 삽입 정렬로 전환합니다. 삽입 정렬을 좋아하는 데에는 여러 가지 이유가 있습니다! 첫째, 삽입 정렬이 안정적입니다. , 이는 동일한 키를 가진 요소의 상대적 순서를 변경하지 않음을 의미합니다. 또한 현재 위치 알고리즘입니다. , 이는 정렬된 요소를 저장할 새 배열을 생성하지 않음을 의미합니다. 마지막으로 삽입 정렬은 구현하기에 매우 간단한 알고리즘입니다. 곧 보게 될 것입니다!
왜 케어
여기에서 깨진 레코드처럼 들리는 것을 피하기는 어렵지만 이전 모든 게시물에서 논의한 것처럼 데이터를 정렬하는 다양한 메커니즘과 다양한 방법 각각의 장단점을 이해하는 것이 중요합니다. 예를 들어, 삽입 정렬은 큰 데이터 세트에는 그다지 유용하지 않지만(아래에서 더 자세히 살펴보겠습니다), 작은 데이터 세트와 이미 정렬에 근접한 데이터 세트에는 괜찮고 매우 효율적일 수 있습니다. 구현 과정을 살펴보고 나면 그 이유를 알게 될 것입니다. 물론, 선택한 프로그래밍 언어가 정렬을 위해 제공하는 기본 제공 방법을 사용하는 경우가 많지만 짝 프로그램 연습이나 시간 복잡성과 관련된 인터뷰 질문으로 나타날 수 있습니다. 운 좋게도 이 게시물을 마칠 때쯤이면 삽입 정렬을 코딩하고 시간 복잡성을 쉽게 이해할 수 있을 것입니다.
시각적 표현
코딩을 시작하기 전에 다음 비디오를 확인하는 것이 좋습니다. 그것은 춤을 활용한 삽입 정렬을 설명하고 개인적으로 충분하지 않습니다! :)
코드 단계별 안내
코드를 살펴보겠습니다!
def insertion_sort(array)
for i in 1...(array.length) # Step 1
j = i # Step 2
while j > 0 # Step 3
if array[j-1] > array[j] # Step 4
temp = array[j]
array[j] = array[j-1]
array[j-1] = temp
else
break
end
j = j - 1 # Step 5
end
end
return array
end
1단계:
for로 시작합니다. 변수 i를 설정하는 루프 1로 설정하고 i까지 계속 증가 배열의 길이와 같습니다.
2단계:
다른 변수 j를 만듭니다. 값 1로 초기화합니다(i 입니다.
3단계:
다음으로 중첩된 while이 있습니다. j만큼 계속되는 루프 0보다 큽니다. j로 시작하기 때문에 1과 같으면 이것이 적어도 한 번 실행된다는 것을 알고 있습니다.
4단계:
if... else 블록이 처음에는 무섭게 보일 수 있지만 걱정하지 마십시오. 일단 살펴보고 나면 이해가 될 것입니다(그리고 언제든지 YouTube 댄스 예를 다시 방문할 수 있습니다!).
if의 경우 조건, 우리는 [j-1] array[j]보다 큽니다. . j 이후 현재 1이면 기본적으로 array[0]를 비교합니다. array[1] 포함 . 이는 배열의 처음 두 요소를 비교하기 때문에 의미가 있습니다.
첫 번째 요소(array[0] )이 다음 것보다 큽니다(array[1]). ) 그러면 당연히 스왑이 필요합니다. 이는 if 내에서 발생합니다. 차단하다. 그러나 array[0]의 값이 array[1]의 값보다 작습니다. , 그럼 대단해! 이미 정렬되어 있으므로 아무 것도 할 필요가 없으므로 break를 누르기만 하면 됩니다. else에서 차단합니다.
5단계:
여기에서 j를 감소시킵니다. . 이제 for로 돌아갑니다. 루프 및 i 이제 2가 됩니다. . array[1]를 비교하는 방법을 상상할 수 있습니다. array[2] 포함 while 내의 첫 번째 반복 루프를 실행한 다음 실제로 while j 2에서 시작됨 대 1 .
실제 데이터의 예
다음 예제 배열을 사용하여 이 코드를 살펴보겠습니다. [5,7,2,10,9,12]
첫 번째 반복에서는 5를 비교할 것입니다. 및 7 . 5 < 7 이후 , if/else 계속 진행합니다.
다음 반복에서는 7을 비교합니다. 및 2 . 이제 이 값을 바꿔야 하므로 [5, 2, 7, 10, 9, 12]가 됩니다. . 그런 다음 2 다시 5 [2, 5, 7, 10, 9, 12]로 끝나려면 .
for 내의 다음 반복에서 루프에서 10을 비교할 것입니다. 및 7 -- 야! 그것들은 이미 정리되어 있습니다.
계속해서 10을 비교합니다. 및 9 교환할 필요가 있음을 확인합니다. 그런 다음 7 9보다 작습니다. , 따라서 다른 스왑을 수행할 필요가 없습니다. 이제 [2, 5, 7, 9, 10, 12]만 남습니다. .
마지막 반복은 12를 찾습니다. , 10보다 큼 , 그래서 짜잔! 완료 및 정렬되었습니다.
성과 분석
우리가 살펴본 일부 정렬 알고리즘, 즉 버블 정렬은 실생활에서 거의 실행되지 않지만 삽입 정렬은 합리적인 솔루션이 될 수 있습니다. 배열이 이미 정렬되어 있다고 상상해보십시오. 삽입 정렬은 매우 빠르고 효율적으로 실행됩니다. 반대로 배열을 역순으로 정렬해야 하는 경우 어떻게 됩니까? 그것은 삽입 정렬의 악몽 같은 상황이 될 것입니다.
배열이 이미 정렬된 경우 삽입 정렬 코드는 O(n)에서 실행됩니다. n만 반복해야 하기 때문에 타임스. 이 문제를 해결하려면 puts i를 추가하세요. 메소드 상단에서 이미 정렬된 배열을 전달하는 프로그램을 실행합니다.
배열이 역 정렬되면 삽입 정렬 코드는 O(n^2)에서 실행됩니다. 이것을 머리로 시각화할 수 있습니다. 연속적으로 교체해야 하므로 if 모든 단일 요소에 대한 조건. 좋아! 다시 한 번 역 정렬된 배열을 전달하고 출력되는 카운터 변수를 만들어 자유롭게 시도해 보십시오.
최악의 경우는 O(n^2)이지만 이는 버블 정렬과 선택 정렬에서 동일하므로 일반적으로 삽입 정렬이 선호됩니다. 이는 우리가 보았듯이 최상의 경우가 O(n)일 수 있기 때문입니다. , 선택 정렬의 가장 좋은 경우는 O(n^2)입니다. . 삽입 정렬도 버블 정렬보다 스왑 횟수가 적기 때문에 이 전투에서 승리합니다.
마무리
이 게시물이 도움이 되었기를 바라며 삽입 정렬의 장단점과 알고리즘이 어떻게 작동하는지 이해하는 데 자신감을 갖기를 바랍니다. 여전히 더 가려우면 위키피디아 페이지에서 삽입 정렬을 확인하는 것이 좋습니다.