1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] تامی: بیایید نگاهی به مرتب کردن بر اساس انتخاب، یک الگوریتم

2
00:00:09,980 --> 00:00:12,800
برای گرفتن یک لیست از اعداد و مرتب سازی آنها.

3
00:00:12,800 --> 00:00:15,750
الگوریتم، به یاد داشته باشید، این است که به سادگی یک گام به گام

4
00:00:15,750 --> 00:00:18,370
روش برای انجام یک کار است.

5
00:00:18,370 --> 00:00:21,470
ایده اصلی در پشت مرتب کردن بر اساس انتخاب است به تقسیم

6
00:00:21,470 --> 00:00:23,390
فهرست ما را به دو بخش -

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

8
00:00:26,810 --> 00:00:30,200
در هر مرحله از الگوریتم، تعدادی از حرکت

9
00:00:30,200 --> 00:00:33,800
بخش نامرتب به بخش طبقه بندی شده اند تا در نهایت

10
00:00:33,800 --> 00:00:35,880
فهرست تمام طبقه بندی شده اند.

11
00:00:35,880 --> 00:00:38,510
بنابراین در اینجا یک لیست از شش عدد -

12
00:00:38,510 --> 00:00:44,010
23، 42، 4، 16، 8، و 15.

13
00:00:44,010 --> 00:00:47,680
در حال حاضر لیست کل در نظر گرفته شده است نامرتب است.

14
00:00:47,680 --> 00:00:51,770
حتی اگر یک عدد مثل 16 در حال حاضر ممکن است در صحیح خود باشد

15
00:00:51,770 --> 00:00:56,040
محل سکونت:، الگوریتم ما هیچ راهی برای دانستن این که تا زمانی که

16
00:00:56,040 --> 00:00:57,980
فهرست تمام طبقه بندی شده اند.

17
00:00:57,980 --> 00:01:01,355
بنابراین ما در هر شماره به نامرتب در نظر بگیرند تا زمانی که مرتب سازی بر اساس

18
00:01:01,355 --> 00:01:03,800
آن خودمان است.

19
00:01:03,800 --> 00:01:06,890
ما می دانیم که ما می خواهیم این فهرست را به صعودی باشد.

20
00:01:06,890 --> 00:01:10,200
بنابراین ما می خواهید برای ساخت قسمت طبقه بندی شده اند از لیست ما

21
00:01:10,200 --> 00:01:13,280
از چپ به راست، کوچکترین به بزرگترین.

22
00:01:13,280 --> 00:01:17,970
برای انجام این کار، ما نیاز به پیدا کردن عنصر نامرتب حداقل

23
00:01:17,970 --> 00:01:21,350
و آن را در پایان از بخش طبقه بندی شده اند.

24
00:01:21,350 --> 00:01:25,370
از آنجا که این لیست طبقه بندی شده اند، تنها راه برای انجام این کار این است که به

25
00:01:25,370 --> 00:01:29,330
نگاهی به هر یک از عناصر در بخش نامرتب، به خاطر سپردن

26
00:01:29,330 --> 00:01:32,010
عنصری که کمترین و مقایسه

27
00:01:32,010 --> 00:01:33,770
هر عنصر به آن.

28
00:01:33,770 --> 00:01:36,150
بنابراین ما برای اولین بار می خواهید از 23 نگاه کنید.

29
00:01:36,150 --> 00:01:38,650
این عنصر برای اولین بار دیده ایم است، بنابراین ما به یاد داشته باشید

30
00:01:38,650 --> 00:01:40,050
آن را به عنوان حداقل.

31
00:01:40,050 --> 00:01:42,320
بعد ما را در 42 نگاه کنید.

32
00:01:42,320 --> 00:01:46,720
42 بزرگتر از 23 است، به طوری که 23 هنوز هم حداقل است.

33
00:01:46,720 --> 00:01:51,210
بعد از 4 است که کمتر از 23 است، بنابراین خواهیم 4 به یاد داشته باشید

34
00:01:51,210 --> 00:01:52,880
به عنوان حداقل های جدید است.

35
00:01:52,880 --> 00:01:56,380
بعد 16] که بزرگتر از 4 است، SO 4

