1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
1
00:00:00,000 --> 00:00:03,360
>> [음악 재생]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG 로이드 : 좋아, 그래서
버블 정렬은 알고리즘

4
00:00:06,730 --> 00:00:08,730
는 요소들의 세트를 정렬하는 데 사용할 수있다.

5
00:00:08,730 --> 00:00:10,850
이제 어떻게 작동하는지 살펴 보자.

6
00:00:10,850 --> 00:00:13,240
>> 그래서 기본 아이디어 뒤에
버블 정렬이입니다.

7
00:00:13,240 --> 00:00:17,340
우리는 일반적으로 더 높은 이동할
일반적으로 오른쪽에 상당 소자

8
00:00:17,340 --> 00:00:20,340
일반적으로 평가 요소를 낮출
왼쪽에, 우리가 기대하는 것처럼.

9
00:00:20,340 --> 00:00:23,256
우리는 낮은 가지에가되고 싶어요
시작 및 높은 것들

10
00:00:23,256 --> 00:00:24,970
마지막에한다.

11
00:00:24,970 --> 00:00:26,130
>> 우리는 어떻게해야합니까?

12
00:00:26,130 --> 00:00:28,040
그럼 의사 코드,
우리는의를하자, 말할 수

13
00:00:28,040 --> 00:00:30,320
0이 아닌 값으로 스왑 카운터를 설정한다.

14
00:00:30,320 --> 00:00:32,570
우리는 두 번째에 그렇게 할 이유를 우리는 볼 수 있습니다.

15
00:00:32,570 --> 00:00:36,090
그리고 우리는 다음을 반복
스왑 카운터가 0이 될 때까지 공정

16
00:00:36,090 --> 00:00:39,910
또는 우리는 전혀 스왑을하지 않을 때까지.

17
00:00:39,910 --> 00:00:43,170
>> 에 스왑 카운터를 재설정
0 이미 0이 아니라면.

18
00:00:43,170 --> 00:00:46,420
그런 다음에 모든보고
요소의 인접 쌍.

19
00:00:46,420 --> 00:00:49,550
이 두 요소가있는 경우
하지 않게하기 위해, 그들을 스왑

20
00:00:49,550 --> 00:00:51,620
및 스왑 카운터에 1을 추가합니다.

21
00:00:51,620 --> 00:00:53,870
당신에 대해 생각하는 경우
이 당신이 그것을 시각화하기 전에,

22
00:00:53,870 --> 00:00:57,471
이 낮은 이동합니다 통지
왼쪽으로 평가 요소

23
00:00:57,471 --> 00:01:00,720
이상, 우측 요소를 반환
효과적으로 우리가하고 싶은 일을,

24
00:01:00,720 --> 00:01:03,940
이는 해당 그룹을 이동입니다
그런 식의 요소.

25
00:01:03,940 --> 00:01:07,035
의 방법이 시각화하자
우리의 배열을 사용하여 볼 수 있습니다

26
00:01:07,035 --> 00:01:10,504
우리가 테스트하는 데 사용
이러한 알고리즘 아웃.

27
00:01:10,504 --> 00:01:13,420
우리는 여기에 다시 정렬되지 않은 배열을 가지고
모든 요소에 의해 지시

28
00:01:13,420 --> 00:01:14,840
빨간색에있는.

29
00:01:14,840 --> 00:01:17,970
그리고 나는 나의 스왑 카운터를 설정
0이 아닌 값으로.

30
00:01:17,970 --> 00:01:20,610
내가 임의로 선택
부정적인 1--은 0이 아니다.

31
00:01:20,610 --> 00:01:23,840
우리는이 프로세스를 반복 할
스왑 카운터까지 0입니다.

32
00:01:23,840 --> 00:01:26,540
내 스왑을 설정하는 이유입니다
0이 아닌 값으로 카운터

33
00:01:26,540 --> 00:01:29,400
그렇지 않으면 때문에
스왑 카운터는 0이 될 것이다.

34
00:01:29,400 --> 00:01:31,610
우리는 심지어을 시작하지 않을
알고리즘의 방법.

