1
00:00:00,000 --> 00:00:02,826
>> [MÜZİK OYUN]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> Doug LLOYD: Yani ekleme sıralama başka bir şeydir
Algoritma, biz bir dizi sıralamak için kullanabilirsiniz.

4
00:00:09,370 --> 00:00:12,350
Bu algoritma arkasındaki fikir
senin sıralı dizi oluşturmaktır

5
00:00:12,350 --> 00:00:19,670
yerinde, takım elemanları değişen
Eğer gitmek gibi yol, yer açmak için.

6
00:00:19,670 --> 00:00:22,240
Bu biraz farklıdır
Seçim tür veya kabarcık

7
00:00:22,240 --> 00:00:25,460
sıralama, örneğin, nerede
Biz yerleri ayarlama ediyoruz,

8
00:00:25,460 --> 00:00:26,910
nerede swapları yapıyoruz.

9
00:00:26,910 --> 00:00:29,760
>> Bu durumda ne aslında konum
yapıyor sürgülü unsurlar

10
00:00:29,760 --> 00:00:31,390
üzerinde, yolumdan.

11
00:00:31,390 --> 00:00:34,030
Bu algoritma yapar nasıl
pseudocode çalışır?

12
00:00:34,030 --> 00:00:37,646
Peki sadece keyfi olduğunu diyelim
Dizinin ilk elemanı sıralanır.

13
00:00:37,646 --> 00:00:38,770
Biz bir yerde inşa ediyoruz.

14
00:00:38,770 --> 00:00:42,660
>> Biz olacak bir seferde bir eleman gidip konum ve
onu inşa ve böylece ilk şey gördüğümüz

15
00:00:42,660 --> 00:00:43,890
Bir tek unsur dizidir.

16
00:00:43,890 --> 00:00:47,720
Ve tanımı gereği, bir
eleman dizisi sıralanır.

17
00:00:47,720 --> 00:00:50,850
>> Sonra bu işlemi tekrarlayın edeceğiz until--
aşağıdaki işlemi tekrarlayın edeceğiz

18
00:00:50,850 --> 00:00:52,900
bütün elemanları kriteri kadar devam eder.

19
00:00:52,900 --> 00:00:57,770
Bir sonraki ayrımı yapılmamış diğer elemana bak ve
Sıralanan kısmına takın,

20
00:00:57,770 --> 00:01:01,209
gerekli sayıda kaydırarak
yolumdan elemanlarının.

21
00:01:01,209 --> 00:01:03,750
Umarım bu görselleştirme
Eğer tam olarak ne olduğunu görmek yardımcı olacaktır

22
00:01:03,750 --> 00:01:05,980
Ekleme sıralama ile devam.

23
00:01:05,980 --> 00:01:08,010
>> Yani yine burada bulunuyor
Tüm sıralanmamış dizi,

24
00:01:08,010 --> 00:01:10,970
elementlerin bütün kırmızı ile gösterilmiştir.

25
00:01:10,970 --> 00:01:13,320
Ve en takip edelim
Bizim pseudocode adımlar.

26
00:01:13,320 --> 00:01:16,970
Yaptığımız ilk şey, biz diyoruz olduğunu
dizinin ilk elemanı sıralanır.

27
00:01:16,970 --> 00:01:20,920
Yani biz öylece demek sensin
Beş, artık sıralanmış ediyoruz.

28
00:01:20,920 --> 00:01:24,570
>> Sonra bir sonraki bakmak
Dizinin sıralanmamış elemanı

29
00:01:24,570 --> 00:01:27,610
ve biz bunu eklemek istediğiniz
kriteri bölümü içine,

30
00:01:27,610 --> 00:01:29,750
elemanları üzerinde kaydırarak.

31
00:01:29,750 --> 00:01:33,470
Yani iki sonraki sıralanmamış
dizi elemanı.

32
00:01:33,470 --> 00:01:36,250
Açıkçası daha önce aittir
Beş, bu yüzden biz ne yapacağız konum

33
00:01:36,250 --> 00:01:41,580
çeşit bir saniye kenara iki basılı tutun,
üzerinde beş vardiya ve ardından iki takın

34
00:01:41,580 --> 00:01:43,210
Beş önce, nereye gitmeli için.

35
00:01:43,210 --> 00:01:45,280
Ve şimdi biz iki sıralanır söyleyebiliriz.

36
00:01:45,280 --> 00:01:48,400
>> Gördüğünüz gibi Yani, biz şimdiye kadar sadece ettik
Dizinin iki unsur baktı.

37
00:01:48,400 --> 00:01:50,600
Biz bakmadım
tüm dinlenmek, ama biz ettik

38
00:01:50,600 --> 00:01:54,582
Bu iki unsur sıralama kriteri var
kaydırma mekanizması yolu.

39
00:01:54,582 --> 00:01:56,410
>> Bu yüzden tekrar işlemi yineleyin.

40
00:01:56,410 --> 00:01:58,850
Bir sonraki unsorted bak
eleman, işte o.

41
00:01:58,850 --> 00:02:04,010
, Bir saniye kenara tutun Let
üzerinde her şeyi vardiya ve bir tane koyun

42
00:02:04,010 --> 00:02:05,570
nereye gitmeli.

43
00:02:05,570 --> 00:02:08,110
>> Yine, halen, biz sadece hiç ettik
bir, iki ve beş baktı.