36
00:01:56,380 --> 00:01:57,980
هنوز هم حداقل است.

37
00:01:57,980 --> 00:02:03,670
است 8 بزرگتر از 4 و 15 بزرگتر از 4 است، SO 4 باید

38
00:02:03,670 --> 00:02:05,980
کوچکترین عنصر نامرتب.

39
00:02:05,980 --> 00:02:09,350
بنابراین حتی اگر به عنوان انسان، ما بلافاصله می تواند که 4 است

40
00:02:09,350 --> 00:02:12,300
حداقل عنصر، الگوریتم ما باید به دنبال در

41
00:02:12,300 --> 00:02:15,710
هر عنصر نامرتب، حتی پس از ما پیدا کرده ام 4 -

42
00:02:15,710 --> 00:02:16,860
عنصر حداقل.

43
00:02:16,860 --> 00:02:19,900
بنابراین در حال حاضر که ما یافتیم این عنصر حداقل، 4، ما می خواهید

44
00:02:19,900 --> 00:02:23,410
به آن حرکت را به بخش از فهرست طبقه بندی شده اند.

45
00:02:23,410 --> 00:02:27,320
از آنجایی که این اولین گام، این بدان معنی است که ما می خواهیم برای قرار دادن 4 در

46
00:02:27,320 --> 00:02:29,680
آغاز از لیست.

47
00:02:29,680 --> 00:02:33,040
در حال حاضر 23 در ابتدای فهرست، به طوری

48
00:02:33,040 --> 00:02:36,080
اجازه مبادله در 4 و 23.

49
00:02:36,080 --> 00:02:38,870
بنابراین در حال حاضر لیست ما به نظر می رسد مثل این.

50
00:02:38,870 --> 00:02:42,710
ما می دانیم که 4 باید در محل نهایی خود باشد، به دلیل آن است که

51
00:02:42,710 --> 00:02:45,890
هر دو کوچکترین عنصر و عنصر در ابتدا

52
00:02:45,890 --> 00:02:46,960
فهرست.

53
00:02:46,960 --> 00:02:50,650
بنابراین این بدان معنی است که ما هرگز نیاز به آن حرکت دوباره.

54
00:02:50,650 --> 00:02:53,910
بنابراین تکرار این فرایند عنصری دیگر برای اضافه کردن به

55
00:02:53,910 --> 00:02:55,910
بخش از فهرست طبقه بندی شده اند.

56
00:02:55,910 --> 00:02:58,950
ما می دانیم که ما نیازی به در 4 نگاه کنید، چرا که آن

57
00:02:58,950 --> 00:03:00,000
در حال حاضر طبقه بندی شده اند.

58
00:03:00,000 --> 00:03:03,540
بنابراین ما می توانیم از 42 شروع می شود، که ما آن را به عنوان به یاد داشته باشید

59
00:03:03,540 --> 00:03:05,290
عنصر حداقل.

60
00:03:05,290 --> 00:03:08,700
بنابراین بعد ما در 23 است که کمتر از 42 نگاه خواهیم کرد، بنابراین ما

61
00:03:08,700 --> 00:03:11,620
به یاد داشته باشید 23 حداقل جدید.

62
00:03:11,620 --> 00:03:14,870
بعد ما می بینیم از 16 است که کمتر از 23 است، به طوری

63
00:03:14,870 --> 00:03:16,800
16 حداقل است.

64
00:03:16,800 --> 00:03:19,720
در حال حاضر ما در 8 است که کمتر از 16 نگاه کنید، به طوری که

65
00:03:19,720 --> 00:03:21,130
8 حداقل است.

66
00:03:21,130 --> 00:03:25,900
و در نهایت 8 کمتر از 15 است، بنابراین ما می دانیم که 8 حداقل

67
00:03:25,900 --> 00:03:27,780
عنصر نامرتب.

68
00:03:27,780 --> 00:03:30,660
بنابراین این بدان معناست که ما باید 8 تا طبقه بندی شده اند اضافه

69
00:03:30,660 --> 00:03:32,450
بخشی از فهرست.

