[Powered by Google Translate] [버블 정렬]
[잭슨 STEINKAMP 하버드 대학]
[이것은 CS50입니다. CS50TV]
버블 정렬은 정렬 알고리즘의 예입니다 -
즉, 요소​​의 집합을 분류하는 절차입니다
오름차순 또는 내림차순.
당신이 배열을 정렬하고자 할 경우 예를 들어, 숫자로 구성
[3, 5, 2, 9], 버블 정렬의 올바른 구현은을 반환
정렬 배열 [2, 3, 5, 9] 오름차순 인치
자, 알고리즘 작동 방식 의사에 설명 할게.
>> 3, 2, 9, 6, 5 - 우리 5 정수의 목록을 정렬하고 있다고 가정 해 보겠습니다.
이 알고리즘은, 처음 두 가지 요소, 3, 2를보고 시작
그들은 서로에 대해 순서 경우 ​​및 확인.
사람들이 - 3은 2보다 큰 수 있습니다.
오름차순으로 말하자면, 그들은 반대해야합니다.
그래서 우린 그들을 교환.
[2, 3, 9, 6, 5] : 지금 목록은 다음과 같습니다.
>> 다음, 우리는 두 번째와 세 번째 요소, 3과 9 좀 봐.
그들은 서로에 대해 올바른 순서에 있어요.
알고리즘을 교환하지 않습니다 아홉 미만 있도록 즉, 3입니다.
다음, 우리는 9 6 봐요. 그들은 순서 나간다.
>> 그래서, 우리는 9가 6보다 큰 있기 때문에를 교환해야합니다.
마지막으로, 우리는 마지막 두 정수, 9, 5 봐요.
그들은 순서입니다, 그러니 그들은 교체해야합니다.
목록을 첫 번째 패스 후,
[2, 3, 6, 5, 9] : 만약이 것 같습니다.
나쁘지 않군. 그것은 거의 정렬있어.
하지만 우리는 완전히 해결할 수 다시 목록을 실행해야합니다.
두 세 이하이기 때문에, 우리는 그들을 교체하지 않습니다.
>> 세 6 이하이기 때문에, 우리는 그들을 교체하지 않습니다.
여섯는 5보다 큽니다. 우리는 교체.
여섯는 9보다 작습니다. 우리는 교환하지 않습니다.
를 통해 두 번째 패스 후 다음과 같습니다 [2, 3, 5, 6, 9]. 좋아요.
이제 의사에 쓸 까.
기본적으로 목록의 각 요소에 대해, 우리는 볼 필요가
직접 그 오른쪽에있는 요소입니다.
그들은 순서 서로에 대해 알아 인 경우 - 즉, 경우 왼쪽에있는 요소
오른쪽에있는 것보다 더 큰 - 우리는 두 가지 요소를 교체해야합니다.
>> 우리는 목록의 모든 요소에이 작업을 수행, 우리는을 통해 원 패스 사항을 적용했습니다.
이제 우리는 목록을 보장하기 위해 통과 시간도 충분해야
완전히 제대로 정렬됩니다.
그러나 우리는에 목록을 통과하는 방법을 몇 번해야합니까
우리가 완료되는 것은?
우리는 완전히 거꾸로 목록이있는 경우 그럼, 최악의 시나리오입니다.
그럼 번호와 같은 통과 - throughs의 번호를 걸립니다
요소 N-1.
이 직관적으로 이해가되지 않는 경우, 간단한 사건을 생각 - 목록 [2, 1].
>> 이 올바르게 정렬 한 통과 데려 갈 수 있습니다.
[3, 2, 1] - 최악의 경우는, 3 요소와 하위 정렬 것입니다
이 정렬에서 2 반복을 할 거예요.
한 반복 후 [, 3 1 2]입니다.
두 번째 수익률 정렬 배열 [1, 2, 3].
그래서 당신은, 당신은 일반적으로 배열을 통해 갈 필요가 없습니다 알
n은 배열의 요소의 수입니다 N-1 번, 이상.
가장 큰 요소가 '버블 업'으로 경향이 있기 때문에이 버블 정렬이라는
너무 빨리 오른쪽으로.
사실,이 알고리즘은 매우 흥미로운 행동이 있습니다.
>> 전체 배열을 통해 m 반복 후,
가장 오른쪽 m 요소가 보장
자신의 올바른 위치에 정렬 할 수 있습니다.
당신은 자신이보고 싶다면
우리는 완전히 거꾸로 목록 [9, 6, 5, 3, 2]에 시도해 볼 수 있습니다.
전체 목록을 원 패스 후,
[글의 소리]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
가장 오른쪽 엘리먼트 9의 적절한 위치에 있습니다.
통과 번째 후, 6 '부풀어 오른 업'해야합니다
둘째 가장 오른쪽 위치.
6 9 - - 오른쪽에있는 두 가지 요소는 올바른 장소에있을 것입니다
처음 두 패스 - throughs 후.
>> 그래, 어떻게 우리는 알고리즘을 최적화시킬 수 있습니다?
음, 배열을 관통 반복 한 후
우리는 실제로 가장 오른쪽 요소를 확인 할 필요가 없습니다
우리가 알고 있기 때문에이 정렬있어.
이 반복되면, 우리는 가장 오른쪽 두 가지 요소는 위치에 있는지에 대해 알아.
그래서, 일반적으로, 전체 배열을 통해 K 반복 후,
우리가 알고 있기 때문에 마지막 K 요소를 확인하는 것은 중복이다
그들은 이미 올바른 위치에있어.
>> 당신이 N 요소의 배열을 정렬하는하면,
첫 번째 반복에서 - 테고 모든 요소를​​ 정렬해야 - 첫 번째 N-0.
두 번째 반복에서는 요소의 모든하지만 마지막 살펴해야합니다 -
N-1 첫 번째.
또 다른 최적화 목록이 이미 정렬되어 있는지 확인하는 것입니다
각 반복 후.
이미 정렬되어있는 경우, 우리는 더 이상 반복을 할 필요가 없습니다
목록을.
우리가 어떻게이 작업을 수행 할 수 있습니까?
음, 우리는 목록의 통과에 어떤 스왑하지 않는 경우,
우리가 아무것도 교환하지 않았기 때문에이 목록은 이미 정렬 된 것을 분명하다.
그래서 우리는 확실히 다시 정렬 할 필요가 없습니다.
>> 아마도 당신은에 '정렬되지'라는 플래그 변수를 초기화 할 수
당신은에 어떤 요소를 교환해야하는 경우 false로하고 진실한로 변경
배열을 관통 반복.
또는 이와 유사한, 당신 말은 얼마나 많은 스왑 계산하기 위해 카운터를
특정 반복 있습니다.
반복의 끝에서, 당신이 요소를 교환하지 않은 경우는,
당신은 목록이 이미 정렬하면 모든 작업이 완료됩니다 알아요.
버블 정렬은 다른 정렬 알고리즘처럼 될 수 있습니다
주문 방법을 가지고있는 요소에 대한 작업 불통.
>> 그런 말 할 수있는 방법이 두 가지 요소에게 주어진 경우 첫 번째
같거나 두 번째보다,보다 큽니다.
예를 들어, 말하여 알파벳 문자를 정렬 할 수
<B, B <C, 등이
일요일 월요일 미만 곳 또는 요일을 정렬 할 수
어느 화요일 미만의 거리에 있습니다.
>> 더는 매우 효율적인 또는 빠른 정렬 알고리즘을 의미하여 버블 정렬이되지 않습니다.
의 최악의 런타임 n의 빅 O입니다 ²
당신은 목록을 N 반복을해야하기 때문에
각 통과 모든 N 요소를 확인, nxn = N ².
이 실행 시간은 원소의 개수로는 증가를 정렬하는 것을 의미합니다
실행 시간은 quadratically 증가합니다.
>> 그러나 효율이 프로그램의 주요 관심사가 아닌 경우
또는 유일한 요소의 작은 숫자를 정렬하는 경우,
당신은 버블 정렬 유용한 이유
그것은 이해하는 가장 간단한 정렬 알고리즘 중 하나
및 코드입니다.
또한 이론적 번역 경험을 얻을 수있는 좋은 방법입니다
실제 작동 코드로 알고리즘입니다.
그게 당신을위한 버블 정렬입니다. 시청 해 주​​셔서 감사합니다.
CS50.TV