1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [삽입 정렬]

2
00:00:02,290 --> 00:00:04,240
[토미 MacWilliam] [하버드 대학]

3
00:00:04,240 --> 00:00:07,290
[이 CS50.TV입니다]

4
00:00:07,290 --> 00:00:13,060
가 삽입 정렬을 살펴, 숫자의 목록을 복용하고를 분류하는 알고리즘을 보자.

5
00:00:13,060 --> 00:00:18,300
알고리즘, 기억은 단순히 작업을 달성하기위한 단계별 절차입니다.

6
00:00:18,300 --> 00:00:23,640
삽입 정렬 뒤에 기본적인 아이디어는, 두 부분으로 목록을 분할하는 것입니다

7
00:00:23,640 --> 00:00:26,580
정렬 부분과 정렬되지 않은 부분입니다.

8
00:00:26,580 --> 00:00:29,290
>> 알고리즘의 각 단계에서 번호 이동

9
00:00:29,290 --> 00:00:32,439
정렬되지 않은 부분에서 정렬 부분에

10
00:00:32,439 --> 00:00:35,680
결국 때까지 전체 목록이 정렬됩니다.

11
00:00:35,680 --> 00:00:43,340
23, 42, 4, 16, 8, 15 - 여기에 여섯 정렬되지 않은 숫자의 목록입니다.

12
00:00:43,340 --> 00:00:47,680
이 숫자가 오름차순으로 모든 수 없습니다 때문에, 그것들은 정렬되지 않은하고 있습니다.

13
00:00:47,680 --> 00:00:53,890
아직 정렬 시작되지 않았으므로, 우리는 6 요소를 우리의 정렬되지 않은 부분을 고려합니다.

14
00:00:53,890 --> 00:00:59,270
>> 일단 정렬을 시작, 우리는 이들의 왼쪽에 이러한 분류 번호를 넣어드립니다.

15
00:00:59,270 --> 00:01:03,600
자, 23, 목록의 첫 번째 요소로 시작해보세요.

16
00:01:03,600 --> 00:01:06,930
우리는 아직 우리의 정렬 부분에 요소가 없습니다

17
00:01:06,930 --> 00:01:12,460
그러니 단순히 우리의 정렬 부분의 시작과 끝으로 23 생각해 보자.

18
00:01:12,460 --> 00:01:16,510
이제 우리의 정렬 부분은 한 번호 23을 가지고

19
00:01:16,510 --> 00:01:20,260
우리의 정렬되지 않은 부분은이 다섯 가지 숫자가 있습니다.

20
00:01:20,260 --> 00:01:27,320
의 지금 정렬 부분에 우리의 정렬되지 않은 부분을, 42에 다음 번호를 삽입 보자.

21
00:01:27,320 --> 00:01:35,930
>> 이렇게하려면 우리는 23 42를 비교해야합니다 - 우리의 정렬 부분에서 유일한 요소를 지금까지.

22
00:01:35,930 --> 00:01:41,980
42 23보다 큰, 그래서 우리는 간단하게 끝 42 추가 할 수 있습니다

23
00:01:41,980 --> 00:01:45,420
목록의 정렬 부분의. 좋아요!

24
00:01:45,420 --> 00:01:51,850
우리의 정렬 부분은 두 가지 요소가 있으며, 우리의 정렬되지 않은 부분은 4 원소 있습니다.

25
00:01:51,850 --> 00:01:57,200
그래서, 정렬되지 않은 부분에 다음 요소, 이제 4로 이동 보자.

26
00:01:57,200 --> 00:02:00,230
그래서,이는 정렬 부분에있는 배치해야 하는가?

27
00:02:00,230 --> 00:02:04,220
>> 명심 해, 우리가 정렬 순서로이 번호를 게재 할

28
00:02:04,220 --> 00:02:08,680
그래서 우리의 정렬 부분이 올바르게 항상 정렬 남아 있습니다.

