1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] 토미 :가 선택 정렬 살펴, 알고리즘을하게하라

2
00:00:09,980 --> 00:00:12,800
번호 목록을 복용하고 정렬하십시오.

3
00:00:12,800 --> 00:00:15,750
알고리즘, 기억은 단순히 단계별로입니다

4
00:00:15,750 --> 00:00:18,370
작업을 달성하기위한 절차.

5
00:00:18,370 --> 00:00:21,470
선택 정렬 뒤에 기본적인 아이디어는 나눌 것입니다

6
00:00:21,470 --> 00:00:23,390
이 부분에 목록 -

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

8
00:00:26,810 --> 00:00:30,200
알고리즘의 각 단계에서 번호가에서 이동

9
00:00:30,200 --> 00:00:33,800
결국 때까지 정렬 부분에 정렬되지 않은 부분

10
00:00:33,800 --> 00:00:35,880
전체 목록이 정렬됩니다.

11
00:00:35,880 --> 00:00:38,510
그럼 여기에 여섯 전화 번호가 있어요 -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, 15.

13
00:00:44,010 --> 00:00:47,680
지금 전체 목록이 정렬되지 않은 것으로 간주됩니다.

14
00:00:47,680 --> 00:00:51,770
16 같은 숫자는 이미 올바른에있을 수 있습니다하더라도

15
00:00:51,770 --> 00:00:56,040
위치, 우리의 알고리즘은 때까지를 알 수있는 방법이 없습니다

16
00:00:56,040 --> 00:00:57,980
전체 목록이 정렬됩니다.

17
00:00:57,980 --> 00:01:01,355
우리가 정렬 될 때까지 그래서 우리는 정렬되지 않은 것으로 모든 숫자를 고려됩니다

18
00:01:01,355 --> 00:01:03,800
그 자신.

19
00:01:03,800 --> 00:01:06,890
우리는 목록 오름차순으로 할 원하는 알아요.

20
00:01:06,890 --> 00:01:10,200
그래서 우리는 우리의 목록의 정렬 부분을 구성 할 것

21
00:01:10,200 --> 00:01:13,280
왼쪽에서 오른쪽으로, 가장 큰 to 작은.

22
00:01:13,280 --> 00:01:17,970
이를 위해 우리는 최소한의 정렬되지 않은 요소를 찾아야합니다

23
00:01:17,970 --> 00:01:21,350
과 정렬 부분의 끝 부분에 넣어.

24
00:01:21,350 --> 00:01:25,370
이 목록은 정렬되지 않기 때문에, 할 수있는 유일한 방법은 다음과 같습니다

25
00:01:25,370 --> 00:01:29,330
기억, 정렬되지 않은 부분에 각 요소 살펴

26
00:01:29,330 --> 00:01:32,010
요소는 최저과 비교입니다

27
00:01:32,010 --> 00:01:33,770
거기에 각 요소.

28
00:01:33,770 --> 00:01:36,150
그럼 우리가 23 보겠습니다.

29
00:01:36,150 --> 00:01:38,650
이것은 우리가 본 첫 번째 요소입니다, 그래서 우리는 기억합니다

30
00:01:38,650 --> 00:01:40,050
최소로 그.

31
00:01:40,050 --> 00:01:42,320
다음 우리는 42 보겠습니다.

32
00:01:42,320 --> 00:01:46,720
42 23보다 큰, 그래서 23 여전히 최소입니다.

33
00:01:46,720 --> 00:01:51,210
다음은 23보다 작음 4, 그래서 우리는 4 기억합니다

34
00:01:51,210 --> 00:01:52,880
새로운 최소 있습니다.

35
00:01:52,880 --> 00:01:56,380
다음 그래서 4, 4보다 큰 16

36
00:01:56,380 --> 00:01:57,980
아직 최소입니다.

37
00:01:57,980 --> 00:02:03,670
8 4보다 큰이며, 15 4보다 큰, 4해야만

38
00:02:03,670 --> 00:02:05,980
작은 정렬되지 않은 요소입니다.

39
00:02:05,980 --> 00:02:09,350
그래서, 비록 인간으로 우리는 즉시 4임을 알 수 있습니다

40
00:02:09,350 --> 00:02:12,300
최소 요소는 우리의 알고리즘은보고 할 필요가

41
00:02:12,300 --> 00:02:15,710
우리는 4을 발견 한 후에도 모든 정렬되지 않은 요소 -

42
00:02:15,710 --> 00:02:16,860
최소 요소입니다.

43
00:02:16,860 --> 00:02:19,900
그래서 지금 우리가 최소한의 요소 4를 발견 한, 우리가 원하는 것

44
00:02:19,900 --> 00:02:23,410
목록의 정렬 부분에 이동합니다.