35
00:01:31,610 --> 00:01:33,610
그래서 다시, 단계으로 죠
스왑 카운터를 재설정

36
00:01:33,610 --> 00:01:37,900
0, 다음, 모든 인접보고
쌍, 그들은 순서가 있다면,

37
00:01:37,900 --> 00:01:40,514
를 교환하고, 1을 추가
스왑 카운터.

38
00:01:40,514 --> 00:01:41,680
그래서이 과정을 시작합시다.

39
00:01:41,680 --> 00:01:44,430
그래서 우리가 먼저입니다
우리가 0으로 스왑 카운터 설정

40
00:01:44,430 --> 00:01:46,660
그리고, 우리는보고 시작
인접한 각에서.

41
00:01:46,660 --> 00:01:49,140
>> 그래서 우리는 처음 5와 2를보고 시작합니다.

42
00:01:49,140 --> 00:01:52,410
우리는 그들이 벗어난 것을 확인할
주문하고 그래서 우리는 그들을 교환합니다.

43
00:01:52,410 --> 00:01:53,830
그리고 우리는 스왑 카운터에 1을 추가합니다.

44
00:01:53,830 --> 00:01:57,860
그래서 지금 우리의 스왑 카운터가 1이고,
및 (2)와 (5)는 전환되었다.

45
00:01:57,860 --> 00:01:59,370
이제 우리는 다시 프로세스를 반복합니다.

46
00:01:59,370 --> 00:02:03,540
>> 우리는 다음 인접한 한 쌍을보고,
5 그들은 또한 순서가있어 1--,

47
00:02:03,540 --> 00:02:06,960
그래서 우리는 그들을 교체 및 추가
스왑 카운터 1.

48
00:02:06,960 --> 00:02:08,900
그 다음 우리는 5와 3 봐.

49
00:02:08,900 --> 00:02:13,830
그들은 순서가, 그래서 우리는 스왑
그들과 우리는 스왑 카운터에 1을 추가합니다.

50
00:02:13,830 --> 00:02:15,550
그럼 우리가 5와 6을 봐주세요.

51
00:02:15,550 --> 00:02:18,630
그들은 순서에있어, 그래서 우리는 실제로하지 않습니다
아무것도이 시간을 교체해야합니다.

52
00:02:18,630 --> 00:02:20,250
그 다음 우리는 6과 4를 봐주세요.

53
00:02:20,250 --> 00:02:24,920
그들은 순서가도, 그래서 우리는 스왑
그들과 우리는 스왑 카운터에 1을 추가합니다.

54
00:02:24,920 --> 00:02:26,230
>> 지금 일어난 것을 알 수 있습니다.

55
00:02:26,230 --> 00:02:29,514
우리는 끝 6 줄곧 옮겼다.

56
00:02:29,514 --> 00:02:32,180
선택의 종류에 따라서, 당신이 한 경우
그 비디오를 본, 우리가 한 일은이었다

57
00:02:32,180 --> 00:02:35,290
우리는 이동 결국
건물의 작은 요소

58
00:02:35,290 --> 00:02:39,640
본질적으로 정렬 된 배열
최대 규모로, 작은 왼쪽에서 오른쪽으로.

59
00:02:39,640 --> 00:02:43,200
버블 정렬의 경우, 우리는이 있다면
이 특정 알고리즘 다음,

60
00:02:43,200 --> 00:02:46,720
우리는 실제로 구축 할거야
오른쪽 정렬 된 배열

61
00:02:46,720 --> 00:02:49,100
최소로, 가장 왼쪽에.

62
00:02:49,100 --> 00:02:53,840
우리는 효과적으로 6을 발포 한
최대 값, 일단 모든 방법.

63
00:02:53,840 --> 00:02:56,165
>> 그래서 우리는 지금 선언 할 수 있습니다
즉 분류된다,

64
00:02:56,165 --> 00:02:59,130
미래에 iterations--
배열을 통과 again--

65
00:02:59,130 --> 00:03:01,280
우리는 더 이상 (6)을 고려해야 할 필요가 없습니다.

