[음악 재생] 

DOUG 로이드 : 그래서 삽입 정렬은 다른입니다 알고리즘은 우리가 배열을 정렬하는 데 사용할 수 있습니다. 이 알고리즘의 기본 개념 당신의 정렬 된 배열을 구축하는 것입니다 대신에, 밖으로 전환 부재 당신이가는대​​로 방법은 공간을 만들 수 있습니다. 이것은 약간 다릅니다 선택 정렬 또는 거품에서 정렬, 예를 들면, 여기서 우리의 위치를​​ 조정하고, 여기서 우리가 스왑을 만들고있어. 

이 경우 우리는 실제로있어 일을 슬라이딩 요소입니다 이상, 비켜. 이 알고리즘을 수행하는 방법 의사에서 작동? 그럼 그냥 임의로라고하자 배열의 첫 번째 요소는 정렬됩니다. 우리는 장소에 구축하고 있습니다. 

우리는 거 한 번에 하나의 요소를 이동하고 있고 를 구축, 그래서 먼저 우리는 참조 하나의 요소의 배열이다. 및 정의함으로써, 하나 요소 배열은 정렬됩니다. 

그리고 우리는이 과정을 반복합니다 until-- 우리는 다음과 같은 과정을 반복 할 것이다 모든 요소가 정렬 될 때까지. 다음 정렬되지 않은 요소로보고 정렬 된 부분에 삽입, 필요한 번호를 이동시킴으로써 방법 중 요소. 희망이 시각화 당신이 정확히 무엇을보고 도움이 될 것입니다 삽입 정렬로 진행. 

그래서 다시, 여기에 우리의있어 전체 정렬되지 않은 배열, 모든 요소는 적색으로 표시. 그리고 이제를 수행 할 수 우리의 의사의 단계. 우리가 할 첫 번째 일은, 우리는 전화한다 배열의 첫 번째 요소, 분류. 그래서 우리는 단지거야 말거야 다섯은 이제 분류하고 있습니다. 

그런 다음 우리는 다음을보고 배열의 정렬되지 않은 요소 우리는 삽입 할 정렬 된 부분으로, 요소를 통해 이동하여. 그래서 두 사람은 다음 정렬되지 않은 것입니다 배열의 요소입니다. 분명히 그것은 전에 속한 오, 그래서 우리는거야 무엇이야 종류의 두 번째 따로 두를 개최하고, 이상 다섯 가지를 이동 한 다음 두를 삽입 다섯 전에, 어디를 가야합니다. 그리고 지금 우리는 두 가지가 정렬됩니다 말할 수 있습니다. 

당신이 볼 수 있도록, 우리는 지금까지 만했습니다 배열의 두 요소로 보았다. 우리는 보았다하지 않은 전혀 휴식, 그러나 우리는했습니다 이 두 요소에 의해 분류되었다 변속기구의 방법. 

그래서 우리는 다시 프로세스를 반복합니다. 다음 정렬되지 않은 봐 요소, 즉 하나입니다. ,의는 잠시 그​​ 옆으로 잡아 보자 이상의 모든 이동하고 1 점을 추가하는 듯 그것은 어디 가야한다. 

다시 말하지만, 여전히, 우리는 오직했습니다 하나, 둘, 5 보았다. 우리는오고 다른 모르겠어요, 그러나 우리는이 세 가지 요소를 분류했습니다. 

다음으로 정렬되지 않은 요소는 세, 그래서 우리는 옆에 설정합니다. 우리는을 통해 이동합니다 우리 이는이 시간에 필요 이전과 같이 모든 것을 아니다 두 가지 경우, 그냥 다섯입니다. 그리고 우리는 세 가지 스틱 것이다, 둘 사이의 다섯. 

여섯 분류되지 않은 옆에 배열에 요소입니다. 그리고 사실 여섯 그래서, 다섯보다 큰 우리는 심지어 어떤 스와핑을 수행 할 필요가 없습니다. 우리는 오른쪽에 여섯 압정 수 있습니다 정렬 된 부분의 끝. 

마지막으로, 네 인 마지막으로 정렬되지 않은 요소입니다. 그래서 우리는 따로 설정할 것, 이상 이동 요소는 우리가 이상 이동해야 자신이 속한 위치를 다음 네 가지를 넣어. 그리고 지금, 보면 우리는 일종의했습니다 모든 요소. 삽입에 주목 종류, 우리는하지 않았다 앞뒤로 배열에서 이동합니다. 우리는 배열을 가로 질러 갔다 한 시간, 우리는 물건을 이동 우리가 이미 위해가 발생 거라고 새로운 요소를위한 공간을 확인합니다. 

그래서 최악의 경우입니다 삽입 정렬과 시나리오? 최악의 경우, 배열을 역순으로한다. 사용자는 n 개의 원소를 각각 이동해야 N 위치까지, 매 시간 우리 삽입을합니다. 즉 이동을 많이합니다. 

최상의 경우에서, 배열이 완벽하게 정렬됩니다. 그리고 일종의 무슨 일이 있었는지 등 예를 들어 다섯 여섯와, 우리는 단지 그것을 압정 수있는 곳 임의의 이동을하지 않고도, 우리는 본질적으로 그렇게 할 것입니다. 

당신이 상상하는 경우 우리의 어레이는 6을 통해 하나 우리는에 의해 시작 것 하나를 선언하는 정렬됩니다. 두 그래서 우리가 할 수있는 한 후 제공 하나, 둘,이 분류되어 잘 확인을 말한다. 세 가지 확인, 그래서 후 2 온다, 하나, 둘, 셋이 분류되어 있습니다. 

우리는 우리가있어, 어떤 스왑을하지 않을 그냥 임의의 라인을 이동 우리가 가서 사이의 분류 및 정렬되지 않은. 효과적으로 우리가 예에서와 마찬가지로, 우리가 진행하는, 파란색 요소를 선회. 따라서 최악의 경우 런타임은, 무슨 일이야? 우리가 각을 이동해야하는 경우, 기억 N 소자 아마도 N 위치, 희망이 당신을 제공합니다 최악의 경우는 그 아이디어 런타임은 N의 큰 O 제곱입니다. 

배열이 완벽하게되어있는 경우 분류, 우리 모두가해야 할 모든 단일 요소를 보면됩니다 한 번, 그리고, 우리는 완료. 따라서 최상의 경우에는, N의 오메가이다. 

나는 더그 로이드입니다. 이 CS50입니다.