>> MARK GROZEN - 스미스 : 안녕, 난 마크 해요 스미스를 Grozen, 이것은 퀵 정​​렬입니다.
그냥 삽입 정렬과 거품 같은 정렬, 퀵 정렬을위한 알고리즘이다
목록이나 물건의 배열을 정렬.
단순 들어, 가정하자 그들 물건은 정수이지만,
퀵 정렬이 작동 것을 알고 단지 숫자보다.
퀵 스타트는 조금 더 복잡하다 보다 삽입 또는 거품 만입니다
또한 훨씬 더 효율적 대부분의 경우.
잠깐만.
그는 단지 "대부분의 말 했는가 경우, ""모든 "?
흥미롭게도, 아니.
모든 경우에 동일합니다.
이 세부 사항에 대해 걱정하지 마십시오 당신이 경우 아직 큰 O 표기법을 볼 수 있지만하지 않은
퀵 정렬은 O (N 제곱) 알고리즘 최악의 경우, 단지 등
삽입 또는 버블 정렬.
그러나, 일반적으로 더 많은 역할 오래된 아날로그 M 알고리즘 등을들 수있다.
왜?
우리는 그건 나중에 다시 해보자.
하지만 지금은 그냥 배워 봅시다 퀵 정렬이 작동하는 방법.
>> 그럼이 Quicksorting를 살펴 보자 최소의 정수의 배열
규모에.
여기에서 우리는, 정수 6을 4.0, 1, 3, 8, 4, 7, 9, 2.
첫째, 최종 요소의 픽 이 배열 -이 경우, 두 -
그 "피벗"라고 부릅니다. 다음으로, 두 가지를보고 시작합니다 -
하나, 나는이 참조하는 것입니다 가장 낮은 인덱스, 의 권리에 머무는 등
벽, 그리고, 둘, 왼쪽 내가 "현재 전화 할게 요소,
요소입니다. "우리가하려고하는 것은 다른 모든 다른 요소를보고
피벗보다는, 모든 요소를​​ 넣어 피벗보다 작은
벽의 왼쪽과 모든 사람 피벗보다 큰
벽의 오른쪽.
그리고, 마지막으로, 우리는 피벗을 삭제합니다 바로 사이에 넣어 그 벽에
그것보다 작은 모든 숫자 모든 숫자를 더.
>> 그럼 그렇게합시다.
2 픽업,에 벽을두고 시작 및 6 "현재 전화
요소입니다. "그래서 우리는보고 싶지 현재 요소 6.
그리고보다 큰이기 때문에 2, 우리는 거기두고
벽의 오른쪽.
그 후, 우리는 5를보고 이동 우리 현재 요소 수 있으며 그이
다시, 인 피벗보다 큰, 그래서 우리 는 오른쪽에 위치를두고
벽의 측면.
우리는 이동합니다.
우리의 현재 요소입니다 지금 1과 - 오.
이제이 다릅니다.
현재 요소는 지금보다 작은 요점은, 그래서 우리는 그것을두고 싶은
벽의 왼쪽에.
이렇게하려면, 그냥 가서 할 일 가장 낮은 인덱스를 현재 요소
다만 벽의 오른쪽에 앉아.
이제, 우리는 하나의 인덱스까지 벽을 이동 그래서 하나는 좌측에
이제 벽의 측면.
>> 기다립니다.
나는 단지의 요소를 혼합 벽의 오른쪽에, 내가하지 않았다?
걱정하지 마십시오.
괜찮아요.
우리가 지금 관심은 온통 입니다 이러한 모든 요소
벽의 권리는 더 커 피벗보다.
실제 순서는 아직지지 않습니다.
>> 이제, 정렬합니다.
그래서 우리는보고 계속 나머지 요소.
이 경우, 우리는이 있다는 것을 볼 보다 다른 요소에 덜
피벗, 그래서 우리는에 그들 모두를 남겨 벽의 오른쪽.
마지막으로, 우리는 현재 요소에 도착 그것이 요점 것을 볼 수 있습니다.
자, 우리는 두 가지를 가지고 있음을 의미 배열, 제 존재의 섹션
피벗에 및 좌측 작은 벽, 두 번째 존재의
피벗보다 큰 벽의 오른쪽.
우리는 사이 피벗 요소를 넣을 두, 그리고, 우리는 알 수 있습니다
요점은 오른쪽에 있음 최종 정렬 된 장소.
그래서 우리는 첫 번째 요소를 전환 피벗과 벽의 오른쪽,
우리가 알고있는 피벗의 오른쪽 위치에있다.
>> 우리는 그 다음에이 과정을 반복 서브 어레이는 왼쪽과 피벗 오른쪽.
마지막 서브 어레이는 하나이므로 요소 긴, 우리는 이미 알고있다
정렬 방법 당신이 밖으로 할 수 있기 때문에 당신은 하나의 요소 만 있다면 주문?
배열의 오른쪽에, 우리는 피봇 벽보기 5이고, 볼
다만 6 남아 있습니다.
그리고 현재 요소도 6으로 시작한다.
그래서 6은 5보다 큽니다.
이에 우리는 어디에두고 벽의 오른쪽.
자, 이동, 3은 5보다 작습니다.
그래서 우리는 첫 번째 요소로 전환 벽의 바로.
지금, 나는 하나까지 벽을 움직였다.
이제 8로 이동하기.
8, 5보다 큰 그래서 우리는 그것을 둡니다.
4는 5보다 작은, 그래서 우리는 그것을 전환 할 수 있습니다.
그리고에.
>> 우리의 과정을 반복 할 때마다 어레이의 좌우측. 우리
피벗을 선택하고 비교를 할 왼쪽의 또 다른 레벨을 작성하고
바로 하위 배열.
이 재귀 호출까지 계속됩니다 우리는 우리가했습니다 끝에 도달
로 전체 배열을 분할 길이 1 단지 하위 배열.
거기에서, 우리는 배열을 정렬 알고 모든 요소가 있기 때문에,에
어떤 점은, 피벗이었다.
즉, 각 요소에 대해, 모든 왼쪽의 숫자가 적은 아르
값과 모든 숫자 바로 더 큰 값을 갖습니다.
>> 이 방법은 아주 잘 작동하는 경우 선택 피벗의 값은
약 중간에 목록 값의 범위.
우리가 이동 한 후이는 것을 의미 할 것입니다 많은 약이 주변 요소,
피벗의 왼쪽에있는 요소 오른쪽에 있기 때문에.
그리고의 분할 정복 자연 퀵 정렬 알고리즘은 다음 촬영
의 이점.
이 O의 런타임 생성 (N N 로그인) 우리가해야 할 N - 1 N 있기 때문에
각 생성 및 로그에 대한 비교 , 우리는 목록을 분할해야하기 때문에 N
N 시간을 기록합니다.
그러나 최악의 경우에, 이것은 알고리즘은 실제로 O (N이 될 수 있습니다
제곱.) 각 세대에 가정, 요점은 그렇게 될 일이
최소 또는 최대의 우리가 정렬하고 번호.
이 목록을 나누는 의미 배를 만드는 N - 1 N
비교 매번.
따라서, N의 O를 제곱.
>> 우리가 어떻게 방법을 개선 할 수 있습니까?
방법을 개선하기위한 한 가지 좋은 방법은 확률을 줄이기 위해 해당
런타임은 지금까지 실제로 N의 오 제곱.
최악의, 최악의 시나리오를 기억 만 일어날 수있는 경우
선택 피벗은 항상 최고입니다 또는 배열의 가장 낮은 값.
이런 일이 일어날 가능성이 적습니다 보장하기 위해, 우리가 피벗을 찾을 수 있습니다
여러 요소를 선택 중간 값을 가지고.
>> 내 이름은 마크 Grozen - 스미스 이것은 CS50이다.
>> 단순 들어, 가정하자 그들 물건은 정수이지만,
그 Quicksert 알 -
Quicksert?
미안 해요.
>> 여기에 우리가 정수가 6, 4.0, 1, 3, 8, 4, 9.
>> 스피커 1 : 정말?
>> 스피커 2 : 거기서 멈추지 마십시오.
>> 스피커 1 : 정말?