66
00:03:01,280 --> 00:03:03,850
우리는 고려해야 할
정렬되지 않은 요소

67
00:03:03,850 --> 00:03:06,299
때 우리가 인접한 찾고 있습니다.

68
00:03:06,299 --> 00:03:08,340
그래서 우리는 하나를 완료
거품 정렬을 통해 전달합니다.

69
00:03:08,340 --> 00:03:11,941
그래서 지금 우리가 질문으로 돌아가,
스왑 카운터가 0이 될 때까지 반복합니다.

70
00:03:11,941 --> 00:03:13,690
그럼 스왑 카운터
4, 그래서 우리는거야

71
00:03:13,690 --> 00:03:15,410
다시이 과정을 계속 반복합니다.

72
00:03:15,410 --> 00:03:19,180
>> 우리는 스왑 카운터를 재설정거야
0으로, 각 인접한 쌍 봐.

73
00:03:19,180 --> 00:03:21,890
그래서 우리는 그들이있어 1-- 2로 시작
순서가, 그래서 우리는 그들을 교환

74
00:03:21,890 --> 00:03:23,620
우리는 스왑 카운터에 1을 추가합니다.

75
00:03:23,620 --> 00:03:25,490
2, 3, 그들은 순서에있어.

76
00:03:25,490 --> 00:03:27,060
우리는 아무것도 할 필요가 없습니다.

77
00:03:27,060 --> 00:03:28,420
3과 5는 순서에 있습니다.

78
00:03:28,420 --> 00:03:30,150
우리는이 작업을 수행 할 필요가 없습니다.

79
00:03:30,150 --> 00:03:32,515
>> 5, 4, 그들이 외출
주문, 그래서 우리를

80
00:03:32,515 --> 00:03:35,130
를 교환하고 추가 할 필요가
스왑 카운터 1.

81
00:03:35,130 --> 00:03:38,880
그리고 지금 우리는 5 이동 한
다음 가장 큰 요소,

82
00:03:38,880 --> 00:03:40,920
정렬되지 않은 부분의 끝까지.

83
00:03:40,920 --> 00:03:44,360
그래서 우리는 지금를 호출 할 수 있습니다
정렬 된 부분의 일부입니다.

84
00:03:44,360 --> 00:03:47,180
>> 지금 당신은보고있다
화면 아마도 말할 수,

85
00:03:47,180 --> 00:03:50,130
내가 할 수있는 배열과
지금 정렬됩니다.

86
00:03:50,130 --> 00:03:51,820
그러나 우리는 아직 증명할 수 없습니다.

87
00:03:51,820 --> 00:03:54,359
우리는 보장이 없습니다
그것이이 분류입니다.

88
00:03:54,359 --> 00:03:56,900
그러나 이것은 어디 스왑입니다
카운터 플레이로 올 것입니다.

89
00:03:56,900 --> 00:03:59,060
>> 그래서 우리는 패스를 완료 한.

90
00:03:59,060 --> 00:04:00,357
스왑 카운터는 2입니다.

91
00:04:00,357 --> 00:04:02,190
그래서 우리는 반복하는거야
다시 공정

92
00:04:02,190 --> 00:04:04,290
스왑 카운터가 0이 될 때까지 반복합니다.

93
00:04:04,290 --> 00:04:05,550
0 스왑 카운터를 재설정합니다.

94
00:04:05,550 --> 00:04:06,820
그래서 우리는 그것을 다시 설정합니다.

95
00:04:06,820 --> 00:04:09,810
>> 지금 인접한 각 봐.

96
00:04:09,810 --> 00:04:11,880
즉, 순서대로 1, 2입니다.

97
00:04:11,880 --> 00:04:13,590
도 2 및도 3은 순서이다.

98
00:04:13,590 --> 00:04:15,010
도 3 및도 4는 순서이다.

99
00:04:15,010 --> 00:04:19,250
따라서이 시점에서, 우리가 완료 한 알
모든 인접 쌍을보고,

