1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [مرتب سازی بر اساس درج]

2
00:00:02,290 --> 00:00:04,240
[تامی MacWilliam] [دانشگاه هاروارد]

3
00:00:04,240 --> 00:00:07,290
[این CS50.TV]

4
00:00:07,290 --> 00:00:13,060
بیایید نگاهی به چیدمان بر اساس درج، یک الگوریتم برای گرفتن یک لیست از اعداد و مرتب سازی آنها.

5
00:00:13,060 --> 00:00:18,300
الگوریتم، به یاد داشته باشید، این است که به سادگی یک روش گام به گام توسط به گام برای انجام یک کار است.

6
00:00:18,300 --> 00:00:23,640
ایده اساسی در پشت مرتب سازی بر درج، این است که به لیست ما را به دو بخش تقسیم

7
00:00:23,640 --> 00:00:26,580
بخش طبقه بندی شده اند و بخش نامرتب است.

8
00:00:26,580 --> 00:00:29,290
>> در هر مرحله از الگوریتم، شماره منتقل شده است

9
00:00:29,290 --> 00:00:32,439
از قسمت نامرتب به قسمت طبقه بندی شده اند

10
00:00:32,439 --> 00:00:35,680
تا در نهایت لیست تمام طبقه بندی شده اند.

11
00:00:35,680 --> 00:00:43,340
در اینجا لیست شش عدد نامرتب - 23، 42، 4، 16، 8، و 15 می باشد.

12
00:00:43,340 --> 00:00:47,680
از آنجا که این شماره ها صعودی نشده است، آنها نامرتب است.

13
00:00:47,680 --> 00:00:53,890
از آنجا که ما را شروع کرده اند مرتب سازی هنوز، ما در نظر گرفتن هر شش عنصر بخش نامرتب ما.

14
00:00:53,890 --> 00:00:59,270
>> هنگامی که ما شروع به طبقه بندی، خواهیم این اعداد طبقه بندی شده اند را به سمت چپ از این قرار داده است.

15
00:00:59,270 --> 00:01:03,600
بنابراین، اجازه دهید با شروع 23، این عنصر را برای اولین بار در لیست ما است.

16
00:01:03,600 --> 00:01:06,930
ما هیچ کدام از عناصر موجود در بخش طبقه بندی شده اند ما هنوز رتبهدهی نشده است،

17
00:01:06,930 --> 00:01:12,460
بنابراین به سادگی با در نظر گرفتن 23 شروع و پایان از بخش طبقه بندی شده اند ما را به.

18
00:01:12,460 --> 00:01:16,510
در حال حاضر، طبقه بندی شده اند ما بخش دارای یک عدد، 23،

19
00:01:16,510 --> 00:01:20,260
و بخش نامرتب ما دارای این پنج عدد است.

20
00:01:20,260 --> 00:01:27,320
اجازه دهید در حال حاضر وارد کردن عدد بعدی در قسمت نامرتب، 42، به بخش طبقه بندی شده اند.

21
00:01:27,320 --> 00:01:35,930
>> برای انجام این کار، ما نیاز به مقایسه 42 تا از 23 - تنها عنصر ما در بخش طبقه بندی شده اند تا کنون.

22
00:01:35,930 --> 00:01:41,980
چهل و دو بزرگتر از 23 است، بنابراین ما به سادگی می توانید به اضافه 42 تا پایان

23
00:01:41,980 --> 00:01:45,420
بخش از فهرست طبقه بندی شده اند. بزرگ!

24
00:01:45,420 --> 00:01:51,850
حاضر مرتب شده اند ما بخش دارای دو عنصر است، و بخش نامرتب ما دارای چهار عنصر است.

25
00:01:51,850 --> 00:01:57,200
بنابراین، اجازه دهید در حال حاضر به 4 حرکت می کند، عنصر بعدی در قسمت نامرتب است.

26
00:01:57,200 --> 00:02:00,230
بنابراین، جایی که باید از این توان در بخش مرتب شده قرار داده است؟

27
00:02:00,230 --> 00:02:04,220
>> به یاد داشته باشید، ما می خواهیم به جای این شماره به منظور طبقه بندی شده اند

