1
00:00:00,000 --> 00:00:05,726
>> [음악 재생]

2
00:00:05,726 --> 00:00:08,600
DOUG 로이드 : 선택 종류입니다
예상대로, 알고리즘,

3
00:00:08,600 --> 00:00:10,470
요소들의 세트를 정렬한다.

4
00:00:10,470 --> 00:00:12,470
그리고 알고리즘 리콜
단계별 집합이다

5
00:00:12,470 --> 00:00:15,260
작업을 완료하기위한 지침.

6
00:00:15,260 --> 00:00:17,580
>> 선택에서를 정렬
기본적인 아이디어는 이것이다

7
00:00:17,580 --> 00:00:22,080
정렬되지 않은 작은 요소를 찾아
정렬 된리스트의 마지막에 추가합니다.

8
00:00:22,080 --> 00:00:26,970
효과적으로이 무엇 빌드입니다
정렬 된 목록, 한번에 한 소자.

9
00:00:26,970 --> 00:00:29,800
의사로 분해
우리는이 알고리즘을 진술 할 수

10
00:00:29,800 --> 00:00:34,490
다음과 같이 될 때까지이 작업을 반복
더 정렬되지 않은 요소가 남아 있지.

11
00:00:34,490 --> 00:00:38,660
정렬되지 않은 통해 검색
데이터는 작은 값을 찾을 수 있습니다,

12
00:00:38,660 --> 00:00:44,130
그 다음으로 작은 값을 바꿀
정렬되지 않은 부분의 첫 번째 요소.

13
00:00:44,130 --> 00:00:47,130
>> 그것은이를 시각화하는 데 도움이 될 수 있습니다
그래서이 살펴 보자.

14
00:00:47,130 --> 00:00:49,710
그래서, 내가 주장,이다
정렬되지 않은 배열과 나는했습니다

15
00:00:49,710 --> 00:00:53,040
모든 것을 나타내는하여 표시된
요소, 빨간색으로

16
00:00:53,040 --> 00:00:54,420
그들은 아직 정렬되지 않습니다.

17
00:00:54,420 --> 00:00:57,670
이것은 전체 인
배열의 정렬되지 않은 부분.

18
00:00:57,670 --> 00:01:02,020
>> 그럼의 단계를 통해 가자
선택 정렬이 배열을 정렬합니다.

19
00:01:02,020 --> 00:01:05,296
그래서 다시, 우리는 거 반복이야
더 정렬되지 않은 요소가 남아 있지 않을 때까지.

20
00:01:05,296 --> 00:01:07,920
우리는 통해 거 검색이야
데이터는 작은 값을 찾을 수 있습니다,

21
00:01:07,920 --> 00:01:11,990
다음으로, 그 값을 교환
정렬되지 않은 부분의 첫 번째 요소.

22
00:01:11,990 --> 00:01:14,380
>> 지금, 다시 전체
배열은 정렬되지 않은 부분입니다.

23
00:01:14,380 --> 00:01:16,534
붉은 모든 요소가 정렬되지 않은 있습니다.

24
00:01:16,534 --> 00:01:18,700
그래서 우리는을 통해 검색
우리는 작은 값을 찾을 수 있습니다.

25
00:01:18,700 --> 00:01:20,533
우리는 처음부터 시작
우리는, 끝으로 이동

26
00:01:20,533 --> 00:01:23,630
우리는 가장 작은 값이 하나 찾을 수 있습니다.

27
00:01:23,630 --> 00:01:24,860
그래서 그 부분 하나입니다.

28
00:01:24,860 --> 00:01:29,440
그리고 두 번째 부분은,와 그 값을 교체
정렬되지 않은 부분의 제 요소,

29
00:01:29,440 --> 00:01:31,340
또는 제 1 빨간색 요소.

30
00:01:31,340 --> 00:01:34,980
>> 이 경우이 될 것이라고
다섯, 그래서 우리는 한 다섯 교환합니다.

31
00:01:34,980 --> 00:01:37,320
우리는이 작업을 수행 할 때, 우리는 할 수
시각적으로 우리가했다고 볼

32
00:01:37,320 --> 00:01:41,260
가장 작은 값의 요소를 이동
배열의 맨 처음에.

33
00:01:41,260 --> 00:01:43,920
효과적으로 그 요소를 정렬.

34
00:01:43,920 --> 00:01:47,520
>> 그래서 우리는 참으로 확인할 수 있습니다
및 주 한 것으로, 정렬됩니다.

35
00:01:47,520 --> 00:01:52,080
그래서 우리는 정렬 된 부분을 표시합니다
우리의 배열, 그것은 파란색 색소에 의해.

36
00:01:52,080 --> 00:01:53,860
>> 이제 우리는 단지 과정을 다시 반복합니다.

37
00:01:53,860 --> 00:01:57,430
우리의 정렬되지 않은 부분을 검색
배열은 가장 작은 요소를 찾을 수 있습니다.

38
00:01:57,430 --> 00:01:59,000
이 경우, 2의.