29
00:02:08,680 --> 00:02:14,380
우리는 42의 오른쪽에있는 4 배치한다면, 목록이 순서대로 될 것입니다.

30
00:02:14,380 --> 00:02:18,380
자, 우리의 정렬 부분에 오른쪽에서 왼쪽으로 이동을 계속 하죠.

31
00:02:18,380 --> 00:02:23,260
우리가 이동,의는 새로운 번호 공간을 확보 할 수있는 장소 다운 각 번호를 이동 보자.

32
00:02:25,440 --> 00:02:31,740
좋아요, 4도 이하로 23, 우리는 하나 여기에 배치 할 수 없습니다.

33
00:02:31,740 --> 00:02:34,480
가 23 오른쪽 한 곳으로 이동하자.

34
00:02:36,500 --> 00:02:43,120
>> 우리가 정렬 부분의 첫 번째 슬롯에 4를 배치하고 싶은 의미한다.

35
00:02:43,120 --> 00:02:46,300
목록에이 공간이 이미 비어에주의하십시오,

36
00:02:46,300 --> 00:02:51,120
우리가 그들을 발생한 것처럼 우리는 정렬 요소를 아래로 이동되어서.

37
00:02:51,120 --> 00:02:52,740
괜찮아요. 그래서, 우리는 우리가 반이야.

38
00:02:52,740 --> 00:02:57,990
가 정렬 부분에 16을 삽입하여 알고리즘을 계속 보자.

39
00:02:59,260 --> 00:03:03,820
16 이하 42 이상 그러니, 오른쪽에있는 42 이동하게됩니다.

40
00:03:05,700 --> 00:03:10,190
16 이하 23 이상 그러니, 또한 요소를 이동하게 있습니다.

41
00:03:11,790 --> 00:03:20,820
>> 지금, 16는 4보다 큽니다. 우리는 4 23 사이에 16를 삽입하려면 같은 그래서 같습니다.

42
00:03:20,820 --> 00:03:24,620
오른쪽에서 왼쪽으로 목록의 정렬 부분을 통해 이동하지만,

43
00:03:24,620 --> 00:03:29,160
4 수보다 작습니다 우리가 본 최초의 번호입니다

44
00:03:29,160 --> 00:03:31,540
우리는 삽입 할 노력하고 있습니다.

45
00:03:31,540 --> 00:03:35,820
자, 이제 우리는이 빈 슬롯에 16을 삽입 할 수 있습니다

46
00:03:35,820 --> 00:03:40,520
하는 기억, 우리는 위에 정렬 부분에 움직이는 요소에 의해 생성 한

47
00:03:40,520 --> 00:03:43,340
우리는 그들을 발생했습니다 있습니다.

48
00:03:43,340 --> 00:03:47,900
>> 괜찮아요. 이제, 우리는 네 정렬 요소와 두 개의 정렬되지 않은 요소가 있습니다.

49
00:03:47,900 --> 00:03:51,600
자,이 정렬 부분에 8 이동하세요.

50
00:03:51,600 --> 00:03:55,010
여덟 미만 42.

51
00:03:55,010 --> 00:03:56,940
여덟 미만 23.

52
00:03:56,940 --> 00:04:00,230
그리고 8 이하 16 세입니다.

53
00:04:00,230 --> 00:04:03,110
그러나 8 4보다 더 크다.

54
00:04:03,110 --> 00:04:07,280
그래서, 우리는 우리가 4 16 사이에 8을 삽입하고 싶습니다.

55
00:04:09,070 --> 00:04:13,650
15 - 그리고 지금 우리가 정렬하려면 왼쪽 하나 더 요소가 있습니다.

56
00:04:13,950 --> 00:04:16,589
열 다섯 미만 42

57
00:04:16,589 --> 00:04:19,130
열 다섯 미만이 23.

58
00:04:19,130 --> 00:04:21,750
그리고 15 이하 16입니다.