70
00:03:32,450 --> 00:03:35,990
در حال حاضر 4 تنها عنصر طبقه بندی شده اند، به طوری که ما می خواهیم به جای

71
00:03:35,990 --> 00:03:38,410
بعدی 8 به 4.

72
00:03:38,410 --> 00:03:41,920
از سال 42 این عنصر را برای اولین بار در بخش نامرتب است

73
00:03:41,920 --> 00:03:47,260
فهرست، ما می خواهید به مبادله 42 و 8.

74
00:03:47,260 --> 00:03:49,680
بنابراین در حال حاضر لیست ما به نظر می رسد مثل این.

75
00:03:49,680 --> 00:03:53,830
4 و 8 نشان دهنده بخش از فهرست طبقه بندی شده اند، و

76
00:03:53,830 --> 00:03:56,440
باقی مانده اعداد نامرتب

77
00:03:56,440 --> 00:03:58,260
بخشی از فهرست.

78
00:03:58,260 --> 00:04:00,630
بنابراین ادامه با یکی دیگر از تکرار کنیم.

79
00:04:00,630 --> 00:04:03,850
ما با 23 شروع به این زمان، از آنجایی که ما لازم نیست که به دنبال در

80
00:04:03,850 --> 00:04:05,770
از 4 و 8 دیگر از آنجا که

81
00:04:05,770 --> 00:04:07,660
در حال حاضر مرتب شده است.

82
00:04:07,660 --> 00:04:10,270
16 کمتر از 23 است، بنابراین ما به یاد داشته باشید

83
00:04:10,270 --> 00:04:12,070
16 به عنوان حداقل های جدید شده است.

84
00:04:12,070 --> 00:04:18,149
16 کمتر از 42 است، اما 15 این است که کمتر از 16، تا 15 باید

85
00:04:18,149 --> 00:04:20,480
عنصر حداقل نامرتب.

86
00:04:20,480 --> 00:04:24,580
بنابراین در حال حاضر ما می خواهیم به مبادله 15 و 23 تا

87
00:04:24,580 --> 00:04:26,310
ما این لیست را به من بدهید.

88
00:04:26,310 --> 00:04:30,500
بخش طبقه بندی شده اند از فهرست متشکل از 4، 8 و 15، و

89
00:04:30,500 --> 00:04:33,210
این عناصر هنوز نامرتب است.

90
00:04:33,210 --> 00:04:36,900
اما این فقط اتفاق می افتد که عنصر بعدی نامرتب، 16،

91
00:04:36,900 --> 00:04:38,480
در حال حاضر طبقه بندی شده اند.

92
00:04:38,480 --> 00:04:42,060
با این حال، هیچ راهی وجود دارد برای الگوریتم ما به دانستن که 16

93
00:04:42,060 --> 00:04:45,230
در حال حاضر در محل صحیح خود است، بنابراین ما هنوز هم نیاز به

94
00:04:45,230 --> 00:04:47,870
دقیقا همین روند را تکرار.

95
00:04:47,870 --> 00:04:53,750
پس ما می بینیم که 16 این است که کمتر از 42 و 16 این است که کمتر از 23 است، بنابراین

96
00:04:53,750 --> 00:04:56,230
16 سال باید به حداقل عنصر است.

97
00:04:56,230 --> 00:04:59,010
این غیر ممکن است این عنصر را با خود به مبادله، بنابراین ما می توانیم

98
00:04:59,010 --> 00:05:01,780
به سادگی آن را در این مکان را ترک کنند.

99
00:05:01,780 --> 00:05:04,660
بنابراین ما نیاز به عبور یکی دیگر از الگوریتم ما.

100
00:05:04,660 --> 00:05:09,370
42 بزرگتر از 23 است، به طوری که 23 باید

101
00:05:09,370 --> 00:05:10,970
حداقل عنصر نامرتب.

102
00:05:10,970 --> 00:05:17,410
پس از 23 و 42 مبادله، ما تا پایان با نهایی ما

103
00:05:17,410 --> 00:05:18,530
طبقه بندی شده اند - فهرست

104
00:05:18,530 --> 00:05:23,390
4، 8، 15، 16، 23، 42.

