[Powered by Google Translate] [삽입 정렬]
[토미 MacWilliam] [하버드 대학]
[이 CS50.TV입니다]
가 삽입 정렬을 살펴, 숫자의 목록을 복용하고를 분류하는 알고리즘을 보자.
알고리즘, 기억은 단순히 작업을 달성하기위한 단계별 절차입니다.
삽입 정렬 뒤에 기본적인 아이디어는, 두 부분으로 목록을 분할하는 것입니다
정렬 부분과 정렬되지 않은 부분입니다.
>> 알고리즘의 각 단계에서 번호 이동
정렬되지 않은 부분에서 정렬 부분에
결국 때까지 전체 목록이 정렬됩니다.
23, 42, 4, 16, 8, 15 - 여기에 여섯 정렬되지 않은 숫자의 목록입니다.
이 숫자가 오름차순으로 모든 수 없습니다 때문에, 그것들은 정렬되지 않은하고 있습니다.
아직 정렬 시작되지 않았으므로, 우리는 6 요소를 우리의 정렬되지 않은 부분을 고려합니다.
>> 일단 정렬을 시작, 우리는 이들의 왼쪽에 이러한 분류 번호를 넣어드립니다.
자, 23, 목록의 첫 번째 요소로 시작해보세요.
우리는 아직 우리의 정렬 부분에 요소가 없습니다
그러니 단순히 우리의 정렬 부분의 시작과 끝으로 23 생각해 보자.
이제 우리의 정렬 부분은 한 번호 23을 가지고
우리의 정렬되지 않은 부분은이 다섯 가지 숫자가 있습니다.
의 지금 정렬 부분에 우리의 정렬되지 않은 부분을, 42에 다음 번호를 삽입 보자.
>> 이렇게하려면 우리는 23 42를 비교해야합니다 - 우리의 정렬 부분에서 유일한 요소를 지금까지.
42 23보다 큰, 그래서 우리는 간단하게 끝 42 추가 할 수 있습니다
목록의 정렬 부분의. 좋아요!
우리의 정렬 부분은 두 가지 요소가 있으며, 우리의 정렬되지 않은 부분은 4 원소 있습니다.
그래서, 정렬되지 않은 부분에 다음 요소, 이제 4로 이동 보자.
그래서,이는 정렬 부분에있는 배치해야 하는가?
>> 명심 해, 우리가 정렬 순서로이 번호를 게재 할
그래서 우리의 정렬 부분이 올바르게 항상 정렬 남아 있습니다.
우리는 42의 오른쪽에있는 4 배치한다면, 목록이 순서대로 될 것입니다.
자, 우리의 정렬 부분에 오른쪽에서 왼쪽으로 이동을 계속 하죠.
우리가 이동,의는 새로운 번호 공간을 확보 할 수있는 장소 다운 각 번호를 이동 보자.
좋아요, 4도 이하로 23, 우리는 하나 여기에 배치 할 수 없습니다.
가 23 오른쪽 한 곳으로 이동하자.
>> 우리가 정렬 부분의 첫 번째 슬롯에 4를 배치하고 싶은 의미한다.
목록에이 공간이 이미 비어에주의하십시오,
우리가 그들을 발생한 것처럼 우리는 정렬 요소를 아래로 이동되어서.
괜찮아요. 그래서, 우리는 우리가 반이야.
가 정렬 부분에 16을 삽입하여 알고리즘을 계속 보자.
16 이하 42 이상 그러니, 오른쪽에있는 42 이동하게됩니다.
16 이하 23 이상 그러니, 또한 요소를 이동하게 있습니다.
>> 지금, 16는 4보다 큽니다. 우리는 4 23 사이에 16를 삽입하려면 같은 그래서 같습니다.
오른쪽에서 왼쪽으로 목록의 정렬 부분을 통해 이동하지만,
4 수보다 작습니다 우리가 본 최초의 번호입니다
우리는 삽입 할 노력하고 있습니다.
자, 이제 우리는이 빈 슬롯에 16을 삽입 할 수 있습니다
하는 기억, 우리는 위에 정렬 부분에 움직이는 요소에 의해 생성 한
우리는 그들을 발생했습니다 있습니다.
>> 괜찮아요. 이제, 우리는 네 정렬 요소와 두 개의 정렬되지 않은 요소가 있습니다.
자,이 정렬 부분에 8 이동하세요.
여덟 미만 42.
여덟 미만 23.
그리고 8 이하 16 세입니다.
그러나 8 4보다 더 크다.
그래서, 우리는 우리가 4 16 사이에 8을 삽입하고 싶습니다.
15 - 그리고 지금 우리가 정렬하려면 왼쪽 하나 더 요소가 있습니다.
열 다섯 미만 42
열 다섯 미만이 23.
그리고 15 이하 16입니다.
하지만 15은 8보다 큽니다.
>> 우리가 우리의 마지막 삽입을하려는 자, 여기 있습니다.
그리고 우리는 끝났어.
우리는 정렬되지 않은 부분에 더 많은 요소가 없습니다
우리의 정렬 부분은 올바른 순서입니다.
번호는 최소에서 최대로 정렬됩니다.
자, 우리가 방금 수행 한 단계를 설명합니다 어떤 의사를 살펴 보자.
>> 1 번 라인에, 우리는 목록의 각 요소를 통해 반복해야합니다 것을 알 수 있습니다
첫 번째 경우를 제외하고 정렬되지 않은 부분의 첫 번째 요소부터 간단하게 될 것입니다
정렬 부분의 첫 번째 요소입니다.
라인 2와 3에서 우리는 정렬되지 않은 부분에 현재 장소 추적을 유지하고 있습니다.
요소는 우리가 현재 정렬 부분으로 이동하는 수를 나타냅니다
와 j는 정렬되지 않은 부분에 색인을 나타냅니다.
>> 4 호선에, 우리는 오른쪽에서 왼쪽으로 정렬 부분을 반복하고 있습니다.
우리는 우리의 현재 위치의 왼쪽에있는 요소를 한 번 반복 중지하려면
우리가 삽입하려는 요소보다 작습니다.
5 호선에서 우리는 오른쪽으로 한 공간을 발생 각 요소를 이동하고있다.
우리가 첫 번째 요소를 찾을 때 방법은, 우리는에 삽입 할 수있는 명확한 공간이됩니다
우리가 움직이기 요소보다.
6 호선에서, 우리는 정렬 부분을 왼쪽으로 이동을 계속하기 위해 카운터를 업데이트하고 있습니다.
마지막으로, 7 호선에, 우리는 목록의 정렬 부분에 요소를 삽입하고 있습니다.
>> 우리는이 위치 제이에 삽입 할 수 괜찮 알고
우리는 이미 오른쪽으로가 한 공간이 될하는 데 사용되는 요소를 이동 한 때문입니다.
명심 해, 우리가, 오른쪽에서 왼쪽으로 정렬 부분을 통해 이동
그러나 우리는 왼쪽에서 오른쪽으로 정렬되지 않은 부분을 통해 이동하고 있습니다.
괜찮아요. 의 지금 알고리즘했다는 실행 시간을 살펴 보자.
우리는 먼저이 알고리즘은 최악의 경우에 실행이 얼마나가 걸리나요 질문을 요청할 것입니다.
우리가 큰 O 표기법으로이 실행 시간을 나타냅니다 것을 기억합니다.
목록을 정렬하기 위해, 우리는 정렬되지 않은 부분의 요소를 통해 반복했다
잠재적으로 정렬 부분의 모든 요소를​​ 통해 이러한 요소 각각에 대해.
직관적으로, O (N ^ 2) 작업처럼 소리.
>> 우리의 의사를 살펴보면, 우리는 다른 루프 안에 중첩 루프를 가지고
있는 사실은, O (N ^ 2) 작업처럼 들린다.
그러나, 목록의 정렬 부분은 매우 말까지 전체 목록을 포함하지 않았다.
그러나, 우리는 잠재적으로 정렬 부분의 처음에 새로운 요소를 삽입 할 수
알고리즘의 모든 반복에,
이는 우리가 정렬 부분에 현재 각 요소를보고해야 할 것을 의미합니다.
그래서 우리가 잠재적으로 두 번째 요소에 대해 하나의 비교를 만들 수 의미
세 번째 요소 두 비교 등.
따라서 단계의 총 수는 1에서 목록 마이너스 1의 길이에 정수의 합계입니다.
우리는 합류로이를 대표 할 수 있습니다.
>> 우리는 여기 summations로 이동되지 않습니다,하지만이 합류과 동일하다고 판명
N / 2 - 동등한 N ^ 이분의이 있습니다 2 이상 - N (1 N).
점근 런타임에 대해 얘기하면,
이 N ^ 2 학기는 N 용어를 지배 할 것이다.
따라서, 삽입 정렬은 빅 O (N ^ 2)입니다.
우리가 이미 정렬 된 목록에 삽입 정렬을 실행합니다.
이 경우, 우리는 단순히 왼쪽에서 오른쪽으로 정렬 된 부분을 구축 할.
그럼, 우리는 N 단계의 순서를해야합니다.
>> 즉, 삽입 정렬 n의 최선의 성능을 의미합니다
있는 우리는 Ω (n)이 함께 나타냅니다.
그래서, 삽입 정렬을 위해 야
단지 여러 알고리즘 중 하나는 우리는 목록을 정렬하는 데 사용할 수 있습니다.
내 이름은 토미이고,이 CS50입니다.
[CS50.TV]
아, 당신은 한 번가 시작되는 중지 할 수 없습니다.
아, 우리는 그렇게 했어요 - >> 붐!