[Powered by Google Translate] [విలీనం క్రమీకరించు] [రాబ్ బౌడెన్ - హార్వర్డ్ యూనివర్శిటీ] [ఈ CS50 ఉంది. - CS50.TV] విలీనంతో విధమైన గురించి మాట్లాడేందుకు యొక్క లెట్. ఇప్పటివరకు మీరు బబుల్ సార్ట్, చొప్పించడం విధమైన, మరియు ఎంపిక విధమైన చూసిన. నేను బాగా అర్ధం ఏమిటి వద్ద అల నా చేతి యొక్క రకం చేస్తాము అయితే, విలీనం విధమైన సాధారణంగా ఈ 3 రకాల కంటే మెరుగ్గా పని చేస్తాయి. 

కానీ విలీనంతో విధమైన గురించి మాట్లాడటం ముందు, యొక్క 2 పేర్చిన జాబితాలు విలీనం గురించి మాట్లాడేందుకు అనుమతిస్తాయి. మేము, ఈ వంటి 2 పేర్చిన జాబితాలు తీసుకునే ప్రక్రియ పిలుస్తాను మరియు వాటిలో ఒక క్రమబద్ధీకరించబడతాయి జాబితాను తయారు - జాబితాలు విలీనం. దీన్ని మేము ఎలా చేయగలరు? వెల్, ఒక ఆలోచన కేవలం ఇతర జాబితా ముగింపు లో ఒక జాబితా కట్టుబడి ఉంది మరియు అప్పుడు ఫలిత జాబితా క్రమం. 

ఈ పని, అది అనవసరమైన పని ఉంది. మేము క్రమబద్ధీకరించడం కంటే వేగంగా చేయవచ్చు. ఒక తప్పు ఆలోచన కేవలం ప్రతి జాబితా నుండి ప్రత్యామ్నాయ cups తీసుకోవాలని అని గమనించండి. మొదట ఆ పనులు వంటి అనిపించే అవకాశం ఉన్నప్పటికీ, 16 మరియు 23 స్థానంలో ఉన్నాయి ఆ ప్రకటన - మేము 4, 8, 15, 23, 16 తో ముగుస్తుంది చేసే విధంగా. ఇది విలీనమైన జాబితాలో వరుసగా కనిపిస్తాయి ఆ 2 అంశాలు అదే ప్రారంభ జాబితాలో ఉన్నాయి. 15 మరియు 16 రెండూ ఎడమవైపు జాబితాలో ఉన్నాయి. ట్రిక్ రెండు జాబితాలు ఇప్పటికే క్రమబద్ధీకరించబడతాయి వాస్తవం యొక్క సౌలభ్యాన్ని పొందాలి. దీని అర్థం మేమిద్దరమూ జాబితాలు మొదటి అంశాలు విషయంలో చూస్తే - ఇక్కడ, 4 మరియు 8 - వాటిలో ఒకటి కూడా విలీనమైన జాబితా యొక్క మొదటి మూలకం ఉండాలి. Well, ఎందుకు అని? ఈ జాబితాలు రెండు ఇప్పటికే క్రమబద్ధీకరించబడతాయి, మేము 2 జాబితాలు మిశ్రమంలో మరియు కనుక 4 లేదా 8 గాని చిన్న మూలకం ఉండాలి. ఈ సందర్భంలో, చిన్న, 4 ఉంటుంది కాబట్టి మేము 4 చేద్దామని మరియు మా విలీనమైన జాబితా యొక్క మొదటి మూలకం చేయవచ్చు. ఇప్పుడు మేము మొదటి జాబితాలో మిగిలిన 3 అంశాలను విలీనం కొనసాగుతుంది మరియు రెండవ జాబితాలో 4 అంశాలను. 

మరోసారి, మేము రెండు జాబితాలు మొదటి మూలకం వద్ద చూడవలసిన అవసరం. 2 చిన్న మా విలీనమైన జాబితాలో రెండవ మూలకం ఉండాలి. ఈ సమయంలో, 8 మరియు 15 మధ్య చిన్న 8, కావున మేము ఇన్సర్ట్ ఆ మా క్రమబద్ధీకరించబడతాయి జాబితాలో రెండవ మూలకం వంటి. మేము రెండు జాబితాలు మొదటి అంశాలను పోల్చి కొనసాగించవచ్చు మరియు 2 చిన్న తొలగించడం. 15 మరియు 23, 15 పోల్చడం చిన్న మరియు అందువలన యొక్క మా మూడవ అంశం. ఇప్పుడు 16 పోల్చడం మరియు 23, 16 తక్కువగా ఉంది. కాబట్టి ఆ నాలుగో ఎలిమెంట్. 