105
00:05:23,390 --> 00:05:26,830
ما می دانیم که 42 باید در محل صحیح از آن

106
00:05:26,830 --> 00:05:30,210
تنها عنصر باقی مانده است، و این که مرتب سازی بر اساس انتخاب.

107
00:05:30,210 --> 00:05:32,100
بیایید در حال حاضر الگوریتم ما با برخی از رسمی

108
00:05:32,100 --> 00:05:34,540
شبه.

109
00:05:34,540 --> 00:05:37,760
در خط اول، ما می توانید ببینید که ما نیاز به استفاده از بیش از

110
00:05:37,760 --> 00:05:39,530
هر عنصر از لیست.

111
00:05:39,530 --> 00:05:42,150
به جز آخرین عنصر، از عنصر 1

112
00:05:42,150 --> 00:05:44,230
لیست در حال حاضر طبقه بندی شده اند.

113
00:05:44,230 --> 00:05:48,100
در خط دو، از نظر ما اولین عنصر نامرتب

114
00:05:48,100 --> 00:05:51,080
بخشی از این فهرست به حداقل، به عنوان ما با ما

115
00:05:51,080 --> 00:05:53,750
به عنوان مثال، بنابراین ما باید چیزی برای مقایسه.

116
00:05:53,750 --> 00:05:57,260
خط سوم شروع می شود حلقه دوم است که در آن ما تکرار بیش از

117
00:05:57,260 --> 00:05:59,170
هر یک از عناصر نامرتب است.

118
00:05:59,170 --> 00:06:02,150
ما می دانیم که بعد از من تکرار، بخش طبقه بندی شده اند

119
00:06:02,150 --> 00:06:05,330
از لیست ما باید در آن از عناصر هر مرحله

120
00:06:05,330 --> 00:06:06,890
انواع یک عنصر است.

121
00:06:06,890 --> 00:06:11,770
بنابراین اولین عنصر نامرتب باید در موقعیت به علاوه 1 باشد.

122
00:06:11,770 --> 00:06:15,440
در خط چهارم، مقایسه کنیم عنصر فعلی را به حداقل برساند

123
00:06:15,440 --> 00:06:17,750
عنصر است که ما تا کنون دیده ایم.

124
00:06:17,750 --> 00:06:20,560
اگر عنصر کوچکتر است از حداقل

125
00:06:20,560 --> 00:06:23,870
عنصر، پس از آن ما به یاد داشته باشید در حال حاضر به عنوان عنصر جدید

126
00:06:23,870 --> 00:06:26,250
حداقل در خط 5.

127
00:06:26,250 --> 00:06:29,900
در نهایت، در خطوط شش و هفت، ما مبادله حداقل

128
00:06:29,900 --> 00:06:33,080
عنصر با عنصر اول نامرتب، در نتیجه

129
00:06:33,080 --> 00:06:36,990
اضافه کردن آن را به بخش از فهرست طبقه بندی شده اند.

130
00:06:36,990 --> 00:06:40,030
هنگامی که یک الگوریتم، برای پرسیدن یک سوال مهم

131
00:06:40,030 --> 00:06:43,370
خودمان را به عنوان برنامه نویسان این است که چه مدت طول کشید؟

132
00:06:43,370 --> 00:06:46,970
ما ابتدا به این سوال که چگونه آن را برای این

133
00:06:46,970 --> 00:06:50,070
الگوریتم در بدترین حالت اجرا؟

134
00:06:50,070 --> 00:06:51,640
به یاد ما نمایندگی این در حال اجرا

135
00:06:51,640 --> 00:06:55,060
زمان با نماد O بزرگ.

136
00:06:55,060 --> 00:06:58,650
به منظور تعیین حداقل عنصر نامرتب،

137
00:06:58,650 --> 00:07:01,880
اساسا تا به حال به هر عنصر در لیست مقایسه

138
00:07:01,880 --> 00:07:04,040
هر عنصر دیگر در لیست.

139
00:07:04,040 --> 00:07:08,430
به طور مستقیم، این برای تلفن های موبایل مانند O عملیات N مربع است.