59
00:04:21,750 --> 00:04:24,810
하지만 15은 8보다 큽니다.

60
00:04:24,810 --> 00:04:27,440
>> 우리가 우리의 마지막 삽입을하려는 자, 여기 있습니다.

61
00:04:28,770 --> 00:04:30,330
그리고 우리는 끝났어.

62
00:04:30,330 --> 00:04:33,540
우리는 정렬되지 않은 부분에 더 많은 요소가 없습니다

63
00:04:33,540 --> 00:04:36,670
우리의 정렬 부분은 올바른 순서입니다.

64
00:04:36,670 --> 00:04:40,270
번호는 최소에서 최대로 정렬됩니다.

65
00:04:40,270 --> 00:04:44,330
자, 우리가 방금 수행 한 단계를 설명합니다 어떤 의사를 살펴 보자.

66
00:04:46,760 --> 00:04:51,740
>> 1 번 라인에, 우리는 목록의 각 요소를 통해 반복해야합니다 것을 알 수 있습니다

67
00:04:51,740 --> 00:04:57,060
첫 번째 경우를 제외하고 정렬되지 않은 부분의 첫 번째 요소부터 간단하게 될 것입니다

68
00:04:57,060 --> 00:05:00,220
정렬 부분의 첫 번째 요소입니다.

69
00:05:00,220 --> 00:05:06,320
라인 2와 3에서 우리는 정렬되지 않은 부분에 현재 장소 추적을 유지하고 있습니다.

70
00:05:06,320 --> 00:05:10,450
요소는 우리가 현재 정렬 부분으로 이동하는 수를 나타냅니다

71
00:05:10,450 --> 00:05:15,600
와 j는 정렬되지 않은 부분에 색인을 나타냅니다.

72
00:05:15,600 --> 00:05:20,980
>> 4 호선에, 우리는 오른쪽에서 왼쪽으로 정렬 부분을 반복하고 있습니다.

73
00:05:20,980 --> 00:05:26,010
우리는 우리의 현재 위치의 왼쪽에있는 요소를 한 번 반복 중지하려면

74
00:05:26,010 --> 00:05:30,050
우리가 삽입하려는 요소보다 작습니다.

75
00:05:30,050 --> 00:05:35,600
5 호선에서 우리는 오른쪽으로 한 공간을 발생 각 요소를 이동하고있다.

76
00:05:35,600 --> 00:05:40,950
우리가 첫 번째 요소를 찾을 때 방법은, 우리는에 삽입 할 수있는 명확한 공간이됩니다

77
00:05:40,950 --> 00:05:44,080
우리가 움직이기 요소보다.

78
00:05:44,080 --> 00:05:50,800
6 호선에서, 우리는 정렬 부분을 왼쪽으로 이동을 계속하기 위해 카운터를 업데이트하고 있습니다.

79
00:05:50,800 --> 00:05:56,860
마지막으로, 7 호선에, 우리는 목록의 정렬 부분에 요소를 삽입하고 있습니다.

80
00:05:56,860 --> 00:06:00,020
>> 우리는이 위치 제이에 삽입 할 수 괜찮 알고

81
00:06:00,020 --> 00:06:05,360
우리는 이미 오른쪽으로가 한 공간이 될하는 데 사용되는 요소를 이동 한 때문입니다.

82
00:06:05,360 --> 00:06:09,460
명심 해, 우리가, 오른쪽에서 왼쪽으로 정렬 부분을 통해 이동

83
00:06:09,460 --> 00:06:13,960
그러나 우리는 왼쪽에서 오른쪽으로 정렬되지 않은 부분을 통해 이동하고 있습니다.

84
00:06:13,960 --> 00:06:19,090
괜찮아요. 의 지금 알고리즘했다는 실행 시간을 살펴 보자.

85
00:06:19,090 --> 00:06:25,300
우리는 먼저이 알고리즘은 최악의 경우에 실행이 얼마나가 걸리나요 질문을 요청할 것입니다.

