1
00:00:00,000 --> 00:00:05,726
>> [Грає музика]

2
00:00:05,726 --> 00:00:08,600
ДАГ Lloyd: Сортувати Вибір є
алгоритм, який, як ви могли б очікувати,

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
або перший елемент червоний.

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
У цьому випадку, це два.

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
і ми повинні повторити
цей процес п раз.

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
>> Таким чином, в гіршому разі виконання, ми
доведеться повторити процес п раз,

69
00:03:26,760 --> 00:03:28,960
один раз для кожного з п елементів.

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
>> Ви здогадалися Big O н квадрат,
і Великий Омега п квадраті?

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