>> [음악 재생]
DOUG 로이드 : 좋아, 그래서 버블 정렬은 알고리즘
는 요소들의 세트를 정렬하는 데 사용할 수있다.
이제 어떻게 작동하는지 살펴 보자.
>> 그래서 기본 아이디어 뒤에 버블 정렬이입니다.
우리는 일반적으로 더 높은 이동할 일반적으로 오른쪽에 상당 소자
일반적으로 평가 요소를 낮출 왼쪽에, 우리가 기대하는 것처럼.
우리는 낮은 가지에가되고 싶어요 시작 및 높은 것들
마지막에한다.
>> 우리는 어떻게해야합니까?
그럼 의사 코드, 우리는의를하자, 말할 수
0이 아닌 값으로 스왑 카운터를 설정한다.
우리는 두 번째에 그렇게 할 이유를 우리는 볼 수 있습니다.
그리고 우리는 다음을 반복 스왑 카운터가 0이 될 때까지 공정
또는 우리는 전혀 스왑을하지 않을 때까지.
>> 에 스왑 카운터를 재설정 0 이미 0이 아니라면.
그런 다음에 모든보고 요소의 인접 쌍.
이 두 요소가있는 경우 하지 않게하기 위해, 그들을 스왑
및 스왑 카운터에 1을 추가합니다.
당신에 대해 생각하는 경우 이 당신이 그것을 시각화하기 전에,
이 낮은 이동합니다 통지 왼쪽으로 평가 요소
이상, 우측 요소를 반환 효과적으로 우리가하고 싶은 일을,
이는 해당 그룹을 이동입니다 그런 식의 요소.
의 방법이 시각화하자 우리의 배열을 사용하여 볼 수 있습니다
우리가 테스트하는 데 사용 이러한 알고리즘 아웃.
우리는 여기에 다시 정렬되지 않은 배열을 가지고 모든 요소에 의해 지시
빨간색에있는.
그리고 나는 나의 스왑 카운터를 설정 0이 아닌 값으로.
내가 임의로 선택 부정적인 1--은 0이 아니다.
우리는이 프로세스를 반복 할 스왑 카운터까지 0입니다.
내 스왑을 설정하는 이유입니다 0이 아닌 값으로 카운터
그렇지 않으면 때문에 스왑 카운터는 0이 될 것이다.
우리는 심지어을 시작하지 않을 알고리즘의 방법.
그래서 다시, 단계으로 죠 스왑 카운터를 재설정
0, 다음, 모든 인접보고 쌍, 그들은 순서가 있다면,
를 교환하고, 1을 추가 스왑 카운터.
그래서이 과정을 시작합시다.
그래서 우리가 먼저입니다 우리가 0으로 스왑 카운터 설정
그리고, 우리는보고 시작 인접한 각에서.
>> 그래서 우리는 처음 5와 2를보고 시작합니다.
우리는 그들이 벗어난 것을 확인할 주문하고 그래서 우리는 그들을 교환합니다.
그리고 우리는 스왑 카운터에 1을 추가합니다.
그래서 지금 우리의 스왑 카운터가 1이고, 및 (2)와 (5)는 전환되었다.
이제 우리는 다시 프로세스를 반복합니다.
>> 우리는 다음 인접한 한 쌍을보고, 5 그들은 또한 순서가있어 1--,
그래서 우리는 그들을 교체 및 추가 스왑 카운터 1.
그 다음 우리는 5와 3 봐.
그들은 순서가, 그래서 우리는 스왑 그들과 우리는 스왑 카운터에 1을 추가합니다.
그럼 우리가 5와 6을 봐주세요.
그들은 순서에있어, 그래서 우리는 실제로하지 않습니다 아무것도이 시간을 교체해야합니다.
그 다음 우리는 6과 4를 봐주세요.
그들은 순서가도, 그래서 우리는 스왑 그들과 우리는 스왑 카운터에 1을 추가합니다.
>> 지금 일어난 것을 알 수 있습니다.
우리는 끝 6 줄곧 옮겼다.
선택의 종류에 따라서, 당신이 한 경우 그 비디오를 본, 우리가 한 일은이었다
우리는 이동 결국 건물의 작은 요소
본질적으로 정렬 된 배열 최대 규모로, 작은 왼쪽에서 오른쪽으로.
버블 정렬의 경우, 우리는이 있다면 이 특정 알고리즘 다음,
우리는 실제로 구축 할거야 오른쪽 정렬 된 배열
최소로, 가장 왼쪽에.
우리는 효과적으로 6을 발포 한 최대 값, 일단 모든 방법.
>> 그래서 우리는 지금 선언 할 수 있습니다 즉 분류된다,
미래에 iterations-- 배열을 통과 again--
우리는 더 이상 (6)을 고려해야 할 필요가 없습니다.
우리는 고려해야 할 정렬되지 않은 요소
때 우리가 인접한 찾고 있습니다.
그래서 우리는 하나를 완료 거품 정렬을 통해 전달합니다.
그래서 지금 우리가 질문으로 돌아가, 스왑 카운터가 0이 될 때까지 반복합니다.
그럼 스왑 카운터 4, 그래서 우리는거야
다시이 과정을 계속 반복합니다.
>> 우리는 스왑 카운터를 재설정거야 0으로, 각 인접한 쌍 봐.
그래서 우리는 그들이있어 1-- 2로 시작 순서가, 그래서 우리는 그들을 교환
우리는 스왑 카운터에 1을 추가합니다.
2, 3, 그들은 순서에있어.
우리는 아무것도 할 필요가 없습니다.
3과 5는 순서에 있습니다.
우리는이 작업을 수행 할 필요가 없습니다.
>> 5, 4, 그들이 외출 주문, 그래서 우리를
를 교환하고 추가 할 필요가 스왑 카운터 1.
그리고 지금 우리는 5 이동 한 다음 가장 큰 요소,
정렬되지 않은 부분의 끝까지.
그래서 우리는 지금를 호출 할 수 있습니다 정렬 된 부분의 일부입니다.
>> 지금 당신은보고있다 화면 아마도 말할 수,
내가 할 수있는 배열과 지금 정렬됩니다.
그러나 우리는 아직 증명할 수 없습니다.
우리는 보장이 없습니다 그것이이 분류입니다.
그러나 이것은 어디 스왑입니다 카운터 플레이로 올 것입니다.
>> 그래서 우리는 패스를 완료 한.
스왑 카운터는 2입니다.
그래서 우리는 반복하는거야 다시 공정
스왑 카운터가 0이 될 때까지 반복합니다.
0 스왑 카운터를 재설정합니다.
그래서 우리는 그것을 다시 설정합니다.
>> 지금 인접한 각 봐.
즉, 순서대로 1, 2입니다.
도 2 및도 3은 순서이다.
도 3 및도 4는 순서이다.
따라서이 시점에서, 우리가 완료 한 알 모든 인접 쌍을보고,
하지만 스왑 카운터는 여전히 0입니다.
>> 우리는 전환 할 수없는 경우 모든 요소를​​, 다음
에 의해, 순서에 있어야합니다 이 과정의 미덕.
그리고 종류의 효율, 그 우리의 컴퓨터 과학자들은 사랑,
우리는 지금 선언 할 수있다 전체 배열해야
우리가하지 않았기 때문에, 정렬 모든 요소를​​ 교체해야합니다.
그건 꽤 좋은 데요.
>> 그래서 최악의 경우입니다 버블 정렬과 시나리오?
최악의 경우는 어레이 완전히 역순으로,
그래서 우리는 각 거품에있다 큰 모든 요소
배열에 걸쳐 방법.
그리고 우리는 효과적으로에도있다 거품 작은 모든 요소를​​ 다시
너무 배열에서 모든 방법.
따라서 N 개의 요소들 각각이 이동하는 다른 n 개의 모든 요소에 걸쳐.
그래서 최악의 시나리오이다.
최상의 경우 시나리오는하지만,이입니다
선택 정렬과 약간 다릅니다.
배열은 이미 우리가 갈 때 분류.
우리는 어떤 필요가 없습니다 첫 번째 패스에 스왑.
그래서 우리는 볼 필요가 있습니다 적은 수의 요소에, 오른쪽?
우리는이 작업을 반복 할 필요가 없습니다 배의 수를 처리한다.
>> 그래서 무엇을 의미합니까?
그래서는 최악의 시나리오입니다 버블 정렬을 위해, 그리고 무엇
거품 정렬을위한 최상의 시나리오?
당신은이를 생각 했습니까?
최악의 경우에는 반복해야 모든 N 원소 N 회에 걸쳐.
따라서 최악의 경우는 N 제곱된다.
>> 배열이 완벽하게되어있는 경우 정렬하지만, 당신 만
각각보고있다 일단 요소.
및 스왑 카운터가 여전히 0이면 이 배열이 정렬됩니다 말할 수 있습니다.
그리고 최상의 경우이다 선택보다 실제로 더 나은
sort--는 N의 오메가이다.
>> 나는 더그 로이드입니다.
이 CS50입니다.