100
00:04:19,250 --> 00:04:22,530
하지만 스왑 카운터는 여전히 0입니다.

101
00:04:22,530 --> 00:04:25,520
>> 우리는 전환 할 수없는 경우
모든 요소를​​, 다음

102
00:04:25,520 --> 00:04:28,340
에 의해, 순서에 있어야합니다
이 과정의 미덕.

103
00:04:28,340 --> 00:04:32,000
그리고 종류의 효율,
그 우리의 컴퓨터 과학자들은 사랑,

104
00:04:32,000 --> 00:04:35,560
우리는 지금 선언 할 수있다
전체 배열해야

105
00:04:35,560 --> 00:04:38,160
우리가하지 않았기 때문에, 정렬
모든 요소를​​ 교체해야합니다.

106
00:04:38,160 --> 00:04:40,380
그건 꽤 좋은 데요.

107
00:04:40,380 --> 00:04:43,260
>> 그래서 최악의 경우입니다
버블 정렬과 시나리오?

108
00:04:43,260 --> 00:04:46,240
최악의 경우는 어레이
완전히 역순으로,

109
00:04:46,240 --> 00:04:49,870
그래서 우리는 각 거품에있다
큰 모든 요소

110
00:04:49,870 --> 00:04:51,780
배열에 걸쳐 방법.

111
00:04:51,780 --> 00:04:55,350
그리고 우리는 효과적으로에도있다
거품 작은 모든 요소를​​ 다시

112
00:04:55,350 --> 00:04:57,050
너무 배열에서 모든 방법.

113
00:04:57,050 --> 00:05:01,950
따라서 N 개의 요소들 각각이 이동하는
다른 n 개의 모든 요소에 걸쳐.

114
00:05:01,950 --> 00:05:04,102
그래서 최악의 시나리오이다.

115
00:05:04,102 --> 00:05:05,810
최상의 경우
시나리오는하지만,이입니다

116
00:05:05,810 --> 00:05:07,880
선택 정렬과 약간 다릅니다.

117
00:05:07,880 --> 00:05:10,040
배열은 이미
우리가 갈 때 분류.

118
00:05:10,040 --> 00:05:12,550
우리는 어떤 필요가 없습니다
첫 번째 패스에 스왑.

119
00:05:12,550 --> 00:05:14,940
그래서 우리는 볼 필요가 있습니다
적은 수의 요소에, 오른쪽?

120
00:05:14,940 --> 00:05:18,580
우리는이 작업을 반복 할 필요가 없습니다
배의 수를 처리한다.

121
00:05:18,580 --> 00:05:19,540
>> 그래서 무엇을 의미합니까?

122
00:05:19,540 --> 00:05:22,390
그래서는 최악의 시나리오입니다
버블 정렬을 위해, 그리고 무엇

123
00:05:22,390 --> 00:05:25,330
거품 정렬을위한 최상의 시나리오?

124
00:05:25,330 --> 00:05:27,770
당신은이를 생각 했습니까?

125
00:05:27,770 --> 00:05:32,420
최악의 경우에는 반복해야
모든 N 원소 N 회에 걸쳐.

126
00:05:32,420 --> 00:05:34,220
따라서 최악의 경우는 N 제곱된다.

127
00:05:34,220 --> 00:05:36,550
>> 배열이 완벽하게되어있는 경우
정렬하지만, 당신 만

128
00:05:36,550 --> 00:05:38,580
각각보고있다
일단 요소.

129
00:05:38,580 --> 00:05:42,670
및 스왑 카운터가 여전히 0이면
이 배열이 정렬됩니다 말할 수 있습니다.

130
00:05:42,670 --> 00:05:45,780
그리고 최상의 경우이다
선택보다 실제로 더 나은

131
00:05:45,780 --> 00:05:49,230
sort--는 N의 오메가이다.

132
00:05:49,230 --> 00:05:50,270
>> 나는 더그 로이드입니다.

133
00:05:50,270 --> 00:05:52,140
이 CS50입니다.

134
00:05:52,140 --> 00:05:54,382