1 00:00:00,500 --> 00:00:02,840 [Powered by Google Translate] [버블 정렬] 2 00:00:02,840 --> 00:00:04,560 [잭슨 STEINKAMP 하버드 대학] 3 00:00:04,560 --> 00:00:07,500 [이것은 CS50입니다. CS50TV] 4 00:00:08,000 --> 00:00:11,730 버블 정렬은 정렬 알고리즘의 예입니다 - 5 00:00:11,730 --> 00:00:14,460 즉, 요소​​의 집합을 분류하는 절차입니다 6 00:00:14,460 --> 00:00:15,840 오름차순 또는 내림차순. 7 00:00:15,840 --> 00:00:18,710 당신이 배열을 정렬하고자 할 경우 예를 들어, 숫자로 구성 8 00:00:18,710 --> 00:00:23,060 [3, 5, 2, 9], 버블 정렬의 올바른 구현은을 반환 9 00:00:23,060 --> 00:00:26,260 정렬 배열 [2, 3, 5, 9] 오름차순 인치 10 00:00:26,260 --> 00:00:28,850 자, 알고리즘 작동 방식 의사에 설명 할게. 11 00:00:28,850 --> 00:00:34,000 >> 3, 2, 9, 6, 5 - 우리 5 정수의 목록을 정렬하고 있다고 가정 해 보겠습니다. 12 00:00:34,000 --> 00:00:37,650 이 알고리즘은, 처음 두 가지 요소, 3, 2를보고 시작 13 00:00:37,650 --> 00:00:40,850 그들은 서로에 대해 순서 경우 ​​및 확인. 14 00:00:40,850 --> 00:00:43,150 사람들이 - 3은 2보다 큰 수 있습니다. 15 00:00:43,150 --> 00:00:45,190 오름차순으로 말하자면, 그들은 반대해야합니다. 16 00:00:45,190 --> 00:00:46,610 그래서 우린 그들을 교환. 17 00:00:46,610 --> 00:00:49,760 [2, 3, 9, 6, 5] : 지금 목록은 다음과 같습니다. 18 00:00:49,760 --> 00:00:52,450 >> 다음, 우리는 두 번째와 세 번째 요소, 3과 9 좀 봐. 19 00:00:52,450 --> 00:00:55,770 그들은 서로에 대해 올바른 순서에 있어요. 20 00:00:55,770 --> 00:00:58,800 알고리즘을 교환하지 않습니다 아홉 미만 있도록 즉, 3입니다. 21 00:00:58,800 --> 00:01:01,900 다음, 우리는 9 6 봐요. 그들은 순서 나간다. 22 00:01:01,900 --> 00:01:04,260 >> 그래서, 우리는 9가 6보다 큰 있기 때문에를 교환해야합니다. 23 00:01:04,260 --> 00:01:08,840 마지막으로, 우리는 마지막 두 정수, 9, 5 봐요. 24 00:01:08,840 --> 00:01:10,850 그들은 순서입니다, 그러니 그들은 교체해야합니다. 25 00:01:10,850 --> 00:01:13,360 목록을 첫 번째 패스 후, 26 00:01:13,360 --> 00:01:17,140 [2, 3, 6, 5, 9] : 만약이 것 같습니다. 27 00:01:17,140 --> 00:01:19,690 나쁘지 않군. 그것은 거의 정렬있어. 28 00:01:19,690 --> 00:01:22,450 하지만 우리는 완전히 해결할 수 다시 목록을 실행해야합니다. 29 00:01:22,450 --> 00:01:29,250 두 세 이하이기 때문에, 우리는 그들을 교체하지 않습니다. 30 00:01:29,250 --> 00:01:31,700 >> 세 6 이하이기 때문에, 우리는 그들을 교체하지 않습니다. 31 00:01:31,700 --> 00:01:35,500 여섯는 5보다 큽니다. 우리는 교체. 32 00:01:35,500 --> 00:01:38,460 여섯는 9보다 작습니다. 우리는 교환하지 않습니다. 33 00:01:38,460 --> 00:01:42,170 를 통해 두 번째 패스 후 다음과 같습니다 [2, 3, 5, 6, 9]. 좋아요. 34 00:01:42,170 --> 00:01:44,680 이제 의사에 쓸 까. 35 00:01:44,680 --> 00:01:48,450 기본적으로 목록의 각 요소에 대해, 우리는 볼 필요가 36 00:01:48,450 --> 00:01:50,060 직접 그 오른쪽에있는 요소입니다. 37 00:01:50,060 --> 00:01:53,420 그들은 순서 서로에 대해 알아 인 경우 - 즉, 경우 왼쪽에있는 요소 38 00:01:53,420 --> 00:01:56,810 오른쪽에있는 것보다 더 큰 - 우리는 두 가지 요소를 교체해야합니다. 39 00:01:56,810 --> 00:02:01,270 >> 우리는 목록의 모든 요소에이 작업을 수행, 우리는을 통해 원 패스 사항을 적용했습니다. 40 00:02:01,270 --> 00:02:05,160 이제 우리는 목록을 보장하기 위해 통과 시간도 충분해야 41 00:02:05,160 --> 00:02:06,480 완전히 제대로 정렬됩니다. 42 00:02:06,480 --> 00:02:08,889 그러나 우리는에 목록을 통과하는 방법을 몇 번해야합니까 43 00:02:08,889 --> 00:02:10,400 우리가 완료되는 것은? 44 00:02:10,400 --> 00:02:14,730 우리는 완전히 거꾸로 목록이있는 경우 그럼, 최악의 시나리오입니다. 45 00:02:14,730 --> 00:02:17,840 그럼 번호와 같은 통과 - throughs의 번호를 걸립니다 46 00:02:17,840 --> 00:02:19,730 요소 N-1. 47 00:02:19,730 --> 00:02:24,720 이 직관적으로 이해가되지 않는 경우, 간단한 사건을 생각 - 목록 [2, 1]. 48 00:02:24,720 --> 00:02:28,430 >> 이 올바르게 정렬 한 통과 데려 갈 수 있습니다. 49 00:02:28,430 --> 00:02:33,060 [3, 2, 1] - 최악의 경우는, 3 요소와 하위 정렬 것입니다 50 00:02:33,060 --> 00:02:34,830 이 정렬에서 2 반복을 할 거예요. 51 00:02:34,830 --> 00:02:37,980 한 반복 후 [, 3 1 2]입니다. 52 00:02:37,980 --> 00:02:39,550 두 번째 수익률 정렬 배열 [1, 2, 3]. 53 00:02:39,550 --> 00:02:43,350 그래서 당신은, 당신은 일반적으로 배열을 통해 갈 필요가 없습니다 알 54 00:02:43,350 --> 00:02:46,790 n은 배열의 요소의 수입니다 N-1 번, 이상. 55 00:02:47,090 --> 00:02:50,470 가장 큰 요소가 '버블 업'으로 경향이 있기 때문에이 버블 정렬이라는 56 00:02:50,470 --> 00:02:51,950 너무 빨리 오른쪽으로. 57 00:02:51,950 --> 00:02:53,980 사실,이 알고리즘은 매우 흥미로운 행동이 있습니다. 58 00:02:53,980 --> 00:02:57,410 >> 전체 배열을 통해 m 반복 후, 59 00:02:57,410 --> 00:02:59,000 가장 오른쪽 m 요소가 보장 60 00:02:59,000 --> 00:03:01,000 자신의 올바른 위치에 정렬 할 수 있습니다. 61 00:03:01,000 --> 00:03:02,280 당신은 자신이보고 싶다면 62 00:03:02,280 --> 00:03:05,500 우리는 완전히 거꾸로 목록 [9, 6, 5, 3, 2]에 시도해 볼 수 있습니다. 63 00:03:05,500 --> 00:03:08,220 전체 목록을 원 패스 후, 64 00:03:08,220 --> 00:03:09,220 [글의 소리] 65 00:03:09,220 --> 00:03:18,790 [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] 66 00:03:18,790 --> 00:03:21,250 가장 오른쪽 엘리먼트 9의 적절한 위치에 있습니다. 67 00:03:21,250 --> 00:03:24,760 통과 번째 후, 6 '부풀어 오른 업'해야합니다 68 00:03:24,760 --> 00:03:26,220 둘째 가장 오른쪽 위치. 69 00:03:26,220 --> 00:03:28,840 6 9 - - 오른쪽에있는 두 가지 요소는 올바른 장소에있을 것입니다 70 00:03:28,840 --> 00:03:30,580 처음 두 패스 - throughs 후. 71 00:03:30,580 --> 00:03:32,590 >> 그래, 어떻게 우리는 알고리즘을 최적화시킬 수 있습니다? 72 00:03:32,590 --> 00:03:34,850 음, 배열을 관통 반복 한 후 73 00:03:34,850 --> 00:03:37,690 우리는 실제로 가장 오른쪽 요소를 확인 할 필요가 없습니다 74 00:03:37,690 --> 00:03:39,200 우리가 알고 있기 때문에이 정렬있어. 75 00:03:39,200 --> 00:03:43,050 이 반복되면, 우리는 가장 오른쪽 두 가지 요소는 위치에 있는지에 대해 알아. 76 00:03:43,050 --> 00:03:48,260 그래서, 일반적으로, 전체 배열을 통해 K 반복 후, 77 00:03:48,260 --> 00:03:51,550 우리가 알고 있기 때문에 마지막 K 요소를 확인하는 것은 중복이다 78 00:03:51,550 --> 00:03:52,360 그들은 이미 올바른 위치에있어. 79 00:03:52,360 --> 00:03:54,870 >> 당신이 N 요소의 배열을 정렬하는하면, 80 00:03:54,870 --> 00:03:57,870 첫 번째 반복에서 - 테고 모든 요소를​​ 정렬해야 - 첫 번째 N-0. 81 00:03:57,870 --> 00:04:04,170 두 번째 반복에서는 요소의 모든하지만 마지막 살펴해야합니다 - 82 00:04:04,170 --> 00:04:07,090 N-1 첫 번째. 83 00:04:07,090 --> 00:04:10,520 또 다른 최적화 목록이 이미 정렬되어 있는지 확인하는 것입니다 84 00:04:10,520 --> 00:04:11,710 각 반복 후. 85 00:04:11,710 --> 00:04:13,900 이미 정렬되어있는 경우, 우리는 더 이상 반복을 할 필요가 없습니다 86 00:04:13,900 --> 00:04:15,310 목록을. 87 00:04:15,310 --> 00:04:16,220 우리가 어떻게이 작업을 수행 할 수 있습니까? 88 00:04:16,220 --> 00:04:19,360 음, 우리는 목록의 통과에 어떤 스왑하지 않는 경우, 89 00:04:19,360 --> 00:04:22,350 우리가 아무것도 교환하지 않았기 때문에이 목록은 이미 정렬 된 것을 분명하다. 90 00:04:22,350 --> 00:04:24,160 그래서 우리는 확실히 다시 정렬 할 필요가 없습니다. 91 00:04:24,160 --> 00:04:27,960 >> 아마도 당신은에 '정렬되지'라는 플래그 변수를 초기화 할 수 92 00:04:27,960 --> 00:04:30,990 당신은에 어떤 요소를 교환해야하는 경우 false로하고 진실한로 변경 93 00:04:30,990 --> 00:04:32,290 배열을 관통 반복. 94 00:04:32,290 --> 00:04:35,350 또는 이와 유사한, 당신 말은 얼마나 많은 스왑 계산하기 위해 카운터를 95 00:04:35,350 --> 00:04:37,040 특정 반복 있습니다. 96 00:04:37,040 --> 00:04:40,040 반복의 끝에서, 당신이 요소를 교환하지 않은 경우는, 97 00:04:40,040 --> 00:04:41,780 당신은 목록이 이미 정렬하면 모든 작업이 완료됩니다 알아요. 98 00:04:41,780 --> 00:04:44,090 버블 정렬은 다른 정렬 알고리즘처럼 될 수 있습니다 99 00:04:44,090 --> 00:04:46,960 주문 방법을 가지고있는 요소에 대한 작업 불통. 100 00:04:46,960 --> 00:04:50,610 >> 그런 말 할 수있는 방법이 두 가지 요소에게 주어진 경우 첫 번째 101 00:04:50,610 --> 00:04:53,770 같거나 두 번째보다,보다 큽니다. 102 00:04:53,770 --> 00:04:56,870 예를 들어, 말하여 알파벳 문자를 정렬 할 수 103 00:04:56,870 --> 00:05:00,520 00:05:03,830 일요일 월요일 미만 곳 또는 요일을 정렬 할 수 105 00:05:03,830 --> 00:05:05,110 어느 화요일 미만의 거리에 있습니다. 106 00:05:05,110 --> 00:05:09,630 >> 더는 매우 효율적인 또는 빠른 정렬 알고리즘을 의미하여 버블 정렬이되지 않습니다. 107 00:05:09,630 --> 00:05:12,370 의 최악의 런타임 n의 빅 O입니다 ² 108 00:05:12,370 --> 00:05:14,810 당신은 목록을 N 반복을해야하기 때문에 109 00:05:14,810 --> 00:05:18,430 각 통과 모든 N 요소를 확인, nxn = N ². 110 00:05:18,430 --> 00:05:22,730 이 실행 시간은 원소의 개수로는 증가를 정렬하는 것을 의미합니다 111 00:05:22,730 --> 00:05:24,330 실행 시간은 quadratically 증가합니다. 112 00:05:24,330 --> 00:05:27,330 >> 그러나 효율이 프로그램의 주요 관심사가 아닌 경우 113 00:05:27,330 --> 00:05:29,550 또는 유일한 요소의 작은 숫자를 정렬하는 경우, 114 00:05:29,550 --> 00:05:31,660 당신은 버블 정렬 유용한 이유 115 00:05:31,660 --> 00:05:33,360 그것은 이해하는 가장 간단한 정렬 알고리즘 중 하나 116 00:05:33,360 --> 00:05:34,250 및 코드입니다. 117 00:05:34,250 --> 00:05:37,270 또한 이론적 번역 경험을 얻을 수있는 좋은 방법입니다 118 00:05:37,270 --> 00:05:40,220 실제 작동 코드로 알고리즘입니다. 119 00:05:40,220 --> 00:05:43,000 그게 당신을위한 버블 정렬입니다. 시청 해 주​​셔서 감사합니다. 120 00:05:43,000 --> 00:05:44,000 CS50.TV