44
00:02:08,110 --> 00:02:12,480
Biz geliyor başka ne bilmiyorum,
ama biz bu üç unsuru sınıflandırılmaktadır ettik.

45
00:02:12,480 --> 00:02:16,030
>> Sonraki sıralanmamış elemanıdır
Üç, bu yüzden bir kenara koyun olacak.

46
00:02:16,030 --> 00:02:18,200
Biz üzerinde kayma olacak ne
hangi bu sefer gerekir

47
00:02:18,200 --> 00:02:21,820
Önceki gibi her şey değildir
iki olgu, sadece beş.

48
00:02:21,820 --> 00:02:25,440
Ve sonra biz üç çakacağım,
İki ile beş arasında.

49
00:02:25,440 --> 00:02:27,849
>> Altı unsorted yanındaki
diziye eleman.

50
00:02:27,849 --> 00:02:31,140
Ve aslında altı yüzden, beşten büyüktür
biz bile herhangi bir takas yapmak gerekmez.

51
00:02:31,140 --> 00:02:35,710
Biz sadece sağ için altı çakmak olabilir
sıralanmış bölümünün sonu.

52
00:02:35,710 --> 00:02:38,270
>> Son olarak, dört olduğu
Son sıralanmamış unsur.

53
00:02:38,270 --> 00:02:42,060
Yani biz bir kenara koyun edeceğiz, üzerinde kayması
elementler biz üzerinde kaydırmaya gerek

54
00:02:42,060 --> 00:02:43,780
ait olduğu yere ve sonra dört koydu.

55
00:02:43,780 --> 00:02:46,400
Ve şimdi, bak biz bir çeşit ettik
tüm elementlerin.

56
00:02:46,400 --> 00:02:48,150
Ekleme ile dikkat
sıralama biz yoktu

57
00:02:48,150 --> 00:02:50,240
ileri ve geri dizi boyunca gitmek için.

58
00:02:50,240 --> 00:02:54,720
Biz sadece dizi boyunca gitti
bir kez, ve biz bir şeyler değiştirdi

59
00:02:54,720 --> 00:02:59,870
biz zaten sipariş, karşılaşılan olacağımı
yeni unsurlar yer açmak için.

60
00:02:59,870 --> 00:03:02,820
>> Peki kötü durumda bulunuyor
Ekleme çeşit senaryo?

61
00:03:02,820 --> 00:03:05,090
En kötü durumda,
Dizi tersten olduğunu.

62
00:03:05,090 --> 00:03:11,180
Sen n öğelerinin her değiştirmek zorunda
n pozisyonlarına kadar her zaman biz

63
00:03:11,180 --> 00:03:12,880
Bir ekleme yapmak.

64
00:03:12,880 --> 00:03:15,720
Bu değişen bir sürü.

65
00:03:15,720 --> 00:03:18,014
>> En iyi durumda,
Dizi mükemmel sıralanır.

66
00:03:18,014 --> 00:03:20,680
Ve çeşit ne gibi
örnekte beş ve altı ile

67
00:03:20,680 --> 00:03:23,779
sadece onu tack nerede
Herhangi bir vites yapmak zorunda kalmadan,

68
00:03:23,779 --> 00:03:24,820
biz aslında böyle yapardım.

69
00:03:24,820 --> 00:03:27,560
>> Bunu düşünürsek bizim
Dizi, altıya kadar oldu

70
00:03:27,560 --> 00:03:29,900
Biz başlamak istiyorum
biri ilan sıralanır.

71
00:03:29,900 --> 00:03:33,300
İki böylece biz sadece can birbiri ardına geliyor
Bir ve iki sıralanır iyi, tamam, demek.

72
00:03:33,300 --> 00:03:36,190
Üç Tamam, sonra iki gelir
bir ve iki ve üç sıralanır.

73
00:03:36,190 --> 00:03:39,590
>> Biz konum, herhangi bir swap yapma değil
sadece bu keyfi hattı hareketli

74
00:03:39,590 --> 00:03:42,460
Biz giderken arasında sıralanır ve sıralanmamış.

75
00:03:42,460 --> 00:03:46,646
Gibi etkili biz örnekte olduğu gibi,
biz ilerlerken, mavi unsurları dönüm.

76
00:03:46,646 --> 00:03:48,270
Yani en kötü durum zamanı daha sonra, ne var?

77
00:03:48,270 --> 00:03:51,854
Biz her vardiya varsa, Unutmayın
n elemanları da N konumları,

78
00:03:51,854 --> 00:03:54,020
umarım bu size verir
En kötü durumda olduğunu bir fikir

79
00:03:54,020 --> 00:03:57,770
Çalışma zamanı n Big O karesi olduğunu.

80
00:03:57,770 --> 00:04:00,220
>> Dizi mükemmel değilse
sıralanmış, tüm yapmamız gereken

81
00:04:00,220 --> 00:04:04,480
her element bakmak olduğunu
Bir kez, ve sonra biz bitirdik.

82
00:04:04,480 --> 00:04:08,440
Yani en iyi durumda, n omega var.

83
00:04:08,440 --> 00:04:09,490
>> Ben Doug Lloyd değilim.

84
00:04:09,490 --> 00:04:11,760
Bu CS50 olduğunu.

85
00:04:11,760 --> 00:04:13,119