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