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

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
این الگوریتم چگونه
کار در شبه؟

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، هر زمان که ما تنها

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
سه می آید پس از دو تا، OK،
یک و دو و سه طبقه بندی شده اند.

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
زمان اجرا است 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