1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN - 스미스 : 안녕, 난 마크 해요
스미스를 Grozen, 이것은 퀵 정​​렬입니다.

3
00:00:10,390 --> 00:00:13,520
그냥 삽입 정렬과 거품 같은
정렬, 퀵 정렬을위한 알고리즘이다

4
00:00:13,520 --> 00:00:15,720
목록이나 물건의 배열을 정렬.

5
00:00:15,720 --> 00:00:19,080
단순 들어, 가정하자 그들
물건은 정수이지만,

6
00:00:19,080 --> 00:00:22,060
퀵 정렬이 작동 것을 알고
단지 숫자보다.

7
00:00:22,060 --> 00:00:24,720
퀵 스타트는 조금 더 복잡하다
보다 삽입 또는 거품 만입니다

8
00:00:24,720 --> 00:00:27,560
또한 훨씬 더 효율적
대부분의 경우.

9
00:00:27,560 --> 00:00:28,150
잠깐만.

10
00:00:28,150 --> 00:00:30,760
그는 단지 "대부분의 말 했는가
경우, ""모든 "?

11
00:00:30,760 --> 00:00:31,710
흥미롭게도, 아니.

12
00:00:31,710 --> 00:00:33,560
모든 경우에 동일합니다.

13
00:00:33,560 --> 00:00:36,650
이 세부 사항에 대해 걱정하지 마십시오 당신이 경우
아직 큰 O 표기법을 볼 수 있지만하지 않은

14
00:00:36,650 --> 00:00:39,730
퀵 정렬은 O (N 제곱) 알고리즘
최악의 경우, 단지 등

15
00:00:39,730 --> 00:00:41,430
삽입 또는 버블 정렬.

16
00:00:41,430 --> 00:00:44,950
그러나, 일반적으로 더 많은 역할
오래된 아날로그 M 알고리즘 등을들 수있다.

17
00:00:44,950 --> 00:00:45,750
왜?

18
00:00:45,750 --> 00:00:46,810
우리는 그건 나중에 다시 해보자.

19
00:00:46,810 --> 00:00:49,610
하지만 지금은 그냥 배워 봅시다
퀵 정렬이 작동하는 방법.

20
00:00:49,610 --> 00:00:53,080
>> 그럼이 Quicksorting를 살펴 보자
최소의 정수의 배열

21
00:00:53,080 --> 00:00:54,260
규모에.

22
00:00:54,260 --> 00:01:00,110
여기에서 우리는, 정수 6을
4.0, 1, 3, 8, 4, 7, 9, 2.

23
00:01:00,110 --> 00:01:03,480
첫째, 최종 요소의 픽
이 배열 -이 경우, 두 -

24
00:01:03,480 --> 00:01:06,870
그 "피벗"라고 부릅니다. 다음으로,
두 가지를보고 시작합니다 -

25
00:01:06,870 --> 00:01:10,220
하나, 나는이 참조하는 것입니다 가장 낮은 인덱스,
의 권리에 머무는 등

26
00:01:10,220 --> 00:01:13,970
벽, 그리고, 둘, 왼쪽
내가 "현재 전화 할게 요소,

27
00:01:13,970 --> 00:01:17,260
요소입니다. "우리가하려고하는 것은
다른 모든 다른 요소를보고

28
00:01:17,260 --> 00:01:20,930
피벗보다는, 모든 요소를​​ 넣어
피벗보다 작은

29
00:01:20,930 --> 00:01:24,140
벽의 왼쪽과 모든 사람
피벗보다 큰

30
00:01:24,140 --> 00:01:25,570
벽의 오른쪽.

31
00:01:25,570 --> 00:01:29,560
그리고, 마지막으로, 우리는 피벗을 삭제합니다
바로 사이에 넣어 그 벽에

32
00:01:29,560 --> 00:01:32,970
그것보다 작은 모든 숫자
모든 숫자를 더.

33
00:01:32,970 --> 00:01:34,460
>> 그럼 그렇게합시다.

34
00:01:34,460 --> 00:01:38,540
2 픽업,에 벽을두고
시작 및 6 "현재 전화

35
00:01:38,540 --> 00:01:41,590
요소입니다. "그래서 우리는보고 싶지
현재 요소 6.

36
00:01:41,590 --> 00:01:44,200
그리고보다 큰이기 때문에
2, 우리는 거기두고

37
00:01:44,200 --> 00:01:45,610
벽의 오른쪽.

38
00:01:45,610 --> 00:01:48,980
그 후, 우리는 5를보고 이동 우리
현재 요소 수 있으며 그이

39
00:01:48,980 --> 00:01:51,840
다시, 인 피벗보다 큰, 그래서 우리
는 오른쪽에 위치를두고

40
00:01:51,840 --> 00:01:53,190
벽의 측면.

