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
pseudocode کے لئے اس کو توڑ
ہم اس الگورتھم بیان سکتا

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
اور ہم دوبارہ کرنا پڑے
اس عمل کو (ن) بار.

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
ن عناصر میں سے ہر ایک بار.

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
>> مربع ن آپ کو بگ اے لگتا تھا،
اور بگ ومیگا (ن) کے مربع؟

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