28
00:02:04,220 --> 00:02:08,680
بنابراین طبقه بندی شده اند ما بخش باقی مانده به درستی در همه زمان ها طبقه بندی شده اند.

29
00:02:08,680 --> 00:02:14,380
اگر ما از 4 به سمت راست از 42، پس از آن لیست ما خواهد بود از.

30
00:02:14,380 --> 00:02:18,380
بنابراین، بیایید در حال حرکت راست به چپ در قسمت مرتب کردن بر اساس ما ادامه.

31
00:02:18,380 --> 00:02:23,260
همانطور که ما حرکت می کند، اجازه تغییر هر عدد پایین محل به اتاق را برای شماره جدید.

32
00:02:25,440 --> 00:02:31,740
خوب، 4 است نیز کمتر از 23 است، بنابراین ما می توانیم آن را در اینجا قرار دهید یا.

33
00:02:31,740 --> 00:02:34,480
اجازه دهید از 23 راست یک مکان.

34
00:02:36,500 --> 00:02:43,120
>> این بدان معناست که ما می خواهم 4 تا اسلات برای اولین بار در بخش مرتب شده قرار.

35
00:02:43,120 --> 00:02:46,300
توجه داشته باشید که چگونه این فضا در این فهرست در حال حاضر خالی است،

36
00:02:46,300 --> 00:02:51,120
از آنجا که ما شده ایم حرکت عناصر طبقه بندی شده اند، که ما آنها را مواجه می شوند.

37
00:02:51,120 --> 00:02:52,740
بسیار خوب. بنابراین، ما در نیمه راه وجود دارد.

38
00:02:52,740 --> 00:02:57,990
اجازه دهید ادامه الگوریتم ما با قرار دادن 16 به بخش طبقه بندی شده اند.

39
00:02:59,260 --> 00:03:03,820
شانزده کمتر از 42 است، به طوری که اجازه تغییر از 42 به سمت راست.

40
00:03:05,700 --> 00:03:10,190
شانزده نیز کمتر از 23 است، بنابراین اجازه دهید نیز تغییر آن عنصر است.

41
00:03:11,790 --> 00:03:20,820
>> در حال حاضر، 16 بزرگتر از 4 است. بنابراین، به نظر می رسد که ما می خواهم به وارد کردن 16 بین 4 و 23.

42
00:03:20,820 --> 00:03:24,620
در حالی که در حال حرکت از طریق بخش از فهرست طبقه بندی شده اند از راست به چپ،

43
00:03:24,620 --> 00:03:29,160
4 شماره اول دیده ایم که کوچکتر است از تعداد

44
00:03:29,160 --> 00:03:31,540
ما در حال تلاش برای وارد کردن.

45
00:03:31,540 --> 00:03:35,820
بنابراین، در حال حاضر ما می توانیم از 16 را به این اسلات خالی وارد

46
00:03:35,820 --> 00:03:40,520
که به یاد داشته باشید، ما که توسط عناصر متحرک در بخش مرتب سازی بر ایجاد

47
00:03:40,520 --> 00:03:43,340
که ما آنها را مواجه می شوند.

48
00:03:43,340 --> 00:03:47,900
>> بسیار خوب. در حال حاضر، ما چهار طبقه بندی شده اند و عناصر دو عنصر نامرتب است.

49
00:03:47,900 --> 00:03:51,600
بنابراین، اجازه دهید 8 به بخش طبقه بندی شده اند.

50
00:03:51,600 --> 00:03:55,010
هشت کمتر از 42 است.

51
00:03:55,010 --> 00:03:56,940
هشت کمتر از 23 است.

52
00:03:56,940 --> 00:04:00,230
و 8 کمتر از 16 است.

53
00:04:00,230 --> 00:04:03,110
اما 8 است بیشتر از 4 است.

54
00:04:03,110 --> 00:04:07,280
بنابراین، ما می خواهم برای قرار دادن 8 بین 4 و 16.

55
00:04:09,070 --> 00:04:13,650
و در حال حاضر ما فقط باید یک عنصر سمت چپ مرتب - از 15.

56
00:04:13,950 --> 00:04:16,589
پانزده کمتر از 42 است،

57
00:04:16,589 --> 00:04:19,130
پانزده کمتر از 23 است.