41
00:01:53,190 --> 00:01:53,880
우리는 이동합니다.

42
00:01:53,880 --> 00:01:56,750
우리의 현재 요소입니다
지금 1과 - 오.

43
00:01:56,750 --> 00:01:58,030
이제이 다릅니다.

44
00:01:58,030 --> 00:02:00,890
현재 요소는 지금보다 작은
요점은, 그래서 우리는 그것을두고 싶은

45
00:02:00,890 --> 00:02:02,570
벽의 왼쪽에.

46
00:02:02,570 --> 00:02:06,555
이렇게하려면, 그냥 가서 할 일
가장 낮은 인덱스를 현재 요소

47
00:02:06,555 --> 00:02:07,970
다만 벽의 오른쪽에 앉아.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
이제, 우리는 하나의 인덱스까지 벽을 이동
그래서 하나는 좌측에

50
00:02:17,570 --> 00:02:19,750
이제 벽의 측면.

51
00:02:19,750 --> 00:02:20,310
>> 기다립니다.

52
00:02:20,310 --> 00:02:23,450
나는 단지의 요소를 혼합
벽의 오른쪽에, 내가하지 않았다?

53
00:02:23,450 --> 00:02:23,890
걱정하지 마십시오.

54
00:02:23,890 --> 00:02:24,930
괜찮아요.

55
00:02:24,930 --> 00:02:27,570
우리가 지금 관심은 온통
입니다 이러한 모든 요소

56
00:02:27,570 --> 00:02:29,570
벽의 권리는 더 커
피벗보다.

57
00:02:29,570 --> 00:02:31,760
실제 순서는 아직지지 않습니다.

58
00:02:31,760 --> 00:02:33,200
>> 이제, 정렬합니다.

59
00:02:33,200 --> 00:02:35,840
그래서 우리는보고 계속
나머지 요소.

60
00:02:35,840 --> 00:02:39,075
이 경우, 우리는이 있다는 것을 볼
보다 다른 요소에 덜

61
00:02:39,075 --> 00:02:42,100
피벗, 그래서 우리는에 그들 모두를 남겨
벽의 오른쪽.

62
00:02:42,100 --> 00:02:45,980
마지막으로, 우리는 현재 요소에 도착
그것이 요점 것을 볼 수 있습니다.

63
00:02:45,980 --> 00:02:48,830
자, 우리는 두 가지를 가지고 있음을 의미
배열, 제 존재의 섹션

64
00:02:48,830 --> 00:02:51,820
피벗에 및 좌측 작은
벽, 두 번째 존재의

65
00:02:51,820 --> 00:02:54,500
피벗보다 큰
벽의 오른쪽.

66
00:02:54,500 --> 00:02:57,040
우리는 사이 피벗 요소를 넣을
두, 그리고, 우리는 알 수 있습니다

67
00:02:57,040 --> 00:03:01,000
요점은 오른쪽에 있음
최종 정렬 된 장소.

68
00:03:01,000 --> 00:03:04,980
그래서 우리는 첫 번째 요소를 전환
피벗과 벽의 오른쪽,

69
00:03:04,980 --> 00:03:06,410
우리가 알고있는 피벗의
오른쪽 위치에있다.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> 우리는 그 다음에이 과정을 반복
서브 어레이는 왼쪽과 피벗 오른쪽.

72
00:03:15,650 --> 00:03:18,700
마지막 서브 어레이는 하나이므로
요소 긴, 우리는 이미 알고있다

73
00:03:18,700 --> 00:03:22,480
정렬 방법 당신이 밖으로 할 수 있기 때문에
당신은 하나의 요소 만 있다면 주문?

74
00:03:22,480 --> 00:03:28,860
배열의 오른쪽에, 우리는
피봇 벽보기 5이고, 볼

75
00:03:28,860 --> 00:03:32,250
다만 6 남아 있습니다.

76
00:03:32,250 --> 00:03:34,970
그리고 현재 요소도
6으로 시작한다.

77
00:03:34,970 --> 00:03:36,200
그래서 6은 5보다 큽니다.

78
00:03:36,200 --> 00:03:38,590
이에 우리는 어디에두고
벽의 오른쪽.

79
00:03:38,590 --> 00:03:41,060
자, 이동, 3은 5보다 작습니다.

80
00:03:41,060 --> 00:03:44,160
그래서 우리는 첫 번째 요소로 전환
벽의 바로.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
지금, 나는 하나까지 벽을 움직였다.

83
00:03:50,750 --> 00:03:53,010
이제 8로 이동하기.

84
00:03:53,010 --> 00:03:56,480
8, 5보다 큰
그래서 우리는 그것을 둡니다.

85
00:03:56,480 --> 00:03:58,720
4는 5보다 작은, 그래서 우리는 그것을 전환 할 수 있습니다.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
그리고에.

