1
00:00:00,000 --> 00:00:02,826
>> [음악 재생]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG 로이드 : 그래서 삽입 정렬은 다른입니다
알고리즘은 우리가 배열을 정렬하는 데 사용할 수 있습니다.

4
00:00:09,370 --> 00:00:12,350
이 알고리즘의 기본 개념
당신의 정렬 된 배열을 구축하는 것입니다

5
00:00:12,350 --> 00:00:19,670
대신에, 밖으로 전환 부재
당신이가는대​​로 방법은 공간을 만들 수 있습니다.

6
00:00:19,670 --> 00:00:22,240
이것은 약간 다릅니다
선택 정렬 또는 거품에서

7
00:00:22,240 --> 00:00:25,460
정렬, 예를 들면, 여기서
우리의 위치를​​ 조정하고,

8
00:00:25,460 --> 00:00:26,910
여기서 우리가 스왑을 만들고있어.

9
00:00:26,910 --> 00:00:29,760
>> 이 경우 우리는 실제로있어
일을 슬라이딩 요소입니다

10
00:00:29,760 --> 00:00:31,390
이상, 비켜.

11
00:00:31,390 --> 00:00:34,030
이 알고리즘을 수행하는 방법
의사에서 작동?

12
00:00:34,030 --> 00:00:37,646
그럼 그냥 임의로라고하자
배열의 첫 번째 요소는 정렬됩니다.

13
00:00:37,646 --> 00:00:38,770
우리는 장소에 구축하고 있습니다.

14
00:00:38,770 --> 00:00:42,660
>> 우리는 거 한 번에 하나의 요소를 이동하고 있고
를 구축, 그래서 먼저 우리는 참조

15
00:00:42,660 --> 00:00:43,890
하나의 요소의 배열이다.

16
00:00:43,890 --> 00:00:47,720
및 정의함으로써, 하나
요소 배열은 정렬됩니다.

17
00:00:47,720 --> 00:00:50,850
>> 그리고 우리는이 과정을 반복합니다 until--
우리는 다음과 같은 과정을 반복 할 것이다

18
00:00:50,850 --> 00:00:52,900
모든 요소가 정렬 될 때까지.

19
00:00:52,900 --> 00:00:57,770
다음 정렬되지 않은 요소로보고
정렬 된 부분에 삽입,

20
00:00:57,770 --> 00:01:01,209
필요한 번호를 이동시킴으로써
방법 중 요소.

21
00:01:01,209 --> 00:01:03,750
희망이 시각화
당신이 정확히 무엇을보고 도움이 될 것입니다

22
00:01:03,750 --> 00:01:05,980
삽입 정렬로 진행.

23
00:01:05,980 --> 00:01:08,010
>> 그래서 다시, 여기에 우리의있어
전체 정렬되지 않은 배열,

24
00:01:08,010 --> 00:01:10,970
모든 요소는 적색으로 표시.

25
00:01:10,970 --> 00:01:13,320
그리고 이제를 수행 할 수
우리의 의사의 단계.

26
00:01:13,320 --> 00:01:16,970
우리가 할 첫 번째 일은, 우리는 전화한다
배열의 첫 번째 요소, 분류.

27
00:01:16,970 --> 00:01:20,920
그래서 우리는 단지거야 말거야
다섯은 이제 분류하고 있습니다.

28
00:01:20,920 --> 00:01:24,570
>> 그런 다음 우리는 다음을보고
배열의 정렬되지 않은 요소

29
00:01:24,570 --> 00:01:27,610
우리는 삽입 할
정렬 된 부분으로,

30
00:01:27,610 --> 00:01:29,750
요소를 통해 이동하여.

31
00:01:29,750 --> 00:01:33,470
그래서 두 사람은 다음 정렬되지 않은 것입니다
배열의 요소입니다.

32
00:01:33,470 --> 00:01:36,250
분명히 그것은 전에 속한
오, 그래서 우리는거야 무엇이야

33
00:01:36,250 --> 00:01:41,580
종류의 두 번째 따로 두를 개최하고,
이상 다섯 가지를 이동 한 다음 두를 삽입

34
00:01:41,580 --> 00:01:43,210
다섯 전에, 어디를 가야합니다.

35
00:01:43,210 --> 00:01:45,280
그리고 지금 우리는 두 가지가 정렬됩니다 말할 수 있습니다.

36
00:01:45,280 --> 00:01:48,400
>> 당신이 볼 수 있도록, 우리는 지금까지 만했습니다
배열의 두 요소로 보았다.

37
00:01:48,400 --> 00:01:50,600
우리는 보았다하지 않은
전혀 휴식, 그러나 우리는했습니다

38
00:01:50,600 --> 00:01:54,582
이 두 요소에 의해 분류되었다
변속기구의 방법.

39
00:01:54,582 --> 00:01:56,410
>> 그래서 우리는 다시 프로세스를 반복합니다.

40
00:01:56,410 --> 00:01:58,850
다음 정렬되지 않은 봐
요소, 즉 하나입니다.

41
00:01:58,850 --> 00:02:04,010
,의는 잠시 그​​ 옆으로 잡아 보자
이상의 모든 이동하고 1 점을 추가하는 듯

42
00:02:04,010 --> 00:02:05,570
그것은 어디 가야한다.

43
00:02:05,570 --> 00:02:08,110
>> 다시 말하지만, 여전히, 우리는 오직했습니다
하나, 둘, 5 보았다.

