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

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: ასე რომ Insertion დალაგების არის სხვა
ალგორითმი ჩვენ შეგვიძლია გამოვიყენოთ დასალაგებლად მასივი.

4
00:00:09,370 --> 00:00:12,350
იდეა უკან ამ ალგორითმი
ავაშენოთ თქვენი დახარისხებული მასივი

5
00:00:12,350 --> 00:00:19,670
ადგილი, გადასვლის ელემენტები გარეთ
ისე, როგორც თქვენ გადასვლა, რათა ოთახში.

6
00:00:19,670 --> 00:00:22,240
ეს არის ოდნავ განსხვავებული
საწყისი შერჩევის დალაგების ან ბუშტი

7
00:00:22,240 --> 00:00:25,460
დალაგების, მაგალითად, სადაც
ჩვენ მორგება ადგილას,

8
00:00:25,460 --> 00:00:26,910
სადაც ჩვენ მიღების გაცვლებს.

9
00:00:26,910 --> 00:00:29,760
>> ამ შემთხვევაში, რაც ჩვენ, ფაქტობრივად,
ამით არის მოცურების ელემენტები

10
00:00:29,760 --> 00:00:31,390
მეტი, იმ გზას.

11
00:00:31,390 --> 00:00:34,030
როგორ აკეთებს ამას ალგორითმი
მუშაობა pseudocode?

12
00:00:34,030 --> 00:00:37,646
ისე მოდით უბრალოდ თვითნებურად ამბობენ, რომ
პირველი ელემენტია მასივი დალაგებულია.

13
00:00:37,646 --> 00:00:38,770
ჩვენ ვაშენებთ ეს ადგილი.

14
00:00:38,770 --> 00:00:42,660
>> ჩვენ კარგად წასვლა ერთ-ერთი ელემენტია დროს და
აშენება, და ამიტომ პირველი, რაც ჩვენ ვხედავთ,

15
00:00:42,660 --> 00:00:43,890
არის ერთ-ერთი ელემენტია მასივი.

16
00:00:43,890 --> 00:00:47,720
და ზოგადად, ერთი
ელემენტს მასივი დალაგებულია.

17
00:00:47,720 --> 00:00:50,850
>> მაშინ ჩვენ ვიმეორებ ეს პროცესი until--
ჩვენ გავიმეორო შემდეგ პროცესი

18
00:00:50,850 --> 00:00:52,900
სანამ ყველა ელემენტები დალაგებულია.

19
00:00:52,900 --> 00:00:57,770
შეხედეთ შემდეგი არასორტირებული ელემენტს და
ჩადეთ იგი დახარისხებული ნაწილი,

20
00:00:57,770 --> 00:01:01,209
გადასვლის საჭირო რაოდენობის
ელემენტების გარეთ გზა.

21
00:01:01,209 --> 00:01:03,750
იმედია ეს ვიზუალიზაცია
დაეხმარება ხედავთ ზუსტად რა

22
00:01:03,750 --> 00:01:05,980
ხდება Insertion დალაგების.

23
00:01:05,980 --> 00:01:08,010
>> ასე რომ კიდევ ერთხელ, აქ არის ჩვენი
მთელი დაუხარისხებელი მასივი,

24
00:01:08,010 --> 00:01:10,970
ყველა ელემენტები მითითებული წითელი.

25
00:01:10,970 --> 00:01:13,320
და მოდით დაიცვას
ნაბიჯები ჩვენი pseudocode.

26
00:01:13,320 --> 00:01:16,970
პირველი, რაც უნდა გავაკეთოთ, არის მოვუწოდებთ
პირველი ელემენტია მასივი, დახარისხებული.

27
00:01:16,970 --> 00:01:20,920
ასე რომ, ჩვენ უბრალოდ კარგად ვთქვათ
ხუთი, თქვენ გადანაწილებული.

28
00:01:20,920 --> 00:01:24,570
>> მაშინ ჩვენ შევხედოთ შემდეგი
დაუხარისხებელი ელემენტს მასივი

29
00:01:24,570 --> 00:01:27,610
და ჩვენ გვინდა ჩადეთ რომ
შევიდა დახარისხებული ნაწილი,

30
00:01:27,610 --> 00:01:29,750
გადასვლის ელემენტები დასრულდა.

31
00:01:29,750 --> 00:01:33,470
ასე რომ, ორი არის შემდეგი დაუხარისხებელი
ელემენტს მასივი.