45
00:02:23,410 --> 00:02:27,320
이 첫 번째 단계이기 때문에, 우리가에 4 넣었 으면 좋겠어 의미

46
00:02:27,320 --> 00:02:29,680
목록의 시작.

47
00:02:29,680 --> 00:02:33,040
지금 23 때문에, 목록의 시작 부분에 있습니다

48
00:02:33,040 --> 00:02:36,080
의는 4 23 교환 보자.

49
00:02:36,080 --> 00:02:38,870
이제 목록은 다음과 같습니다.

50
00:02:38,870 --> 00:02:42,710
이 때문에 우리는 4 최종 위치에 있어야합니다 알고

51
00:02:42,710 --> 00:02:45,890
처음에 가장 작은 요소와 요소를 모두

52
00:02:45,890 --> 00:02:46,960
목록의.

53
00:02:46,960 --> 00:02:50,650
우리가 다시 이동 할 필요가 없다는 의미는 그럼.

54
00:02:50,650 --> 00:02:53,910
그러니에 다른 요소를 추가 할이 과정을 반복하게

55
00:02:53,910 --> 00:02:55,910
목록의 정렬 부분입니다.

56
00:02:55,910 --> 00:02:58,950
그 때문에 우리는 우리가 4 볼 필요가 전혀 없다는 것을 알고

57
00:02:58,950 --> 00:03:00,000
이미 정렬.

58
00:03:00,000 --> 00:03:03,540
그래서 우리는 우리가로 기억됩니다있는 42에서 시작할 수 있습니다

59
00:03:03,540 --> 00:03:05,290
최소 요소입니다.

60
00:03:05,290 --> 00:03:08,700
그래서 다음에 우리는 42보다 작음 23를보세요, 정말 드리겠습니다

61
00:03:08,700 --> 00:03:11,620
23 새 최소 기억 해요.

62
00:03:11,620 --> 00:03:14,870
다음 우리는 그렇게 미만 23 16를 참조

63
00:03:14,870 --> 00:03:16,800
16 새 최소입니다.

64
00:03:16,800 --> 00:03:19,720
이제 우리는, 그래서보다 16 8 볼

65
00:03:19,720 --> 00:03:21,130
8 새로운 최소입니다.

66
00:03:21,130 --> 00:03:25,900
그리고 마지막으로 8 미만 15, 그래서 우리는 8 최소 알고

67
00:03:25,900 --> 00:03:27,780
정렬되지 않은 요소입니다.

68
00:03:27,780 --> 00:03:30,660
그럼 우리가 정렬 8를 추가해야 함을 의미합니다

69
00:03:30,660 --> 00:03:32,450
목록의 부분입니다.

70
00:03:32,450 --> 00:03:35,990
지금 4 만 정렬 요소입니다, 그래서 우리는 배치하려는

71
00:03:35,990 --> 00:03:38,410
4 8 옆에 있습니다.

72
00:03:38,410 --> 00:03:41,920
42 이후의 정렬되지 않은 부분의 첫 번째 요소입니다

73
00:03:41,920 --> 00:03:47,260
목록, 우리는 42 8을 교환하는 것이 좋습니다.

74
00:03:47,260 --> 00:03:49,680
이제 목록은 다음과 같습니다.

75
00:03:49,680 --> 00:03:53,830
4 8 목록의 정렬 부분을 대표하고,

76
00:03:53,830 --> 00:03:56,440
나머지 숫자는 정렬되지 않은를 나타냅니다

77
00:03:56,440 --> 00:03:58,260
목록의 부분입니다.

78
00:03:58,260 --> 00:04:00,630
그럼 다른 반복을 계속 보자.

79
00:04:00,630 --> 00:04:03,850
우리가 볼 필요가 없기 때문에 우리는 23와 함께 시작 시간

80
00:04:03,850 --> 00:04:05,770
4 이상 8가 없기 때문에

81
00:04:05,770 --> 00:04:07,660
이미 정렬 된.

82
00:04:07,660 --> 00:04:10,270
16 미만 23, 그래서 우리는 기억합니다

83
00:04:10,270 --> 00:04:12,070
새로운 최소로 16.

84
00:04:12,070 --> 00:04:18,149
15해야하므로, 16 미만 42 만 15 미만 16입니다

85
00:04:18,149 --> 00:04:20,480
최소 정렬되지 않은 요소입니다.

86
00:04:20,480 --> 00:04:24,580
그래서 지금 우리는 15 23로 교환하려면

87
00:04:24,580 --> 00:04:26,310
우리에게이 목록을 제공합니다.

88
00:04:26,310 --> 00:04:30,500
목록의 정렬 부분은 4, 8, 15로 구성되어 있으며,