2 అంశాలు వరుసగా ఒకే జాబితా నుండి వచ్చిన గమనించండి. ఈ ఎందుకు విలీనమైన జాబితా 2 జాబితాల నుండి కేవలం ప్రత్యామ్నాయ అంశాలు కాదు. 50 మరియు 23, 23 పోల్చడం చిన్న, కాబట్టి మేము ఆ ఎంచుకోండి. 50 మరియు 42 మధ్య, 42 తక్కువగా ఉంది. 50 మరియు 108 మధ్య, 50 తక్కువగా ఉంది. మరియు, చివరకు, మేము 108 కలిగి ఉంటాయి, కాబట్టి అది మా జాబితా చివరిలో వెళ్ళి ఉండాలి. మేము ఒక మంచి, క్రమబద్ధీకరించబడింది జాబితా గమనించండి. మేము 2 జాబితాలు మొదటి 2 అంశాలు పోలిస్తే ప్రతి సమయం మేము విలీనమైన జాబితా యొక్క తదుపరి మూలకం గుర్తించగలిగారు. ఉంటే ఇది తుది జాబితా n ఇక్కడ 8 ఉన్న n సంఖ్యలు కలిగి అర్థం అప్పుడు మేము స్థానంలో ఆ సంఖ్యల అన్ని పొందడానికి అత్యంత n పోలికలు వద్ద ఉంది. ఇటువంటి యాంత్రిక పద్ధతి సరళ సమయంలో అమలు చెబుతారు కానీ ఇక్కడ గురించి ఆందోళన చెందకండి. 

విలీనం కోసం మా అల్గారిథమ్ ఉపయోగించి, మేము ఒక ఫాస్ట్ విలీనంతో విధమైన అల్గోరిథం చేయవచ్చు. కాబట్టి, మా యొక్క జాబితాలు రీసెట్ తెలియజేయండి. విలీనంతో విధమైన ప్రక్రియలో 2 పెద్ద దశలు ఉన్నాయి. మొదటి, నిరంతరం భాగాలుగా విడదీస్తుంది cups జాబితా విభజించబడింది మేము వాటిని కేవలం 1 కప్ తో జాబితాలు ఒక సమూహం వరకు. జాబితా బేసి సంఖ్యను కలిగి, చింతించకండి మరియు మీరు వాటిని మధ్య పూర్తిగా శుభ్రం కట్ చేయలేరు. జస్ట్ ఏకపక్ష అదనపు కప్ సైన్ ఉన్నాయి ఏ జాబితా ఎంచుకోండి కాబట్టి, ఈ యొక్క జాబితాలు విభజించబడింది తెలియజేయండి. ఇప్పుడు మేము 2 జాబితాలు ఉన్నాయి. ఇప్పుడు మేము 4 జాబితాలు ఉన్నాయి. 

ఇప్పుడు మేము ప్రతి జాబితాలో ఒకే కప్ తో 8 జాబితాలు ఉన్నాయి. కాబట్టి ఆ దశ 1 కోసం ఇది. దశ 2 కోసం, మేము పదేపదే మేము ముందు నేర్చుకున్న విలీనంతో అల్గారిథమ్ ఉపయోగించి జాబితాల జోడీకి విలీనం. 108 మరియు 15 విలీనం, మేము జాబితా 15, 108 తో ముగుస్తుంది. 50 మరియు 4 విలీనం, మేము 4, 50 తో ముగుస్తుంది. 8 మరియు 42 విలీనం, మేము, 8 తో 42 ముగుస్తుంది. మరియు 23 మరియు 16 విలీనం, మేము, 16 తో 23 ముగుస్తుంది. ఇప్పుడు మా జాబితాలు పరిమాణం 2 యొక్క ఉన్నాయి. 4 జాబితాలు ప్రతి క్రమబద్ధీకరించబడింది గమనించాలి. 