44
00:02:08,110 --> 00:02:12,480
우리는오고 다른 모르겠어요,
그러나 우리는이 세 가지 요소를 분류했습니다.

45
00:02:12,480 --> 00:02:16,030
>> 다음으로 정렬되지 않은 요소는
세, 그래서 우리는 옆에 설정합니다.

46
00:02:16,030 --> 00:02:18,200
우리는을 통해 이동합니다 우리
이는이 시간에 필요

47
00:02:18,200 --> 00:02:21,820
이전과 같이 모든 것을 아니다
두 가지 경우, 그냥 다섯입니다.

48
00:02:21,820 --> 00:02:25,440
그리고 우리는 세 가지 스틱 것이다,
둘 사이의 다섯.

49
00:02:25,440 --> 00:02:27,849
>> 여섯 분류되지 않은 옆에
배열에 요소입니다.

50
00:02:27,849 --> 00:02:31,140
그리고 사실 여섯 그래서, 다섯보다 큰
우리는 심지어 어떤 스와핑을 수행 할 필요가 없습니다.

51
00:02:31,140 --> 00:02:35,710
우리는 오른쪽에 여섯 압정 수 있습니다
정렬 된 부분의 끝.

52
00:02:35,710 --> 00:02:38,270
>> 마지막으로, 네 인
마지막으로 정렬되지 않은 요소입니다.

53
00:02:38,270 --> 00:02:42,060
그래서 우리는 따로 설정할 것, 이상 이동
요소는 우리가 이상 이동해야

54
00:02:42,060 --> 00:02:43,780
자신이 속한 위치를 다음 네 가지를 넣어.

55
00:02:43,780 --> 00:02:46,400
그리고 지금, 보면 우리는 일종의했습니다
모든 요소.

56
00:02:46,400 --> 00:02:48,150
삽입에 주목
종류, 우리는하지 않았다

57
00:02:48,150 --> 00:02:50,240
앞뒤로 배열에서 이동합니다.

58
00:02:50,240 --> 00:02:54,720
우리는 배열을 가로 질러 갔다
한 시간, 우리는 물건을 이동

59
00:02:54,720 --> 00:02:59,870
우리가 이미 위해가 발생 거라고
새로운 요소를위한 공간을 확인합니다.

60
00:02:59,870 --> 00:03:02,820
>> 그래서 최악의 경우입니다
삽입 정렬과 시나리오?

61
00:03:02,820 --> 00:03:05,090
최악의 경우,
배열을 역순으로한다.

62
00:03:05,090 --> 00:03:11,180
사용자는 n 개의 원소를 각각 이동해야
N 위치까지, 매 시간 우리

63
00:03:11,180 --> 00:03:12,880
삽입을합니다.

64
00:03:12,880 --> 00:03:15,720
즉 이동을 많이합니다.

65
00:03:15,720 --> 00:03:18,014
>> 최상의 경우에서,
배열이 완벽하게 정렬됩니다.

66
00:03:18,014 --> 00:03:20,680
그리고 일종의 무슨 일이 있었는지 등
예를 들어 다섯 여섯와,

67
00:03:20,680 --> 00:03:23,779
우리는 단지 그것을 압정 수있는 곳
임의의 이동을하지 않고도,

68
00:03:23,779 --> 00:03:24,820
우리는 본질적으로 그렇게 할 것입니다.

69
00:03:24,820 --> 00:03:27,560
>> 당신이 상상하는 경우 우리의
어레이는 6을 통해 하나

70
00:03:27,560 --> 00:03:29,900
우리는에 의해 시작 것
하나를 선언하는 정렬됩니다.

71
00:03:29,900 --> 00:03:33,300
두 그래서 우리가 할 수있는 한 후 제공
하나, 둘,이 분류되어 잘 확인을 말한다.

72
00:03:33,300 --> 00:03:36,190
세 가지 확인, 그래서 후 2 온다,
하나, 둘, 셋이 분류되어 있습니다.

73
00:03:36,190 --> 00:03:39,590
>> 우리는 우리가있어, 어떤 스왑을하지 않을
그냥 임의의 라인을 이동

74
00:03:39,590 --> 00:03:42,460
우리가 가서 사이의 분류 및 정렬되지 않은.

75
00:03:42,460 --> 00:03:46,646
효과적으로 우리가 예에서와 마찬가지로,
우리가 진행하는, 파란색 요소를 선회.

76
00:03:46,646 --> 00:03:48,270
따라서 최악의 경우 런타임은, 무슨 일이야?

77
00:03:48,270 --> 00:03:51,854
우리가 각을 이동해야하는 경우, 기억
N 소자 아마도 N 위치,

78
00:03:51,854 --> 00:03:54,020
희망이 당신을 제공합니다
최악의 경우는 그 아이디어

79
00:03:54,020 --> 00:03:57,770
런타임은 N의 큰 O 제곱입니다.

80
00:03:57,770 --> 00:04:00,220
>> 배열이 완벽하게되어있는 경우
분류, 우리 모두가해야 할

81
00:04:00,220 --> 00:04:04,480
모든 단일 요소를 보면됩니다
한 번, 그리고, 우리는 완료.

82
00:04:04,480 --> 00:04:08,440
따라서 최상의 경우에는, N의 오메가이다.

83
00:04:08,440 --> 00:04:09,490
>> 나는 더그 로이드입니다.

84
00:04:09,490 --> 00:04:11,760
이 CS50입니다.

85
00:04:11,760 --> 00:04:13,119