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: จัดเรียงแทรกดังนั้นเป็นอีกหนึ่ง
ขั้นตอนวิธีการที่เราสามารถใช้ในการจัดเรียงแถว

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
ที่เกิดขึ้นกับการจัดเรียงแทรก

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
และให้เป็นไปตาม
ขั้นตอนของรหัสจำลองของเรา

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
>> หกอยู่ถัดจากบ้านทั่วไป
องค์ประกอบอาร์เรย์

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
>> ดังนั้นสิ่งที่เป็นกรณีที่เลวร้ายที่สุด
สถานการณ์ที่มีการจัดเรียงแทรก?

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
ที่เราก็สามารถตรึงไว้บน
โดยไม่ต้องทำขยับใด ๆ

68
00:03:23,779 --> 00:03:24,820
เราควรที่จะทำเช่นนั้นเป็นหลัก

69
00:03:24,820 --> 00:03:27,560
>> ถ้าคุณคิดว่าของเรา
อาร์เรย์เป็นหนึ่งผ่านหก

70
00:03:27,560 --> 00:03:29,900
เราจะเริ่มต้นปิดโดย
ประกาศหนึ่งจะถูกจัดเรียง

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
ดังนั้นสิ่งที่รันไทม์กรณีที่แย่ที่สุดแล้ว?

77
00:03:48,270 --> 00:03:51,854
จำไว้ว่าถ้าเราจะต้องเปลี่ยนแต่ละ
องค์ประกอบ n อาจจะเป็นตำแหน่งที่ n,

78
00:03:51,854 --> 00:03:54,020
หวังที่ช่วยให้คุณ
ความคิดที่ว่ากรณีที่เลวร้ายที่

79
00:03:54,020 --> 00:03:57,770
รันไทม์เป็น Big O ของ 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
ดังนั้นในกรณีที่ดีที่สุดก็โอเมก้าของ n

83
00:04:08,440 --> 00:04:09,490
>> ฉันลอยด์ดั๊ก

84
00:04:09,490 --> 00:04:11,760
นี่คือ CS50

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