1
00:00:00,000 --> 00:00:05,726
>> [მუსიკის დაკვრა]

2
00:00:05,726 --> 00:00:08,600
DOUG 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
ეფექტურად რა ეს არ არის build
დახარისხებული სია, ერთ-ერთი ელემენტია დროს.

9
00:00:26,970 --> 00:00:29,800
Breaking ის ქვემოთ pseudocode
ჩვენ შეგვიძლია განვაცხადოთ, ეს ალგორითმი

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
და ჩვენ უნდა გავიმეოროთ
ეს პროცესი 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
>> ასე რომ, უარეს შემთხვევაში runtime, ჩვენ
უნდა გავიმეოროთ პროცესის 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
როგორ ფიქრობთ რა არის ყველაზე ცუდი
შემთხვევაში runtime შერჩევის დალაგება?

73
00:03:39,250 --> 00:03:41,840
როგორ ფიქრობთ, რა არის საუკეთესო
შემთხვევაში runtime შერჩევის დალაგება?

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

75
00:03:44,760 --> 00:03:49,325
>> ხომ იცი, დიდი ო ო კვადრატი,
და დიდი ომეგა of 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
>> მე Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
ეს არის CS50.

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