58
00:04:19,130 --> 00:04:21,750
و 15 کمتر از 16 است.

59
00:04:21,750 --> 00:04:24,810
اما 15 بیشتر از 8 می باشد.

60
00:04:24,810 --> 00:04:27,440
>> بنابراین، در اینجا این است که در آن ما می خواهیم به درج نهایی ما می باشد.

61
00:04:28,770 --> 00:04:30,330
و ما در حال انجام شده است.

62
00:04:30,330 --> 00:04:33,540
در حال حاضر هیچ یک از عناصر بیشتر در بخش نامرتب،

63
00:04:33,540 --> 00:04:36,670
و قسمت طبقه بندی شده اند ما را در جهت درست است.

64
00:04:36,670 --> 00:04:40,270
این شماره ها از کوچکترین به بزرگترین سفارش داد.

65
00:04:40,270 --> 00:04:44,330
بنابراین، اجازه دهید نگاهی به برخی از شبه است که مراحل ما فقط انجام.

66
00:04:46,760 --> 00:04:51,740
>> در خط 1، ما می توانید ببینید که ما نیاز به تکرار بیش از هر عنصر در لیست

67
00:04:51,740 --> 00:04:57,060
جز اول، چون این عنصر برای اولین بار در بخش نامرتب به سادگی تبدیل خواهد شد

68
00:04:57,060 --> 00:05:00,220
این عنصر را برای اولین بار در بخش طبقه بندی شده اند.

69
00:05:00,220 --> 00:05:06,320
در خطوط 2 و 3، ما در حال پیگیری از محل فعلی ما در بخش نامرتب است.

70
00:05:06,320 --> 00:05:10,450
عنصر نشان دهنده تعداد ما در حال حاضر به بخش طبقه بندی شده اند در حال حرکت،

71
00:05:10,450 --> 00:05:15,600
و j نشان دهنده شاخص ما به بخش نامرتب است.

72
00:05:15,600 --> 00:05:20,980
>> در خط 4، که ما در حال تکرار از طریق بخش طبقه بندی شده اند از راست به چپ است.

73
00:05:20,980 --> 00:05:26,010
ما می خواهیم برای جلوگیری از تکرار هنگامی که عنصر به سمت چپ موقعیت فعلی ما

74
00:05:26,010 --> 00:05:30,050
است کمتر از عنصر ما در حال تلاش برای وارد کردن است.

75
00:05:30,050 --> 00:05:35,600
در خط 5، ما در حال تغییر هر یک از عناصر یک فضا روبرو می شوند که ما را به سمت راست است.

76
00:05:35,600 --> 00:05:40,950
به این ترتیب، ما می خواهیم یک فضای روشن برای وارد کردن به زمانی که ما اولین عنصر

77
00:05:40,950 --> 00:05:44,080
کمتر از عنصر ما در حال حرکت است.

78
00:05:44,080 --> 00:05:50,800
در خط 6، ما در حال به روز رسانی شمارنده ما به ادامه حرکت در سمت چپ از طریق بخش طبقه بندی شده اند.

79
00:05:50,800 --> 00:05:56,860
در نهایت، در خط 7، ما در حال قرار دادن این عنصر را به بخش از فهرست طبقه بندی شده اند.

80
00:05:56,860 --> 00:06:00,020
>> ما می دانیم که آن را درست به به J موقعیت قرار دادن،

81
00:06:00,020 --> 00:06:05,360
زیرا ما قبلا این عنصر استفاده می شود که می شود وجود دارد یک فضا را به سمت راست منتقل شده است.

82
00:06:05,360 --> 00:06:09,460
به یاد داشته باشید، ما در حال حرکت را از طریق قسمت طبقه بندی شده اند از راست به چپ،

83
00:06:09,460 --> 00:06:13,960
اما ما در حال حرکت را از طریق قسمت نامرتب از چپ به راست است.

84
00:06:13,960 --> 00:06:19,090
بسیار خوب. اکنون بیایید نگاهی به در چه مدت در حال اجرا است که الگوریتم گرفت.

85
00:06:19,090 --> 00:06:25,300
ما برای اولین بار می خواهید این سوال چه مدت طول می کشد که برای این الگوریتم در بدترین حالت اجرا کنید.

