[음악 재생] 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입니다.