>> [음악 재생]
>> DOUG 로이드 : 그래서 삽입 정렬은 다른입니다 알고리즘은 우리가 배열을 정렬하는 데 사용할 수 있습니다.
이 알고리즘의 기본 개념 당신의 정렬 된 배열을 구축하는 것입니다
대신에, 밖으로 전환 부재 당신이가는대​​로 방법은 공간을 만들 수 있습니다.
이것은 약간 다릅니다 선택 정렬 또는 거품에서
정렬, 예를 들면, 여기서 우리의 위치를​​ 조정하고,
여기서 우리가 스왑을 만들고있어.
>> 이 경우 우리는 실제로있어 일을 슬라이딩 요소입니다
이상, 비켜.
이 알고리즘을 수행하는 방법 의사에서 작동?
그럼 그냥 임의로라고하자 배열의 첫 번째 요소는 정렬됩니다.
우리는 장소에 구축하고 있습니다.
>> 우리는 거 한 번에 하나의 요소를 이동하고 있고 를 구축, 그래서 먼저 우리는 참조
하나의 요소의 배열이다.
및 정의함으로써, 하나 요소 배열은 정렬됩니다.
>> 그리고 우리는이 과정을 반복합니다 until-- 우리는 다음과 같은 과정을 반복 할 것이다
모든 요소가 정렬 될 때까지.
다음 정렬되지 않은 요소로보고 정렬 된 부분에 삽입,
필요한 번호를 이동시킴으로써 방법 중 요소.
희망이 시각화 당신이 정확히 무엇을보고 도움이 될 것입니다
삽입 정렬로 진행.
>> 그래서 다시, 여기에 우리의있어 전체 정렬되지 않은 배열,
모든 요소는 적색으로 표시.
그리고 이제를 수행 할 수 우리의 의사의 단계.
우리가 할 첫 번째 일은, 우리는 전화한다 배열의 첫 번째 요소, 분류.
그래서 우리는 단지거야 말거야 다섯은 이제 분류하고 있습니다.
>> 그런 다음 우리는 다음을보고 배열의 정렬되지 않은 요소
우리는 삽입 할 정렬 된 부분으로,
요소를 통해 이동하여.
그래서 두 사람은 다음 정렬되지 않은 것입니다 배열의 요소입니다.
분명히 그것은 전에 속한 오, 그래서 우리는거야 무엇이야
종류의 두 번째 따로 두를 개최하고, 이상 다섯 가지를 이동 한 다음 두를 삽입
다섯 전에, 어디를 가야합니다.
그리고 지금 우리는 두 가지가 정렬됩니다 말할 수 있습니다.
>> 당신이 볼 수 있도록, 우리는 지금까지 만했습니다 배열의 두 요소로 보았다.
우리는 보았다하지 않은 전혀 휴식, 그러나 우리는했습니다
이 두 요소에 의해 분류되었다 변속기구의 방법.
>> 그래서 우리는 다시 프로세스를 반복합니다.
다음 정렬되지 않은 봐 요소, 즉 하나입니다.
,의는 잠시 그​​ 옆으로 잡아 보자 이상의 모든 이동하고 1 점을 추가하는 듯
그것은 어디 가야한다.
>> 다시 말하지만, 여전히, 우리는 오직했습니다 하나, 둘, 5 보았다.
우리는오고 다른 모르겠어요, 그러나 우리는이 세 가지 요소를 분류했습니다.
>> 다음으로 정렬되지 않은 요소는 세, 그래서 우리는 옆에 설정합니다.
우리는을 통해 이동합니다 우리 이는이 시간에 필요
이전과 같이 모든 것을 아니다 두 가지 경우, 그냥 다섯입니다.
그리고 우리는 세 가지 스틱 것이다, 둘 사이의 다섯.
>> 여섯 분류되지 않은 옆에 배열에 요소입니다.
그리고 사실 여섯 그래서, 다섯보다 큰 우리는 심지어 어떤 스와핑을 수행 할 필요가 없습니다.
우리는 오른쪽에 여섯 압정 수 있습니다 정렬 된 부분의 끝.
>> 마지막으로, 네 인 마지막으로 정렬되지 않은 요소입니다.
그래서 우리는 따로 설정할 것, 이상 이동 요소는 우리가 이상 이동해야
자신이 속한 위치를 다음 네 가지를 넣어.
그리고 지금, 보면 우리는 일종의했습니다 모든 요소.
삽입에 주목 종류, 우리는하지 않았다
앞뒤로 배열에서 이동합니다.
우리는 배열을 가로 질러 갔다 한 시간, 우리는 물건을 이동
우리가 이미 위해가 발생 거라고 새로운 요소를위한 공간을 확인합니다.
>> 그래서 최악의 경우입니다 삽입 정렬과 시나리오?
최악의 경우, 배열을 역순으로한다.
사용자는 n 개의 원소를 각각 이동해야 N 위치까지, 매 시간 우리
삽입을합니다.
즉 이동을 많이합니다.
>> 최상의 경우에서, 배열이 완벽하게 정렬됩니다.
그리고 일종의 무슨 일이 있었는지 등 예를 들어 다섯 여섯와,
우리는 단지 그것을 압정 수있는 곳 임의의 이동을하지 않고도,
우리는 본질적으로 그렇게 할 것입니다.
>> 당신이 상상하는 경우 우리의 어레이는 6을 통해 하나
우리는에 의해 시작 것 하나를 선언하는 정렬됩니다.
두 그래서 우리가 할 수있는 한 후 제공 하나, 둘,이 분류되어 잘 확인을 말한다.
세 가지 확인, 그래서 후 2 온다, 하나, 둘, 셋이 분류되어 있습니다.
>> 우리는 우리가있어, 어떤 스왑을하지 않을 그냥 임의의 라인을 이동
우리가 가서 사이의 분류 및 정렬되지 않은.
효과적으로 우리가 예에서와 마찬가지로, 우리가 진행하는, 파란색 요소를 선회.
따라서 최악의 경우 런타임은, 무슨 일이야?
우리가 각을 이동해야하는 경우, 기억 N 소자 아마도 N 위치,
희망이 당신을 제공합니다 최악의 경우는 그 아이디어
런타임은 N의 큰 O 제곱입니다.
>> 배열이 완벽하게되어있는 경우 분류, 우리 모두가해야 할
모든 단일 요소를 보면됩니다 한 번, 그리고, 우리는 완료.
따라서 최상의 경우에는, N의 오메가이다.
>> 나는 더그 로이드입니다.
이 CS50입니다.