140
00:07:08,430 --> 00:07:12,050
نگاهی شبه ما، ما نیز یک حلقه تو در تو در داخل

141
00:07:12,050 --> 00:07:14,420
یکی دیگر از حلقه، که در واقع برای تلفن های موبایل مانند O

142
00:07:14,420 --> 00:07:16,480
عملیات N مربع است.

143
00:07:16,480 --> 00:07:19,250
با این حال، به یاد داشته باشید که ما نیاز به بیش از

144
00:07:19,250 --> 00:07:23,460
فهرست کل زمانی که تعیین حداقل عنصر نامرتب؟

145
00:07:23,460 --> 00:07:26,600
هنگامی که ما می دانستیم که از 4 طبقه بندی شده اند، برای مثال، ما نمی

146
00:07:26,600 --> 00:07:28,170
نیاز به دوباره به آن نگاه کنید.

147
00:07:28,170 --> 00:07:31,020
بنابراین آیا این کاهش زمان در حال اجرا است؟

148
00:07:31,020 --> 00:07:34,510
برای ما طول 6، ما نیاز به 5

149
00:07:34,510 --> 00:07:37,990
مقایسه برای اولین عنصر، چهار مقایسه برای

150
00:07:37,990 --> 00:07:40,750
عنصر دوم، و به همین ترتیب.

151
00:07:40,750 --> 00:07:44,690
این بدان معنی است که تعداد کل مراحل است که مجموع

152
00:07:44,690 --> 00:07:49,160
اعداد صحیح از 1 تا طول لیست منهای 1.

153
00:07:49,160 --> 00:07:51,005
ما می توانیم این کار را با یک جمع را نمایندگی کند.

154
00:07:57,980 --> 00:07:59,910
ما نمی خواهد به summations اینجا.

155
00:07:59,910 --> 00:08:04,900
اما معلوم می شود که این جمع برای بار N برابر است با

156
00:08:04,900 --> 00:08:07,540
N منهای 1 بیش از 2.

157
00:08:07,540 --> 00:08:14,220
یا به طور برابر، توان دو نفر بیش از 2 منهای N بیش از 2.

158
00:08:14,220 --> 00:08:18,860
هنگامی که صحبت کردن در مورد زمان اجرا مجانبی، این اصطلاح مربع N

159
00:08:18,860 --> 00:08:22,070
رفتن به تسلط در این مدت ازت.

160
00:08:22,070 --> 00:08:27,850
بنابراین مرتب کردن بر اساس انتخاب O از N مربع است.

161
00:08:27,850 --> 00:08:31,460
به یاد بیاورید که در مثال ما، مرتب کردن بر اساس انتخاب هنوز نیاز به

162
00:08:31,460 --> 00:08:33,850
بررسی کنید که آیا تعداد که در حال حاضر طبقه بندی شده اند

163
00:08:33,850 --> 00:08:35,450
نیاز به منتقل می شوند.

164
00:08:35,450 --> 00:08:38,929
به طوری که بدان معنی است که اگر ما مرتب کردن بر اساس انتخاب در حال حاضر فرار

165
00:08:38,929 --> 00:08:43,070
طبقه بندی شده اند فهرست، آن را به همان تعداد از مراحل آن را به عنوان نیاز

166
00:08:43,070 --> 00:08:46,340
خواهد بود زمانی که در حال اجرا بیش از یک فهرست نامرتب به طور کامل.

167
00:08:46,340 --> 00:08:51,470
بنابراین مرتب کردن بر اساس انتخاب بهترین عملکرد مورد مربع N،

168
00:08:51,470 --> 00:08:56,820
که ما آن را با امگا N مربع را نمایندگی کند.

169
00:08:56,820 --> 00:08:58,600
و آن را برای مرتب کردن بر اساس انتخاب می باشد.

170
00:08:58,600 --> 00:09:00,630
تنها یکی از الگوریتم های بسیاری از ما می توانیم

171
00:09:00,630 --> 00:09:02,390
استفاده از یک لیست مرتب کردن بر اساس.

172
00:09:02,390 --> 00:09:05,910
نام تامی است، و این cs50.