[음악 재생] DOUG 로이드 : 선택 종류입니다 예상대로, 알고리즘, 요소들의 세트를 정렬한다. 그리고 알고리즘 리콜 단계별 집합이다 작업을 완료하기위한 지침. 

선택에서를 정렬 기본적인 아이디어는 이것이다 정렬되지 않은 작은 요소를 찾아 정렬 된리스트의 마지막에 추가합니다. 효과적으로이 무엇 빌드입니다 정렬 된 목록, 한번에 한 소자. 의사로 분해 우리는이 알고리즘을 진술 할 수 다음과 같이 될 때까지이 작업을 반복 더 정렬되지 않은 요소가 남아 있지. 정렬되지 않은 통해 검색 데이터는 작은 값을 찾을 수 있습니다, 그 다음으로 작은 값을 바꿀 정렬되지 않은 부분의 첫 번째 요소. 

그것은이를 시각화하는 데 도움이 될 수 있습니다 그래서이 살펴 보자. 그래서, 내가 주장,이다 정렬되지 않은 배열과 나는했습니다 모든 것을 나타내는하여 표시된 요소, 빨간색으로 그들은 아직 정렬되지 않습니다. 이것은 전체 인 배열의 정렬되지 않은 부분. 

그럼의 단계를 통해 가자 선택 정렬이 배열을 정렬합니다. 그래서 다시, 우리는 거 반복이야 더 정렬되지 않은 요소가 남아 있지 않을 때까지. 우리는 통해 거 검색이야 데이터는 작은 값을 찾을 수 있습니다, 다음으로, 그 값을 교환 정렬되지 않은 부분의 첫 번째 요소. 

지금, 다시 전체 배열은 정렬되지 않은 부분입니다. 붉은 모든 요소가 정렬되지 않은 있습니다. 그래서 우리는을 통해 검색 우리는 작은 값을 찾을 수 있습니다. 우리는 처음부터 시작 우리는, 끝으로 이동 우리는 가장 작은 값이 하나 찾을 수 있습니다. 그래서 그 부분 하나입니다. 그리고 두 번째 부분은,와 그 값을 교체 정렬되지 않은 부분의 제 요소, 또는 제 1 빨간색 요소. 

이 경우이 될 것이라고 다섯, 그래서 우리는 한 다섯 교환합니다. 우리는이 작업을 수행 할 때, 우리는 할 수 시각적으로 우리가했다고 볼 가장 작은 값의 요소를 이동 배열의 맨 처음에. 효과적으로 그 요소를 정렬. 

그래서 우리는 참으로 확인할 수 있습니다 및 주 한 것으로, 정렬됩니다. 그래서 우리는 정렬 된 부분을 표시합니다 우리의 배열, 그것은 파란색 색소에 의해. 

이제 우리는 단지 과정을 다시 반복합니다. 우리의 정렬되지 않은 부분을 검색 배열은 가장 작은 요소를 찾을 수 있습니다. 이 경우, 2의. 

우리는 첫 번째와 것을 교환 정렬되지 않은 부분의 요소입니다. 이 경우 두도 될 일이 정렬되지 않은 부분의 첫 번째 요소입니다. 그래서 우리는 자체 두를 교환, 이는 정말 두 잎 그것은이며, 그것은 정렬 어디. 에 계속, 우리는을 통해 검색 작은 요소를 찾을 수 있습니다. 그것은 세 가지입니다. 우리는 첫 번째로 스왑 다섯 요소입니다. 그리고 지금 세 가지가 정렬됩니다. 

우리는 다시 통해 검색, 그리고 우리 가장 작은 요소가 네입니다 찾을 수 있습니다. 우리의 첫번째 요소로 교체 정렬되지 않은 부분, 지금은 네가 정렬됩니다. 

우리는 다섯입니다 찾기 가장 작은 요소입니다. 우리는 첫 번째로 스왑 정렬되지 않은 부분의 요소입니다. 이제 다섯이 정렬됩니다. 

그리고 마지막으로, 우리의 정렬되지 않은 부분으로 구성 단지 하나의 요소, 그래서 우리는을 통해 검색 우리는 여섯 것을 발견 작고, 실제로, 유일한 요소. 그리고 우리는 정렬 것을 주장 할 수 있습니다. 그리고 지금 우리는 우리의 배열을 전환했습니다 완전히 정렬되지 않은되는 빨간색으로, 완전하게 분류하는 파란색, 선택 정렬을 사용. 

따라서 최악의 경우는 여기에 무엇입니까? 그럼 절대 최악의 경우, 우리는 이상 볼 필요가 어레이의 모든 요소 중 최소 정렬되지 않은 요소를 발견, 우리는 반복해야 이 과정을 n 번. 배열의 각 요소에 대해 한 번 우리 만 있기 때문에,이 알고리즘에서, 한 번에 정렬 한 요소입니다. 

최선의 시나리오는 무엇입니까? 잘 그것은 바로, 정확히 같은입니까? 우리는 실제로 여전히 단계별로해야 배열의 모든 단일 요소 위해서는임을 확인 사실, 작은 소자. 

따라서 최악의 경우 런타임, 우리 과정을 n 번을 반복해야, N 개의 요소들 각각에 대해 한 번. 그리고 최선의 시나리오에서, 우리는 동일한 작업을 수행해야합니다. 

그래서 다시 생각하는 우리의 계산 복잡도 도구 상자, 당신이 생각하는 최악 선택 정렬을위한 경우 런타임? 당신이 생각하는 최고입니다 선택 정렬을위한 경우 런타임? 

n은 제곱의 당신은 큰 O를 생각나요, 빅 오메가 N의 제곱? 당신은 잘 될 것입니다. 들이다 사실, 최악의 경우와 최상의 경우 실행 선택 정렬을위한 시간. 

나는 더그 로이드입니다. 이 CS50입니다.