88
00:04:03,570 --> 00:04:04,820
그리고에.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> 우리의 과정을 반복 할 때마다
어레이의 좌우측. 우리

91
00:04:13,670 --> 00:04:17,010
피벗을 선택하고 비교를 할
왼쪽의 또 다른 레벨을 작성하고

92
00:04:17,010 --> 00:04:18,240
바로 하위 배열.

93
00:04:18,240 --> 00:04:21,500
이 재귀 호출까지 계속됩니다
우리는 우리가했습니다 끝에 도달

94
00:04:21,500 --> 00:04:25,290
로 전체 배열을 분할
길이 1 단지 하위 배열.

95
00:04:25,290 --> 00:04:28,060
거기에서, 우리는 배열을 정렬 알고
모든 요소가 있기 때문에,에

96
00:04:28,060 --> 00:04:29,330
어떤 점은, 피벗이었다.

97
00:04:29,330 --> 00:04:32,720
즉, 각 요소에 대해, 모든
왼쪽의 숫자가 적은 아르

98
00:04:32,720 --> 00:04:36,420
값과 모든 숫자
바로 더 큰 값을 갖습니다.

99
00:04:36,420 --> 00:04:38,980
>> 이 방법은 아주 잘 작동하는 경우
선택 피벗의 값은

100
00:04:38,980 --> 00:04:41,930
약 중간에
목록 값의 범위.

101
00:04:41,930 --> 00:04:45,630
우리가 이동 한 후이는 것을 의미 할 것입니다
많은 약이 주변 요소,

102
00:04:45,630 --> 00:04:48,390
피벗의 왼쪽에있는 요소
오른쪽에 있기 때문에.

103
00:04:48,390 --> 00:04:52,380
그리고의 분할 정복 자연
퀵 정렬 알고리즘은 다음 촬영

104
00:04:52,380 --> 00:04:53,850
의 이점.

105
00:04:53,850 --> 00:04:57,500
이 O의 런타임 생성 (N N 로그인)
우리가해야 할 N - 1 N 있기 때문에

106
00:04:57,500 --> 00:05:01,640
각 생성 및 로그에 대한 비교
, 우리는 목록을 분할해야하기 때문에 N

107
00:05:01,640 --> 00:05:03,210
N 시간을 기록합니다.

108
00:05:03,210 --> 00:05:06,160
그러나 최악의 경우에, 이것은
알고리즘은 실제로 O (N이 될 수 있습니다

109
00:05:06,160 --> 00:05:09,850
제곱.) 각 세대에 가정,
요점은 그렇게 될 일이

110
00:05:09,850 --> 00:05:12,520
최소 또는 최대의
우리가 정렬하고 번호.

111
00:05:12,520 --> 00:05:15,870
이 목록을 나누는 의미
배를 만드는 N - 1 N

112
00:05:15,870 --> 00:05:17,690
비교 매번.

113
00:05:17,690 --> 00:05:20,490
따라서, N의 O를 제곱.

114
00:05:20,490 --> 00:05:22,000
>> 우리가 어떻게 방법을 개선 할 수 있습니까?

115
00:05:22,000 --> 00:05:25,100
방법을 개선하기위한 한 가지 좋은 방법은
확률을 줄이기 위해 해당

116
00:05:25,100 --> 00:05:28,150
런타임은 지금까지 실제로
N의 오 제곱.

117
00:05:28,150 --> 00:05:31,860
최악의, 최악의 시나리오를 기억
만 일어날 수있는 경우

118
00:05:31,860 --> 00:05:35,320
선택 피벗은 항상 최고입니다
또는 배열의 가장 낮은 값.

119
00:05:35,320 --> 00:05:38,630
이런 일이 일어날 가능성이 적습니다 보장하기 위해,
우리가 피벗을 찾을 수 있습니다

120
00:05:38,630 --> 00:05:42,610
여러 요소를 선택
중간 값을 가지고.

121
00:05:42,610 --> 00:05:44,650
>> 내 이름은 마크 Grozen - 스미스
이것은 CS50이다.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> 단순 들어, 가정하자 그들
물건은 정수이지만,

124
00:05:50,930 --> 00:05:51,970
그 Quicksert 알 -

125
00:05:51,970 --> 00:05:53,160
Quicksert?

126
00:05:53,160 --> 00:05:55,200
미안 해요.

127
00:05:55,200 --> 00:06:02,000
>> 여기에 우리가 정수가
6, 4.0, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> 스피커 1 : 정말?

129
00:06:03,200 --> 00:06:04,850
>> 스피커 2 : 거기서 멈추지 마십시오.

130
00:06:04,850 --> 00:06:06,100
>> 스피커 1 : 정말?

131
00:06:06,100 --> 00:06:08,491