89
00:04:30,500 --> 00:04:33,210
이러한 요소는 여전히 정렬되지 않은 수 있습니다.

90
00:04:33,210 --> 00:04:36,900
그러나 우연히도 그 다음 정렬되지 않은 요소, 16,

91
00:04:36,900 --> 00:04:38,480
이미 정렬됩니다.

92
00:04:38,480 --> 00:04:42,060
그러나, 알고 우리의 알고리즘에 대한 방법이 없습니다 그 16

93
00:04:42,060 --> 00:04:45,230
이미 올바른 위치에, 우리는 여전히 필요

94
00:04:45,230 --> 00:04:47,870
정확히 같은 과정을 반복합니다.

95
00:04:47,870 --> 00:04:53,750
그래서 이렇게, 우리는 16 이하 42 알, 16 미만 23

96
00:04:53,750 --> 00:04:56,230
16의 최소 요소 여야합니다.

97
00:04:56,230 --> 00:04:59,010
그것은 그 자체로이 요소를 교환하는 것은 불가능이야, 우리가 할 수 있도록

98
00:04:59,010 --> 00:05:01,780
단순히이 위치에 두십시오.

99
00:05:01,780 --> 00:05:04,660
그래서 우리는 우리의 알고리즘 중 하나를 더 패스가 필요합니다.

100
00:05:04,660 --> 00:05:09,370
42 23보다 큰, 그래서 23이어야합니다

101
00:05:09,370 --> 00:05:10,970
최소 정렬되지 않은 요소입니다.

102
00:05:10,970 --> 00:05:17,410
일단 우리가 우리의 마지막이 생깁니다, 23 42 교환

103
00:05:17,410 --> 00:05:18,530
정렬 목록 -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
우리는 이니까 42 올바른 위치에 있어야합니다 알고

106
00:05:26,830 --> 00:05:30,210
단 요소는 왼쪽으로, 그리고 그 선택 정렬입니다.

107
00:05:30,210 --> 00:05:32,100
자, 이제 일부의 알고리즘을 공식화

108
00:05:32,100 --> 00:05:34,540
의사.

109
00:05:34,540 --> 00:05:37,760
라인에, 우리는 이상을 통합하는 데 필요한 것을 알 수 있습니다

110
00:05:37,760 --> 00:05:39,530
목록의 모든 요소입니다.

111
00:05:39,530 --> 00:05:42,150
마지막 요소를 제외하고, 이후 한 요소

112
00:05:42,150 --> 00:05:44,230
목록이 이미 정렬됩니다.

113
00:05:44,230 --> 00:05:48,100
2 번 라인에서, 우리는 정렬되지 않은 첫 번째 요소를 고려

114
00:05:48,100 --> 00:05:51,080
우리는 우리와 함께했던 목록의 부분은 최소 할 수

115
00:05:51,080 --> 00:05:53,750
예, 우리는 비교 할 일이 있습니다.

116
00:05:53,750 --> 00:05:57,260
선 셋은 우리가 이상 반복되는 두 번째 루프를 시작

117
00:05:57,260 --> 00:05:59,170
각 정렬되지 않은 요소입니다.

118
00:05:59,170 --> 00:06:02,150
우리가 알고 내가 반복 한 후, 정렬 부분

119
00:06:02,150 --> 00:06:05,330
목록의 각 단계부터 그 안에 내가 요소가 있어야합니다

120
00:06:05,330 --> 00:06:06,890
정렬 한 요소.

121
00:06:06,890 --> 00:06:11,770
따라서 첫 번째 정렬되지 않은 요소는 위치에 내가 플러스 1에 있어야합니다.

122
00:06:11,770 --> 00:06:15,440
4 번에, 우리는 최소한으로 현재 요소를 비교

123
00:06:15,440 --> 00:06:17,750
우리가 지금까지 본 적이 있다고 요소입니다.

124
00:06:17,750 --> 00:06:20,560
현재 요소는 최소보다 작 으면

125
00:06:20,560 --> 00:06:23,870
요소는, 우리는 새로운로 현재 요소를 기억

126
00:06:23,870 --> 00:06:26,250
5 번 라인에서 최소.

127
00:06:26,250 --> 00:06:29,900
마지막으로, 선 6-7에, 우리는 최소 교환

128
00:06:29,900 --> 00:06:33,080
따라서 첫 번째 정렬되지 않은 요소와 요소,

129
00:06:33,080 --> 00:06:36,990
목록의 정렬 부분에 추가.

130
00:06:36,990 --> 00:06:40,030
우리가 알고리즘을 가지고되면, 중요한 질문은 물어