86
00:06:25,300 --> 00:06:29,040
به یاد بیاورید که ما این زمان در حال اجرا را با نماد O بزرگ.

87
00:06:32,530 --> 00:06:38,500
به منظور مرتب کردن بر اساس لیست ما، ما مجبور به تکرار بیش از عناصر موجود در بخش نامرتب،

88
00:06:38,500 --> 00:06:43,430
و برای هر یک از این عناصر، به طور بالقوه در بیش از تمام عناصر در بخش طبقه بندی شده اند.

89
00:06:43,430 --> 00:06:47,950
به طور مستقیم، این برای تلفن های موبایل مانند عملیات O (n ^ 2) است.

90
00:06:47,950 --> 00:06:51,840
>> نگاهی شبه ما، ما باید یک حلقه در داخل یکی دیگر از حلقه تو در تو،

91
00:06:51,840 --> 00:06:55,290
که، در واقع، برای تلفن های موبایل مانند عملیات O (n ^ 2) است.

92
00:06:55,290 --> 00:07:01,590
با این حال، بخش طبقه بندی شده اند از فهرست فهرست کامل تا پایان را شامل نمی شود.

93
00:07:01,590 --> 00:07:06,920
با این حال، ما به طور بالقوه می تواند یک عنصر جدید در همان ابتدا از بخش طبقه بندی شده اند وارد

94
00:07:06,920 --> 00:07:09,320
در هر تکرار الگوریتم،

95
00:07:09,320 --> 00:07:14,500
که بدان معنی است که ما می خواهم که در هر عنصر در حال حاضر در بخش طبقه بندی شده اند.

96
00:07:14,500 --> 00:07:20,090
بنابراین، این بدان معناست که ما به طور بالقوه می تواند یک مقایسه را برای این عنصر دوم،

97
00:07:20,090 --> 00:07:24,660
دو مقایسه را برای این عنصر سوم، و غیره.

98
00:07:24,660 --> 00:07:32,480
بنابراین، تعداد کل مراحل جمع اعداد صحیح از 1 تا طول لیست منهای 1 می باشد.

99
00:07:32,480 --> 00:07:35,240
ما می توانیم این کار را با یک جمع را نمایندگی کند.

100
00:07:41,170 --> 00:07:47,270
>> ما نمی خواهد به summations در اینجا، اما به نظر می رسد که این جمع برابر است با

101
00:07:47,270 --> 00:07:57,900
N (n - 1) بیش از 2 است که معادل N ^ 2/2 - N / 2 است.

102
00:07:57,900 --> 00:08:00,800
هنگامی که صحبت کردن در مورد زمان اجرا مجانبی،

103
00:08:00,800 --> 00:08:05,170
این N ^ 2 مدت در حال رفتن به تسلط در این مدت ازت.

104
00:08:05,170 --> 00:08:11,430
بنابراین، مرتب کردن بر اساس درج بزرگ O (n ^ 2) است.

105
00:08:11,430 --> 00:08:16,150
چه می شود اگر ما مرتب سازی بر درج در فهرست طبقه بندی شده اند در حال حاضر زد.

106
00:08:16,150 --> 00:08:20,960
در آن صورت، ما به سادگی می خواهم تا ساخت قسمت طبقه بندی شده اند از چپ به راست.

107
00:08:20,960 --> 00:08:25,050
بنابراین، ما فقط در جهت از مراحل N نیاز دارید.

108
00:08:25,050 --> 00:08:29,740
>> این بدان معنی است که مرتب سازی بر درج بهترین عملکرد مورد N،

109
00:08:29,740 --> 00:08:34,130
که ما آن را با Ω (n) را نمایندگی کند.

110
00:08:34,130 --> 00:08:36,190
و آن را برای مرتب کردن بر اساس قرار دادن،

111
00:08:36,190 --> 00:08:40,429
فقط یکی از الگوریتم های بسیاری از ما می توانیم با استفاده از یک لیست مرتب سازی بر اساس.

112
00:08:40,429 --> 00:08:43,210
نام تامی است، و این CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
آه، شما نه تنها می تواند به توقف است که یک بار آن شروع می شود.

115
00:09:01,620 --> 00:09:04,760
آه، ما این کار را انجام دادیم - بوم >>!