32
00:01:33,470 --> 00:01:36,250
ცხადია, რომ ეს ეკუთვნის წინაშე
ხუთ, ასე რომ, რასაც ჩვენ ვაპირებთ გავაკეთოთ

33
00:01:36,250 --> 00:01:41,580
არის ერთგვარი გამართავს ორი გათვალისწინებულია მეორე,
გადაიტანოს ხუთ მეტი და შემდეგ ჩადეთ ორი

34
00:01:41,580 --> 00:01:43,210
ადრე ხუთ, სადაც უნდა წავიდეს.

35
00:01:43,210 --> 00:01:45,280
და ახლა ჩვენ შეგვიძლია ვთქვათ, რომ ორი დალაგებულია.

36
00:01:45,280 --> 00:01:48,400
>> ასე რომ, როგორც ხედავთ, ჩვენ მხოლოდ იმდენად, რამდენადაც
შევხედე ორი ელემენტები მასივი.

37
00:01:48,400 --> 00:01:50,600
ჩვენ არ შევხედე
დაისვენოს, მაგრამ ჩვენ

38
00:01:50,600 --> 00:01:54,582
მივიღე ამ ორ ელემენტს დალაგებულია
გზა გადასვლის მექანიზმი.

39
00:01:54,582 --> 00:01:56,410
>> ასე რომ, ჩვენ ვიმეორებ, ეს პროცესი კიდევ ერთხელ.

40
00:01:56,410 --> 00:01:58,850
შეხედეთ შემდეგი დაუხარისხებელი
ელემენტს, რომ ერთი.

41
00:01:58,850 --> 00:02:04,010
მოდით გამართავს, რომ გათვალისწინებულია მეორე,
გადაიტანოს ყველაფერი დასრულდა, და დააყენა ერთი

42
00:02:04,010 --> 00:02:05,570
სადაც ის უნდა წავიდეს.

43
00:02:05,570 --> 00:02:08,110
>> ისევ და ისევ, ისევ, ჩვენ მხოლოდ ოდესმე
შევხედე ერთი, ორი, და ხუთი.

44
00:02:08,110 --> 00:02:12,480
ჩვენ არ ვიცით, რა მოდის,
მაგრამ ჩვენ გადანაწილებული ის სამი ელემენტები.

45
00:02:12,480 --> 00:02:16,030
>> შემდეგი არასორტირებული ელემენტს არის
სამი, ასე რომ ჩვენ მითითებული ეს განზე.

46
00:02:16,030 --> 00:02:18,200
ჩვენ გადაიტანოს, რაც ჩვენ
უნდა, რომელიც ამ დროს

47
00:02:18,200 --> 00:02:21,820
არ არის ყველაფერი, როგორც წინა
ორ შემთხვევაში, უბრალოდ ხუთ.

48
00:02:21,820 --> 00:02:25,440
და მაშინ ჩვენ გამყარებაში სამი,
ორ და ხუთ.

49
00:02:25,440 --> 00:02:27,849
>> Six არის შემდეგი დაუხარისხებელი
ელემენტს მასივი.

50
00:02:27,849 --> 00:02:31,140
და სინამდვილეში ექვსი უფრო მეტია, ვიდრე ხუთი, ასე
ჩვენ კი არ გვჭირდება რაიმე შევცვალე.

51
00:02:31,140 --> 00:02:35,710
ჩვენ შეგვიძლია მხოლოდ დაყენება ექვსი უფლება,
ბოლოს დახარისხებული ნაწილი.

52
00:02:35,710 --> 00:02:38,270
>> და ბოლოს, ოთხი არის
ბოლო არასორტირებული ელემენტს.

53
00:02:38,270 --> 00:02:42,060
ასე რომ, ჩვენ ეს განზე, გადაიტანოს მეტი
ელემენტები ჩვენ უნდა გადაიტანოს მეტი,

54
00:02:42,060 --> 00:02:43,780
და შემდეგ დააყენა ოთხი სადაც მას ეკუთვნის.

55
00:02:43,780 --> 00:02:46,400
ახლა კი გამოიყურება, ჩვენ ერთგვარი
ყველა ელემენტები.

56
00:02:46,400 --> 00:02:48,150
გაითვალისწინეთ ერთად ჩასმა
დალაგების, ჩვენ არ გვაქვს