131
00:06:40,030 --> 00:06:43,370
우리는 프로그래머로서 그 얼마나 걸릴 아세요?

132
00:06:43,370 --> 00:06:46,970
우리는 먼저 질문을 드리겠습니다 얼마나이 순간을 위해 걸리나요

133
00:06:46,970 --> 00:06:50,070
알고리즘은 최악의 경우에 실행?

134
00:06:50,070 --> 00:06:51,640
우리는이 실행을 나타냅니다 기억

135
00:06:51,640 --> 00:06:55,060
큰 O 표기법으로 시간을.

136
00:06:55,060 --> 00:06:58,650
최소 정렬되지 않은 요소를 결정하기 위해, 우리는

137
00:06:58,650 --> 00:07:01,880
기본적으로 목록의 각 요소를 비교했다

138
00:07:01,880 --> 00:07:04,040
목록에있는 다른 모든 요소입니다.

139
00:07:04,040 --> 00:07:08,430
직관적으로, 만약에 n 제곱 연산의 O처럼 소리.

140
00:07:08,430 --> 00:07:12,050
우리의 의사를 살펴보면, 우리는 또한 내부에 중첩 루프를 가지고

141
00:07:12,050 --> 00:07:14,420
O와 같은 실제로 소리가 다른 루프,

142
00:07:14,420 --> 00:07:16,480
N 제곱 운영.

143
00:07:16,480 --> 00:07:19,250
그러나, 우리가 살펴보고 필요하지 않은 기억

144
00:07:19,250 --> 00:07:23,460
최소 정렬되지 않은 요소를 결정하는 전체 목록?

145
00:07:23,460 --> 00:07:26,600
우리가 4 정렬 된 것을 알고되면, 예를 들어, 우리가 아니라,

146
00:07:26,600 --> 00:07:28,170
다시 한번해야합니다.

147
00:07:28,170 --> 00:07:31,020
이 실행 시간도 마찬가지 낮은합니까?

148
00:07:31,020 --> 00:07:34,510
길이 6의 목록을 보려면, 우리는 다섯을 만드는 데 필요한

149
00:07:34,510 --> 00:07:37,990
첫 번째 요소에 대한 비교, 네 번 비교

150
00:07:37,990 --> 00:07:40,750
두 번째 요소 등.

151
00:07:40,750 --> 00:07:44,690
그 단계의 총 수가의 합을 의미합니다

152
00:07:44,690 --> 00:07:49,160
1 목록 마이너스 1의 길이 정수.

153
00:07:49,160 --> 00:07:51,005
우리는 합류로이를 대표 할 수 있습니다.

154
00:07:57,980 --> 00:07:59,910
우리는 여기 summations로 이동하지 않습니다.

155
00:07:59,910 --> 00:08:04,900
그러나이 합류가 n 번과 동일하다고 판명

156
00:08:04,900 --> 00:08:07,540
N 마이너스 2 이상 1.

157
00:08:07,540 --> 00:08:14,220
또는 equivalently, 만약에 n이 넘는 마이너스 N 2를 통해 제곱.

158
00:08:14,220 --> 00:08:18,860
점근 런타임에 대해 얘기,이 N 제곱 용어

159
00:08:18,860 --> 00:08:22,070
이 N 용어를 지배 할 것이다.

160
00:08:22,070 --> 00:08:27,850
그래서 선택 정렬은 N 제곱의 O입니다.

161
00:08:27,850 --> 00:08:31,460
우리 예제에서, 선택 정렬 여전히 필요하다고 기억

162
00:08:31,460 --> 00:08:33,850
선택하면 이미 정렬 된 번호

163
00:08:33,850 --> 00:08:35,450
이동이 필요합니다.

164
00:08:35,450 --> 00:08:38,929
말하자면 우리가 이미를 통해 선택 정렬을 실행하는 경우

165
00:08:38,929 --> 00:08:43,070
목록 정렬, 그것은과 같은 단계의 동일한 번호를 요구

166
00:08:43,070 --> 00:08:46,340
완전히 정렬되지 않은 목록을 통해 실행시 겠지.

167
00:08:46,340 --> 00:08:51,470
그래서 선택 정렬은 제곱 n의 최고의 사례 성능을

168
00:08:51,470 --> 00:08:56,820
있는 우리는 오메가 N 제곱을 나타냅니다.

169
00:08:56,820 --> 00:08:58,600
그리고 그 선택 정렬을 위해 있습니다.

170
00:08:58,600 --> 00:09:00,630
우리가 할 수있는 많은 알고리즘 중 하나

171
00:09:00,630 --> 00:09:02,390
목록을 정렬하려면 사용합니다.

172
00:09:02,390 --> 00:09:05,910
내 이름은 토미이고,이 cs50입니다.