1
00:00:00,000 --> 00:00:05,726
>> [સંગીત વગાડવાનો]

2
00:00:05,726 --> 00:00:08,600
ડો LLOYD: પસંદગી સૉર્ટ છે
તમે આશા રાખી શકે છે કે, અલ્ગોરિધમનો

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
સ્યુડોકોડનો તે તોડી
અમે આ અલ્ગોરિધમનો રાજ્ય શકે

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
અને અમે પુનરાવર્તન છે
આ પ્રક્રિયા n વખત.

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
n તત્વો દરેક માટે એક વાર.

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
>> સ્ક્વેર્ડ n તમે મોટા ઓ ધારી હતી,
અને મોટા ઓમેગા સ્ક્વેર્ડ n ના?

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