[Powered by Google Translate] 토미 :가 선택 정렬 살펴, 알고리즘을하게하라
번호 목록을 복용하고 정렬하십시오.
알고리즘, 기억은 단순히 단계별로입니다
작업을 달성하기위한 절차.
선택 정렬 뒤에 기본적인 아이디어는 나눌 것입니다
이 부분에 목록 -
정렬 부분과 정렬되지 않은 부분입니다.
알고리즘의 각 단계에서 번호가에서 이동
결국 때까지 정렬 부분에 정렬되지 않은 부분
전체 목록이 정렬됩니다.
그럼 여기에 여섯 전화 번호가 있어요 -
23, 42, 4, 16, 8, 15.
지금 전체 목록이 정렬되지 않은 것으로 간주됩니다.
16 같은 숫자는 이미 올바른에있을 수 있습니다하더라도
위치, 우리의 알고리즘은 때까지를 알 수있는 방법이 없습니다
전체 목록이 정렬됩니다.
우리가 정렬 될 때까지 그래서 우리는 정렬되지 않은 것으로 모든 숫자를 고려됩니다
그 자신.
우리는 목록 오름차순으로 할 원하는 알아요.
그래서 우리는 우리의 목록의 정렬 부분을 구성 할 것
왼쪽에서 오른쪽으로, 가장 큰 to 작은.
이를 위해 우리는 최소한의 정렬되지 않은 요소를 찾아야합니다
과 정렬 부분의 끝 부분에 넣어.
이 목록은 정렬되지 않기 때문에, 할 수있는 유일한 방법은 다음과 같습니다
기억, 정렬되지 않은 부분에 각 요소 살펴
요소는 최저과 비교입니다
거기에 각 요소.
그럼 우리가 23 보겠습니다.
이것은 우리가 본 첫 번째 요소입니다, 그래서 우리는 기억합니다
최소로 그.
다음 우리는 42 보겠습니다.
42 23보다 큰, 그래서 23 여전히 최소입니다.
다음은 23보다 작음 4, 그래서 우리는 4 기억합니다
새로운 최소 있습니다.
다음 그래서 4, 4보다 큰 16
아직 최소입니다.
8 4보다 큰이며, 15 4보다 큰, 4해야만
작은 정렬되지 않은 요소입니다.
그래서, 비록 인간으로 우리는 즉시 4임을 알 수 있습니다
최소 요소는 우리의 알고리즘은보고 할 필요가
우리는 4을 발견 한 후에도 모든 정렬되지 않은 요소 -
최소 요소입니다.
그래서 지금 우리가 최소한의 요소 4를 발견 한, 우리가 원하는 것
목록의 정렬 부분에 이동합니다.
이 첫 번째 단계이기 때문에, 우리가에 4 넣었 으면 좋겠어 의미
목록의 시작.
지금 23 때문에, 목록의 시작 부분에 있습니다
의는 4 23 교환 보자.
이제 목록은 다음과 같습니다.
이 때문에 우리는 4 최종 위치에 있어야합니다 알고
처음에 가장 작은 요소와 요소를 모두
목록의.
우리가 다시 이동 할 필요가 없다는 의미는 그럼.
그러니에 다른 요소를 추가 할이 과정을 반복하게
목록의 정렬 부분입니다.
그 때문에 우리는 우리가 4 볼 필요가 전혀 없다는 것을 알고
이미 정렬.
그래서 우리는 우리가로 기억됩니다있는 42에서 시작할 수 있습니다
최소 요소입니다.
그래서 다음에 우리는 42보다 작음 23를보세요, 정말 드리겠습니다
23 새 최소 기억 해요.
다음 우리는 그렇게 미만 23 16를 참조
16 새 최소입니다.
이제 우리는, 그래서보다 16 8 볼
8 새로운 최소입니다.
그리고 마지막으로 8 미만 15, 그래서 우리는 8 최소 알고
정렬되지 않은 요소입니다.
그럼 우리가 정렬 8를 추가해야 함을 의미합니다
목록의 부분입니다.
지금 4 만 정렬 요소입니다, 그래서 우리는 배치하려는
4 8 옆에 있습니다.
42 이후의 정렬되지 않은 부분의 첫 번째 요소입니다
목록, 우리는 42 8을 교환하는 것이 좋습니다.
이제 목록은 다음과 같습니다.
4 8 목록의 정렬 부분을 대표하고,
나머지 숫자는 정렬되지 않은를 나타냅니다
목록의 부분입니다.
그럼 다른 반복을 계속 보자.
우리가 볼 필요가 없기 때문에 우리는 23와 함께 시작 시간
4 이상 8가 없기 때문에
이미 정렬 된.
16 미만 23, 그래서 우리는 기억합니다
새로운 최소로 16.
15해야하므로, 16 미만 42 만 15 미만 16입니다
최소 정렬되지 않은 요소입니다.
그래서 지금 우리는 15 23로 교환하려면
우리에게이 목록을 제공합니다.
목록의 정렬 부분은 4, 8, 15로 구성되어 있으며,
이러한 요소는 여전히 정렬되지 않은 수 있습니다.
그러나 우연히도 그 다음 정렬되지 않은 요소, 16,
이미 정렬됩니다.
그러나, 알고 우리의 알고리즘에 대한 방법이 없습니다 그 16
이미 올바른 위치에, 우리는 여전히 필요
정확히 같은 과정을 반복합니다.
그래서 이렇게, 우리는 16 이하 42 알, 16 미만 23
16의 최소 요소 여야합니다.
그것은 그 자체로이 요소를 교환하는 것은 불가능이야, 우리가 할 수 있도록
단순히이 위치에 두십시오.
그래서 우리는 우리의 알고리즘 중 하나를 더 패스가 필요합니다.
42 23보다 큰, 그래서 23이어야합니다
최소 정렬되지 않은 요소입니다.
일단 우리가 우리의 마지막이 생깁니다, 23 42 교환
정렬 목록 -
4, 8, 15, 16, 23, 42.
우리는 이니까 42 올바른 위치에 있어야합니다 알고
단 요소는 왼쪽으로, 그리고 그 선택 정렬입니다.
자, 이제 일부의 알고리즘을 공식화
의사.
라인에, 우리는 이상을 통합하는 데 필요한 것을 알 수 있습니다
목록의 모든 요소입니다.
마지막 요소를 제외하고, 이후 한 요소
목록이 이미 정렬됩니다.
2 번 라인에서, 우리는 정렬되지 않은 첫 번째 요소를 고려
우리는 우리와 함께했던 목록의 부분은 최소 할 수
예, 우리는 비교 할 일이 있습니다.
선 셋은 우리가 이상 반복되는 두 번째 루프를 시작
각 정렬되지 않은 요소입니다.
우리가 알고 내가 반복 한 후, 정렬 부분
목록의 각 단계부터 그 안에 내가 요소가 있어야합니다
정렬 한 요소.
따라서 첫 번째 정렬되지 않은 요소는 위치에 내가 플러스 1에 있어야합니다.
4 번에, 우리는 최소한으로 현재 요소를 비교
우리가 지금까지 본 적이 있다고 요소입니다.
현재 요소는 최소보다 작 으면
요소는, 우리는 새로운로 현재 요소를 기억
5 번 라인에서 최소.
마지막으로, 선 6-7에, 우리는 최소 교환
따라서 첫 번째 정렬되지 않은 요소와 요소,
목록의 정렬 부분에 추가.
우리가 알고리즘을 가지고되면, 중요한 질문은 물어
우리는 프로그래머로서 그 얼마나 걸릴 아세요?
우리는 먼저 질문을 드리겠습니다 얼마나이 순간을 위해 걸리나요
알고리즘은 최악의 경우에 실행?
우리는이 실행을 나타냅니다 기억
큰 O 표기법으로 시간을.
최소 정렬되지 않은 요소를 결정하기 위해, 우리는
기본적으로 목록의 각 요소를 비교했다
목록에있는 다른 모든 요소입니다.
직관적으로, 만약에 n 제곱 연산의 O처럼 소리.
우리의 의사를 살펴보면, 우리는 또한 내부에 중첩 루프를 가지고
O와 같은 실제로 소리가 다른 루프,
N 제곱 운영.
그러나, 우리가 살펴보고 필요하지 않은 기억
최소 정렬되지 않은 요소를 결정하는 전체 목록?
우리가 4 정렬 된 것을 알고되면, 예를 들어, 우리가 아니라,
다시 한번해야합니다.
이 실행 시간도 마찬가지 낮은합니까?
길이 6의 목록을 보려면, 우리는 다섯을 만드는 데 필요한
첫 번째 요소에 대한 비교, 네 번 비교
두 번째 요소 등.
그 단계의 총 수가의 합을 의미합니다
1 목록 마이너스 1의 길이 정수.
우리는 합류로이를 대표 할 수 있습니다.
우리는 여기 summations로 이동하지 않습니다.
그러나이 합류가 n 번과 동일하다고 판명
N 마이너스 2 이상 1.
또는 equivalently, 만약에 n이 넘는 마이너스 N 2를 통해 제곱.
점근 런타임에 대해 얘기,이 N 제곱 용어
이 N 용어를 지배 할 것이다.
그래서 선택 정렬은 N 제곱의 O입니다.
우리 예제에서, 선택 정렬 여전히 필요하다고 기억
선택하면 이미 정렬 된 번호
이동이 필요합니다.
말하자면 우리가 이미를 통해 선택 정렬을 실행하는 경우
목록 정렬, 그것은과 같은 단계의 동일한 번호를 요구
완전히 정렬되지 않은 목록을 통해 실행시 겠지.
그래서 선택 정렬은 제곱 n의 최고의 사례 성능을
있는 우리는 오메가 N 제곱을 나타냅니다.
그리고 그 선택 정렬을 위해 있습니다.
우리가 할 수있는 많은 알고리즘 중 하나
목록을 정렬하려면 사용합니다.
내 이름은 토미이고,이 cs50입니다.