57
00:02:48,150 --> 00:02:50,240
წასვლა უკან და მეოთხე მასშტაბით მასივი.

58
00:02:50,240 --> 00:02:54,720
ჩვენ მხოლოდ წავიდა მთელს მასივი
ერთ დროს, და ჩვენ გადავიდა რამ

59
00:02:54,720 --> 00:02:59,870
რომ ჩვენ გვინდა უკვე შეექმნა, რათა
რათა ოთახში ახალი ელემენტები.

60
00:02:59,870 --> 00:03:02,820
>> ასე რომ, რა უარეს შემთხვევაში
სცენარი Insertion დალაგების?

61
00:03:02,820 --> 00:03:05,090
უარეს შემთხვევაში,
მასივი საპირისპირო მიზნით.

62
00:03:05,090 --> 00:03:11,180
თქვენ უნდა გადაიტანოს თითოეული N ელემენტები
მდე N პოზიციებზე, თითოეული დროს ჩვენ

63
00:03:11,180 --> 00:03:12,880
რათა ჩანართი.

64
00:03:12,880 --> 00:03:15,720
ეს არის ის, ბევრი გადავიდა.

65
00:03:15,720 --> 00:03:18,014
>> საუკეთესო შემთხვევაში,
მასივი შესანიშნავად გადანაწილებული.

66
00:03:18,014 --> 00:03:20,680
და ერთგვარი მოსწონს თუ რა მოხდა
ხუთ და ექვს მაგალითად,

67
00:03:20,680 --> 00:03:23,779
სადაც ჩვენ შეიძლება მხოლოდ Tack ეს
გარეშე რაიმე გადავიდა,

68
00:03:23,779 --> 00:03:24,820
ჩვენ გვინდა, არსებითად, რომ.

69
00:03:24,820 --> 00:03:27,560
>> თუ თქვენ წარმოიდგინეთ, რომ ჩვენი
array იყო ერთი გზით ექვსი,

70
00:03:27,560 --> 00:03:29,900
ჩვენ გვინდა დაიწყოს off
გამოცხადების ერთ დალაგებულია.

71
00:03:29,900 --> 00:03:33,300
ორი უძღოდა ერთი ასე რომ ჩვენ შეგვიძლია მხოლოდ
იტყვით, ასევე ერთი და ორი დახარისხებული.

72
00:03:33,300 --> 00:03:36,190
სამი უძღოდა ორი ისე, ბატონო,
ერთი და ორი და სამი გადანაწილებული.

73
00:03:36,190 --> 00:03:39,590
>> ჩვენ არ გაუკეთებია გაცვლებს, ჩვენ
მხოლოდ მოძრავი ამ თვითნებური ხაზი

74
00:03:39,590 --> 00:03:42,460
შორის გადანაწილებული და დაუხარისხებელი როგორც ჩვენ წავიდეთ.

75
00:03:42,460 --> 00:03:46,646
ეფექტურად როგორც ჩვენ გავაკეთეთ მაგალითად,
გარდამტეხი ელემენტები ლურჯი, როგორც ჩვენ გაგრძელება.

76
00:03:46,646 --> 00:03:48,270
ასე რომ, რა უარეს შემთხვევაში runtime, მაშინ?

77
00:03:48,270 --> 00:03:51,854
გახსოვდეთ, თუ ჩვენ უნდა გადაიტანოს თითოეული
ო ელემენტები შესაძლოა n პოზიციები,

78
00:03:51,854 --> 00:03:54,020
იმედია, რომელიც გაძლევთ
იდეა, რომ უარეს შემთხვევაში

79
00:03:54,020 --> 00:03:57,770
Runtime არის დიდი O of n კვადრატში.

80
00:03:57,770 --> 00:04:00,220
>> იმ შემთხვევაში, თუ მასივი მშვენივრად
დალაგებულია, ყველა ჩვენ უნდა გავაკეთოთ

81
00:04:00,220 --> 00:04:04,480
არის შევხედოთ თითოეული ელემენტი
ერთხელ, და მაშინ ჩვენ გავაკეთეთ.

82
00:04:04,480 --> 00:04:08,440
ასე რომ, საუკეთესო შემთხვევაში, ეს omega of ო.

83
00:04:08,440 --> 00:04:09,490
>> მე Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
ეს არის CS50.

85
00:04:11,760 --> 00:04:13,119