86
00:06:25,300 --> 00:06:29,040
우리가 큰 O 표기법으로이 실행 시간을 나타냅니다 것을 기억합니다.

87
00:06:32,530 --> 00:06:38,500
목록을 정렬하기 위해, 우리는 정렬되지 않은 부분의 요소를 통해 반복했다

88
00:06:38,500 --> 00:06:43,430
잠재적으로 정렬 부분의 모든 요소를​​ 통해 이러한 요소 각각에 대해.

89
00:06:43,430 --> 00:06:47,950
직관적으로, O (N ^ 2) 작업처럼 소리.

90
00:06:47,950 --> 00:06:51,840
>> 우리의 의사를 살펴보면, 우리는 다른 루프 안에 중첩 루프를 가지고

91
00:06:51,840 --> 00:06:55,290
있는 사실은, O (N ^ 2) 작업처럼 들린다.

92
00:06:55,290 --> 00:07:01,590
그러나, 목록의 정렬 부분은 매우 말까지 전체 목록을 포함하지 않았다.

93
00:07:01,590 --> 00:07:06,920
그러나, 우리는 잠재적으로 정렬 부분의 처음에 새로운 요소를 삽입 할 수

94
00:07:06,920 --> 00:07:09,320
알고리즘의 모든 반복에,

95
00:07:09,320 --> 00:07:14,500
이는 우리가 정렬 부분에 현재 각 요소를보고해야 할 것을 의미합니다.

96
00:07:14,500 --> 00:07:20,090
그래서 우리가 잠재적으로 두 번째 요소에 대해 하나의 비교를 만들 수 의미

97
00:07:20,090 --> 00:07:24,660
세 번째 요소 두 비교 등.

98
00:07:24,660 --> 00:07:32,480
따라서 단계의 총 수는 1에서 목록 마이너스 1의 길이에 정수의 합계입니다.

99
00:07:32,480 --> 00:07:35,240
우리는 합류로이를 대표 할 수 있습니다.

100
00:07:41,170 --> 00:07:47,270
>> 우리는 여기 summations로 이동되지 않습니다,하지만이 합류과 동일하다고 판명

101
00:07:47,270 --> 00:07:57,900
N / 2 - 동등한 N ^ 이분의이 있습니다 2 이상 - N (1 N).

102
00:07:57,900 --> 00:08:00,800
점근 런타임에 대해 얘기하면,

103
00:08:00,800 --> 00:08:05,170
이 N ^ 2 학기는 N 용어를 지배 할 것이다.

104
00:08:05,170 --> 00:08:11,430
따라서, 삽입 정렬은 빅 O (N ^ 2)입니다.

105
00:08:11,430 --> 00:08:16,150
우리가 이미 정렬 된 목록에 삽입 정렬을 실행합니다.

106
00:08:16,150 --> 00:08:20,960
이 경우, 우리는 단순히 왼쪽에서 오른쪽으로 정렬 된 부분을 구축 할.

107
00:08:20,960 --> 00:08:25,050
그럼, 우리는 N 단계의 순서를해야합니다.

108
00:08:25,050 --> 00:08:29,740
>> 즉, 삽입 정렬 n의 최선의 성능을 의미합니다

109
00:08:29,740 --> 00:08:34,130
있는 우리는 Ω (n)이 함께 나타냅니다.

110
00:08:34,130 --> 00:08:36,190
그래서, 삽입 정렬을 위해 야

111
00:08:36,190 --> 00:08:40,429
단지 여러 알고리즘 중 하나는 우리는 목록을 정렬하는 데 사용할 수 있습니다.

112
00:08:40,429 --> 00:08:43,210
내 이름은 토미이고,이 CS50입니다.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
아, 당신은 한 번가 시작되는 중지 할 수 없습니다.

115
00:09:01,620 --> 00:09:04,760
아, 우리는 그렇게 했어요 - >> 붐!