కాబట్టి మేము మళ్ళీ జాబితాల జోడీకి విలీనం చెయ్యవచ్చు. 15 మరియు 108 మరియు 4 మరియు 50 విలీనం - మొదటి అప్పుడు 108, అప్పుడు 50, అప్పుడు 15, 4 పడుతుంది. 8, 42 మరియు 16, 23, విలీనం మేము మొదటి అప్పుడు అప్పుడు 8, 16, 23, 42 పడుతుంది. కాబట్టి ఇప్పుడు మేము పరిమాణం 4 కేవలం 2 జాబితాలను కలిగి, ప్రతి ఒక్కటి క్రమబద్ధీకరించబడింది. కాబట్టి ఇప్పుడు మేము ఈ 2 జాబితాలు విలీనం. మొదటి మేము 4 పడుతుంది. అప్పుడు మేము 8 పడుతుంది. అప్పుడు మేము 15 మరియు అప్పుడు అప్పుడు 16, 23, 42, 50, 108 పడుతుంది. మరియు మేము పూర్తి చేసిన. మేము ఇప్పుడు ఒక క్రమబద్ధీకరించబడతాయి జాబితా. కాబట్టి ఈ ఖచ్చితంగా, ఎంత వేగంగా ఉంది? సాంకేతిక పరంగా, విలీనం విధమైన, O (N log N) ఉంది బబుల్ సార్ట్, చొప్పించడం విధమైన, మరియు ఎంపిక విధమైన అన్ని O కాగా (n ²). మీరు వెంటనే నేర్చుకోవచ్చు నిజానికి,, మీరు ఒక విధమైన పైకి రావటానికి చెయ్యలేరు సాధారణ కేసులో O (N log N) కంటే మెరుగ్గా పని చేస్తాయి. మీరు ఇంకా అది చూడలేదు మళ్లీ, ఈ పెద్ద O సంజ్ఞామానం గురించి ఆందోళన చెందకండి. 

మేము చాల పెద్ద జాబితా క్రమం కోరుకుంటే ఈ అర్థం తెలిసిన బబుల్ సార్ట్, చొప్పించడం విధమైన, మరియు ఎంపిక విధమైన సమర్థవంతంగా పడుతుంది గణనీయంగా ఎక్కువ విధమైన విలీనం కంటే. ఇది విలీనంతో విధమైన వేగంగా అన్ని జాబితాలు అర్థం లేదు లేదా ఒక నిర్దిష్ట పరిమాణం కింద ఏ ఒక్క జాబితా కోసం. ఉదాహరణకు, చొప్పించడం విధమైన 5 అంశాలు కంటే చిన్న అన్ని జాబితాలు వేగంగా విధమైన కావచ్చు. ఆచరణలో, విలీనం విధమైన 50 అంశాలను వంటి చిన్న చిన్న జాబితాలు సాధారణంగా వేగంగా ఉంది. 

కానీ ఈ అదనపు వేగం ధర లేకుండా రాదు. మా ఇతర రకాల వలె కాకుండా, స్థానంలో జాబితా జాబితా తీసుకొని సవరించండి మేము ఒక క్రమబద్ధీకరించబడతాయి జాబితా వచ్చేవరకు, విలీనం విధమైన కొన్ని అదనపు జాగా కావాలి కలిసి 2 జాబితాలు విలీనం. మేము వెంటనే విలీనమైన జాబితా నిల్వ విలీనం చేసిన జాబితాలు ఉపయోగించలేరు మేము ఇంకా విలీనం చేయడానికి అవసరమైన అంశాలను భర్తీ చెల్లదు కాబట్టి. ఈ స్థలం ఒక ధర ఒక బిట్, కానీ అది సాధారణంగా అసమంజసమైన కాదు. మరియు ఆ విలీనంతో విధమైన కోసం ఇది. 

నా పేరు రాబ్ బౌడెన్, మరియు ఈ CS50 ఉంది. [CS50.TV] - మరియు ఎంపిక విధమైన. [నవ్విన] ఓహ్, నేను దీనిని ఎలా మారారు ఎందుకంటే కూడా తీసుకోవాల్సి వచ్చింది. ఎడమవైపు జాబితా. ఒక అక్షర దోషం ఉంది. [Misspoke] నేను ఇరుక్కొనిపోయింది - [నవ్విన] నేను ఏమి లేదు -