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
ได้อย่างมีประสิทธิภาพสิ่งนี้จะสร้าง
รายการที่เรียงลำดับองค์ประกอบหนึ่งที่เวลา

9
00:00:26,970 --> 00:00:29,800
ทำลายมันลงไป 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
>> ดังนั้นรันไทม์กรณีที่เลวร้ายเรา
ต้องทำซ้ำกระบวนการ 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
>> คุณคิดว่า Big O ของ n ยืด,
และบิ๊กโอเมก้าสี่เหลี่ยมของ 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