1
00:00:00,000 --> 00:00:05,726
>> [موسیقی]

2
00:00:05,726 --> 00:00:08,600
داگ لوید: مرتب سازی بر اساس گزینش است
الگوریتم است که، همانطور که شما ممکن است انتظار،

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
و ما مجبور به تکرار
این فرایند 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
>> آیا شما حدس می زنم 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