39
00:01:59,000 --> 00:02:02,100
>> 우리는 첫 번째와 것을 교환
정렬되지 않은 부분의 요소입니다.

40
00:02:02,100 --> 00:02:05,540
이 경우 두도 될 일이
정렬되지 않은 부분의 첫 번째 요소입니다.

41
00:02:05,540 --> 00:02:08,650
그래서 우리는 자체 두를 교환,
이는 정말 두 잎

42
00:02:08,650 --> 00:02:11,257
그것은이며, 그것은 정렬 어디.

43
00:02:11,257 --> 00:02:13,840
에 계속, 우리는을 통해 검색
작은 요소를 찾을 수 있습니다.

44
00:02:13,840 --> 00:02:15,030
그것은 세 가지입니다.

45
00:02:15,030 --> 00:02:17,650
우리는 첫 번째로 스왑
다섯 요소입니다.

46
00:02:17,650 --> 00:02:19,450
그리고 지금 세 가지가 정렬됩니다.

47
00:02:19,450 --> 00:02:22,440
>> 우리는 다시 통해 검색, 그리고 우리
가장 작은 요소가 네입니다 찾을 수 있습니다.

48
00:02:22,440 --> 00:02:28,070
우리의 첫번째 요소로 교체
정렬되지 않은 부분, 지금은 네가 정렬됩니다.

49
00:02:28,070 --> 00:02:29,910
>> 우리는 다섯입니다 찾기
가장 작은 요소입니다.

50
00:02:29,910 --> 00:02:32,900
우리는 첫 번째로 스왑
정렬되지 않은 부분의 요소입니다.

51
00:02:32,900 --> 00:02:34,740
이제 다섯이 정렬됩니다.

52
00:02:34,740 --> 00:02:36,660
>> 그리고 마지막으로, 우리의
정렬되지 않은 부분으로 구성

53
00:02:36,660 --> 00:02:38,576
단지 하나의 요소,
그래서 우리는을 통해 검색

54
00:02:38,576 --> 00:02:41,740
우리는 여섯 것을 발견
작고, 실제로, 유일한 요소.

55
00:02:41,740 --> 00:02:44,906
그리고 우리는 정렬 것을 주장 할 수 있습니다.

56
00:02:44,906 --> 00:02:47,530
그리고 지금 우리는 우리의 배열을 전환했습니다
완전히 정렬되지 않은되는

57
00:02:47,530 --> 00:02:52,660
빨간색으로, 완전하게 분류하는
파란색, 선택 정렬을 사용.

58
00:02:52,660 --> 00:02:54,920
>> 따라서 최악의 경우는 여기에 무엇입니까?

59
00:02:54,920 --> 00:02:57,830
그럼 절대 최악의
경우, 우리는 이상 볼 필요가

60
00:02:57,830 --> 00:03:02,170
어레이의 모든 요소 중
최소 정렬되지 않은 요소를 발견,

61
00:03:02,170 --> 00:03:04,750
우리는 반복해야
이 과정을 n 번.

62
00:03:04,750 --> 00:03:09,090
배열의 각 요소에 대해 한 번
우리 만 있기 때문에,이 알고리즘에서,

63
00:03:09,090 --> 00:03:12,180
한 번에 정렬 한 요소입니다.

64
00:03:12,180 --> 00:03:13,595
>> 최선의 시나리오는 무엇입니까?

65
00:03:13,595 --> 00:03:15,040
잘 그것은 바로, 정확히 같은입니까?

66
00:03:15,040 --> 00:03:18,440
우리는 실제로 여전히 단계별로해야
배열의 모든 단일 요소

67
00:03:18,440 --> 00:03:22,040
위해서는임을 확인
사실, 작은 소자.

68
00:03:22,040 --> 00:03:26,760
>> 따라서 최악의 경우 런타임, 우리
과정을 n 번을 반복해야,

69
00:03:26,760 --> 00:03:28,960
N 개의 요소들 각각에 대해 한 번.

70
00:03:28,960 --> 00:03:31,940
그리고 최선의 시나리오에서,
우리는 동일한 작업을 수행해야합니다.

71
00:03:31,940 --> 00:03:35,340
>> 그래서 다시 생각하는 우리의
계산 복잡도 도구 상자,

72
00:03:35,340 --> 00:03:39,250
당신이 생각하는 최악
선택 정렬을위한 경우 런타임?

73
00:03:39,250 --> 00:03:41,840
당신이 생각하는 최고입니다
선택 정렬을위한 경우 런타임?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> n은 제곱의 당신은 큰 O를 생각나요,
빅 오메가 N의 제곱?

76
00:03:49,325 --> 00:03:49,950
당신은 잘 될 것입니다.

77
00:03:49,950 --> 00:03:52,490
들이다 사실,
최악의 경우와 최상의 경우 실행

78
00:03:52,490 --> 00:03:55,100
선택 정렬을위한 시간.

79
00:03:55,100 --> 00:03:56,260
>> 나는 더그 로이드입니다.

80
00:03:56,260 --> 00:03:58,600
이 CS50입니다.

81
00:03:58,600 --> 00:04:00,279