>> [음악 재생]
DOUG 로이드 : 선택 종류입니다 예상대로, 알고리즘,
요소들의 세트를 정렬한다.
그리고 알고리즘 리콜 단계별 집합이다
작업을 완료하기위한 지침.
>> 선택에서를 정렬 기본적인 아이디어는 이것이다
정렬되지 않은 작은 요소를 찾아 정렬 된리스트의 마지막에 추가합니다.
효과적으로이 무엇 빌드입니다 정렬 된 목록, 한번에 한 소자.
의사로 분해 우리는이 알고리즘을 진술 할 수
다음과 같이 될 때까지이 작업을 반복 더 정렬되지 않은 요소가 남아 있지.
정렬되지 않은 통해 검색 데이터는 작은 값을 찾을 수 있습니다,
그 다음으로 작은 값을 바꿀 정렬되지 않은 부분의 첫 번째 요소.
>> 그것은이를 시각화하는 데 도움이 될 수 있습니다 그래서이 살펴 보자.
그래서, 내가 주장,이다 정렬되지 않은 배열과 나는했습니다
모든 것을 나타내는하여 표시된 요소, 빨간색으로
그들은 아직 정렬되지 않습니다.
이것은 전체 인 배열의 정렬되지 않은 부분.
>> 그럼의 단계를 통해 가자 선택 정렬이 배열을 정렬합니다.
그래서 다시, 우리는 거 반복이야 더 정렬되지 않은 요소가 남아 있지 않을 때까지.
우리는 통해 거 검색이야 데이터는 작은 값을 찾을 수 있습니다,
다음으로, 그 값을 교환 정렬되지 않은 부분의 첫 번째 요소.
>> 지금, 다시 전체 배열은 정렬되지 않은 부분입니다.
붉은 모든 요소가 정렬되지 않은 있습니다.
그래서 우리는을 통해 검색 우리는 작은 값을 찾을 수 있습니다.
우리는 처음부터 시작 우리는, 끝으로 이동
우리는 가장 작은 값이 하나 찾을 수 있습니다.
그래서 그 부분 하나입니다.
그리고 두 번째 부분은,와 그 값을 교체 정렬되지 않은 부분의 제 요소,
또는 제 1 빨간색 요소.
>> 이 경우이 될 것이라고 다섯, 그래서 우리는 한 다섯 교환합니다.
우리는이 작업을 수행 할 때, 우리는 할 수 시각적으로 우리가했다고 볼
가장 작은 값의 요소를 이동 배열의 맨 처음에.
효과적으로 그 요소를 정렬.
>> 그래서 우리는 참으로 확인할 수 있습니다 및 주 한 것으로, 정렬됩니다.
그래서 우리는 정렬 된 부분을 표시합니다 우리의 배열, 그것은 파란색 색소에 의해.
>> 이제 우리는 단지 과정을 다시 반복합니다.
우리의 정렬되지 않은 부분을 검색 배열은 가장 작은 요소를 찾을 수 있습니다.
이 경우, 2의.
>> 우리는 첫 번째와 것을 교환 정렬되지 않은 부분의 요소입니다.
이 경우 두도 될 일이 정렬되지 않은 부분의 첫 번째 요소입니다.
그래서 우리는 자체 두를 교환, 이는 정말 두 잎
그것은이며, 그것은 정렬 어디.
에 계속, 우리는을 통해 검색 작은 요소를 찾을 수 있습니다.
그것은 세 가지입니다.
우리는 첫 번째로 스왑 다섯 요소입니다.
그리고 지금 세 가지가 정렬됩니다.
>> 우리는 다시 통해 검색, 그리고 우리 가장 작은 요소가 네입니다 찾을 수 있습니다.
우리의 첫번째 요소로 교체 정렬되지 않은 부분, 지금은 네가 정렬됩니다.
>> 우리는 다섯입니다 찾기 가장 작은 요소입니다.
우리는 첫 번째로 스왑 정렬되지 않은 부분의 요소입니다.
이제 다섯이 정렬됩니다.
>> 그리고 마지막으로, 우리의 정렬되지 않은 부분으로 구성
단지 하나의 요소, 그래서 우리는을 통해 검색
우리는 여섯 것을 발견 작고, 실제로, 유일한 요소.
그리고 우리는 정렬 것을 주장 할 수 있습니다.
그리고 지금 우리는 우리의 배열을 전환했습니다 완전히 정렬되지 않은되는
빨간색으로, 완전하게 분류하는 파란색, 선택 정렬을 사용.
>> 따라서 최악의 경우는 여기에 무엇입니까?
그럼 절대 최악의 경우, 우리는 이상 볼 필요가
어레이의 모든 요소 중 최소 정렬되지 않은 요소를 발견,
우리는 반복해야 이 과정을 n 번.
배열의 각 요소에 대해 한 번 우리 만 있기 때문에,이 알고리즘에서,
한 번에 정렬 한 요소입니다.
>> 최선의 시나리오는 무엇입니까?
잘 그것은 바로, 정확히 같은입니까?
우리는 실제로 여전히 단계별로해야 배열의 모든 단일 요소
위해서는임을 확인 사실, 작은 소자.
>> 따라서 최악의 경우 런타임, 우리 과정을 n 번을 반복해야,
N 개의 요소들 각각에 대해 한 번.
그리고 최선의 시나리오에서, 우리는 동일한 작업을 수행해야합니다.
>> 그래서 다시 생각하는 우리의 계산 복잡도 도구 상자,
당신이 생각하는 최악 선택 정렬을위한 경우 런타임?
당신이 생각하는 최고입니다 선택 정렬을위한 경우 런타임?
>> n은 제곱의 당신은 큰 O를 생각나요, 빅 오메가 N의 제곱?
당신은 잘 될 것입니다.
들이다 사실, 최악의 경우와 최상의 경우 실행
선택 정렬을위한 시간.
>> 나는 더그 로이드입니다.
이 CS50입니다.