Ընտրեք տեսակավորման c կոդը: Ընտրության տեսակավորում. Նվազագույն տարրը գտնելու մեթոդ

Դաս շարքից՝ «Ծրագրավորում Պասկալում»

Բազմաթիվ խնդիրների լուծման ժամանակ տեղեկատվության մշակման և որոնման գործընթացն ավելի արագ և արդյունավետ է, եթե տվյալները դասավորված են որոշակի հերթականությամբ: Օրինակ՝ ուսանողների, ուսանողների, աշխատողների տարբեր ցուցակներ՝ այբբենական կարգով, թվային տվյալներ բարձրից ցածր (կամ հակառակը) և այլն։

Կան բավականին մի քանի տարբեր մեթոդներ զանգվածների տեսակավորում, որոնք միմյանցից տարբերվում են արդյունավետության աստիճանով, որը հասկացվում է որպես տեսակավորման գործընթացում կատարված համեմատությունների և փոխանակումների քանակ։ Եկեք մանրամասն քննարկենք դրանցից մի քանիսը:

Զանգվածի տեսակավորում՝ օգտագործելով պարզ ընտրության մեթոդը

ժամը զանգվածների տեսակավորումԸնտրության մեթոդը օգտագործում է հիմնական ալգորիթմը առավելագույն (նվազագույն) տարրը և դրա թիվը գտնելու համար:

Ընտրության մեթոդով զանգվածը դասավորելու ալգորիթմ.

1. Բնօրինակ զանգվածի համար ընտրեք առավելագույն տարրը:
2. Փոխեք այն վերջին տարրի հետ (դրանից հետո ամենամեծ տարրը կկանգնի իր տեղում):
3. Կրկնել p.p. 1-2 մնացած n-1 տարրերով, այսինքն՝ դիտարկենք զանգվածի մի մասը՝ սկսած առաջին տարրից մինչև նախավերջին տարրը, գտի՛ր նրանում առավելագույն տարրը և այն փոխանակի՛ր նախավերջին (n-1) -րդով։ զանգվածի տարրը, այնուհետև մնացած (n-2 )-տարրերը և այլն, մինչև մնա մեկ տարր, որն արդեն տեղում է:

Զանգվածը տեսակավորելու համար կպահանջվեն (n-1) զանգվածի որոնումներ: Տեսակավորման գործընթացում զանգվածի տեսակավորված մասը կավելանա, իսկ չտեսակավորված մասը համապատասխանաբար կնվազի։

Երբ տվյալները տեսակավորվում են, փոփոխականների բովանդակությունը փոխանակվում է: Փոխանակման համար դուք պետք է ստեղծեք ժամանակավոր փոփոխական, որը կպահի փոփոխականներից մեկի բովանդակությունը: Հակառակ դեպքում դրա բովանդակությունը կկորչի:

Առաջադրանք 1. 10 տարրերից բաղկացած զանգվածը դասավորել աճման կարգով` օգտագործելով պարզ թվարկում:

Եկեք ընթացակարգ գրենք. Դրա համար մուտքային պարամետրը կլինի զանգված: Դա կլինի նաև ելքային պարամետրը: Հետևաբար, մենք այն նկարագրում ենք որպես փոփոխական պարամետր (հետ հիմնաբառ var).

Ընթացակարգում i-ի արտաքին օղակը որոշում է զանգվածի դիտարկվող մասի երկարությունը: Այն n-ից կփոխվի 2-ի:

j-ի վրայի ներքին օղակն օգտագործվում է առավելագույն տարրը և դրա թիվը գտնելու համար: Որպես առավելագույնի սկզբնական արժեք՝ ողջամիտ է վերցնել զանգվածի դիտարկվող մասի վերջին տարրի արժեքը։

Ծրագրի կոդըընթացակարգեր:

Հիմնական ծրագրի ծրագրային կոդը.

Ընտրության մեթոդով զանգվածում տարրերը աճման կարգով դասավորելու գործընթացը.

Զանգվածը նվազման կարգով պատվիրելիս պետք է տեղափոխել նվազագույն տարրը: Ինչու՞ առավելագույն տարրը գտնելու ալգորիթմում բավական է «>» նշանը փոխել նշանի «<«.

Զանգվածի տեսակավորում՝ օգտագործելով պարզ փոխանակման մեթոդը (փուչիկների մեթոդ)

Ամենահայտնի տեսակավորման մեթոդը փուչիկների տեսակավորումն է: Նրա ժողովրդականությունը պայմանավորված է իր գրավիչ անունով և պարզ ալգորիթմով:

Մեթոդը հիմնված է այն բանի վրա, որ ալգորիթմի կատարման ընթացքում աստիճանաբար «առաջանում են» զանգվածի «թեթև» տարրերը։

Այս մեթոդի առանձնահատկությունը ոչ թե յուրաքանչյուր տարրի համեմատությունն է բոլորի հետ, այլ հարևան տարրերի զույգերի համեմատությունը: Զանգվածի մի քանի հաջորդական սկանավորումներ կատարվում են սկզբից մինչև վերջ։ Եթե ​​հարակից տարրերը գտնվում են «սխալ», ապա դրանք փոխանակվում են:

Զանգվածը աճման կարգով դասավորելու ալգորիթմ՝ օգտագործելով պարզ փոխանակման մեթոդը.

1. Սկսենք զննարկել տարրերի առաջին զույգից (a և a): Եթե ​​այս զույգի առաջին տարրը մեծ է երկրորդից, ապա մենք դրանք փոխանակում ենք, հակառակ դեպքում թողնում ենք անփոփոխ։ Այնուհետև վերցնում ենք տարրերի երկրորդ զույգը (ա և ա), եթե երկրորդը մեծ է երրորդից, ապա դրանք նույնպես փոխում ենք, ապա համեմատում ենք երրորդն ու չորրորդը, իսկ եթե երրորդը մեծ է չորրորդից, ապա դրանք փոխում ենք։ , և այլն։ Վերջում համեմատում ենք (n-1)-րդ և n-րդ տարրերը:Զանգվածի առաջին անցման ժամանակ կուսումնասիրվեն զանգվածի բոլոր զույգերը a[i] և a i-ի համար 1-ից մինչև (n-1): . Արդյունքում զանգվածի առավելագույն տարրը կտեղափոխվի զանգվածի վերջ։
2. Քանի որ ամենամեծ տարրն իր տեղում է, դիտարկենք զանգվածի այն մասը առանց դրա, այսինքն՝ առաջինից մինչև (n-1) -րդ տարրը։Կրկնեք զանգվածի այս մասի նախորդ քայլերը՝ արդյունքում։ որը զանգվածի երկրորդ ամենամեծ տարրը կտեղափոխվի զանգվածի դիտարկվող մասի վերջին տեղը, այսինքն՝ (n-1) - e տեղ ամբողջ զանգվածում։
3. Այս գործողությունները շարունակվում են այնքան ժամանակ, մինչև զանգվածի ընթացիկ մասի տարրերի թիվը կրճատվի երկուսի: Այս դեպքում դուք պետք է կատարեք վերջին համեմատությունը և պատվիրեք վերջին երկու տարրերը:

Հեշտ է հասկանալ, որ n տարրից բաղկացած զանգվածը փոխակերպելու համար անհրաժեշտ է n–1 անգամ նայել դրա միջով՝ ամեն անգամ մեկ տարրով նվազեցնելով դիտման տիրույթը։

Ստորև բերված է պղպջակների մեթոդով զանգվածը աճման կարգով դասավորելու ընթացակարգի տեքստը:

Զանգվածի տարրերն իրենց արժեքների նվազման կարգով դասավորելու համար զանգվածի տարրերը համեմատելիս «>» նշանը պետք է փոխարինել «.<«.

Զանգվածում տարրերը աճման կարգով դասավորելու գործընթացը՝ օգտագործելով փոխանակման մեթոդը.

Ստորև նկարագրված բոլոր մեթոդները պետք է դիտարկվեն որպես մեթոդի հատուկ տարբերակներ, որոնք հայտնի են որպես ուղղակի ընտրության մեթոդկամ տեսակավորում ըստ ընտրության. Այս մեթոդների ընդհանրությունն այն է, որ գտնենք (ընտրենք) զանգվածի առավելագույն կամ նվազագույն տարրերը և տեղադրել դրանք հաջորդական զանգվածի բջիջներում:

Նվազագույն տարրը գտնելու մեթոդ

Այս մեթոդի էությունը (նկատի ունենալով մեր դիտարկվող թվային օրինակի համար ընտրված սահմանափակումները) հետևյալն է.

Առաջին քայլում զանգվածի և դրա ինդեքսի բոլոր թվերի միջև նվազագույն թիվը հայտնաբերվում և պահվում է փոփոխականում, օրինակ՝ Xmin, իսկ դրա ինդեքսը պահվում է մեկ այլ փոփոխականում, օրինակ՝ Imin-ում, այնուհետև գտնված նվազագույն թիվը։ զանգվածում փոխանակվում է զանգվածի առաջին տարրի հետ՝ X:=X ; X:=Xmin;.

Մեր օրինակում Xmin=15 նվազագույն թիվը գտնվում է Imin=3 բջիջում, և առաջին և նվազագույն թվերի փոխանակումը կհանգեցնի հետևյալ արդյունքին.

i=3-ով ստանում ենք Xmin=21 և Imin=4, իսկ փոխարկումից հետո

i=5-ով ստանում ենք Xmin=34 և Imin=5, իսկ փոխարկումից հետո

Այսպիսով, արտաքին օղակը պետք է կատարվի n-1 անգամ, իսկ ներքին օղակի կատարումների թիվը n-1-ից կնվազի 1-ի: Զանգվածը նվազման կարգով տեսակավորելու համար գտնված առաջին նվազագույն թիվը պետք է փոխանակվի վերջինի հետ: մեկը, երկրորդը՝ նախավերջինով և այլն։

Տարրերի որոնման առավելագույն մեթոդ

Այս մեթոդը նախորդից տարբերվում է միայն նրանով, որ հայտնաբերվել են առավելագույն տարրեր: Այս մեթոդներն իրականացնելիս ցիկլերի միևնույն կազմակերպմամբ դրանք ուղիղ հակառակ արդյունքներ կտան՝ եթե մեկը տանում է զանգվածում թվերի ավելացման, ապա մյուսը հանգեցնում է նվազման և հակառակը։

Ինդեքսների որոնման մեթոդ նվազագույն տարր

Այս մեթոդը տարբերվում է նվազագույն տարրի և դրա ինդեքսի որոնման մեթոդից նրանով, որ ներքին օղակն օգտագործվում է միայն նվազագույն տարրի ինդեքսը որոնելու համար, ուստի զանգվածի թվերի փոխարկումները յուրաքանչյուր քայլում i, i=1, 2: , ..., n-1-ը պետք է կատարվի լրացուցիչ փոփոխականի միջոցով, օրինակ՝ R: R:=X[i]; X[i]:=X; X:=R;.

Առավելագույն տարրի ինդեքսը գտնելու մեթոդ

Այս մեթոդը նախորդից տարբերվում է միայն նրանով, որ գտնվել է առավելագույն տարրի ինդեքսը։ Այս մեթոդներն իրականացնելիս ցիկլերի միևնույն կազմակերպմամբ դրանք ուղիղ հակառակ արդյունքներ կտան՝ եթե մեկը տանում է զանգվածում թվերի ավելացման, ապա մյուսը հանգեցնում է նվազման և հակառակը։

Ալգորիթմներ և տվյալների կառուցվածքներ սկսնակների համար. տեսակավորում

Նիկիտա Պրիյացելյուկ

Այս մասում մենք կանդրադառնանք զանգվածում տվյալների տեսակավորման հինգ հիմնական ալգորիթմներին: Սկսենք ամենապարզից՝ պղպջակային տեսակավորումից, և ավարտենք «արագ տեսակավորումով» (արագ տեսակավորում).

Յուրաքանչյուր ալգորիթմի համար, բացի դրա գործողությունը բացատրելուց, մենք նաև նշում ենք նրա հիշողությունը և ժամանակի բարդությունը վատագույն, լավագույն և միջին դեպքերում:

Տես նաև այս շարքի այլ նյութեր., և.

Փոխանակման մեթոդ

Կոդը պարզեցնելու և ընթեռնելիությունը բարելավելու համար մենք կներկայացնենք Swap մեթոդը, որը կփոխանակի զանգվածի արժեքներն ըստ ինդեքսների:

Անվավեր փոխանակում (T տարրեր, int ձախ, int աջ) (եթե (ձախ != աջ) (T temp = տարրեր; տարրեր = տարրեր; տարրեր = ջերմաստիճան; ))

պղպջակների տեսակավորում

Bubble տեսակավորումը ամենապարզ տեսակավորման ալգորիթմն է: Այն մի քանի անգամ պտտվում է զանգվածի միջով, յուրաքանչյուր քայլում ամենամեծ չտեսակավորված արժեքը տեղափոխելով զանգվածի վերջ:

Օրինակ, մենք ունենք ամբողջ թվերի զանգված.

Զանգվածի միջով առաջին անցնելիս մենք համեմատում ենք 3 և 7 արժեքները: Քանի որ 7-ը մեծ է 3-ից, մենք դրանք թողնում ենք այնպես, ինչպես կան: Այնուհետև մենք համեմատում ենք 7-ը և 4-ը: 4-ը փոքր է 7-ից, ուստի մենք դրանք փոխանակում ենք՝ յոթը մեկ դիրքով մոտեցնելով զանգվածի վերջին: Այժմ այն ​​ունի հետևյալ տեսքը.

Այս գործընթացը կրկնվում է այնքան ժամանակ, մինչև յոթը հասնի զանգվածի գրեթե ավարտին: Վերջում այն ​​համեմատվում է 8-րդ տարրի հետ, որն ավելի մեծ է, ինչը նշանակում է, որ փոխանակում չկա։ Այն բանից հետո, երբ մենք մեկ անգամ պտտեցինք զանգվածը, այն նման է հետևյալին.

Քանի որ տեղի է ունեցել արժեքների առնվազն մեկ փոխանակում, մենք պետք է ևս մեկ անգամ կրկնենք զանգվածի վրա: Այս անցման արդյունքում 6 թիվը տեղափոխում ենք իր տեղը։

Եվ կրկին, առնվազն մեկ փոխանակում է կատարվել, ինչը նշանակում է, որ մենք նորից անցնում ենք զանգվածով:

Հաջորդ անցման ժամանակ փոխանակումը չի կատարվում, ինչը նշանակում է, որ մեր զանգվածը տեսակավորված է, և ալգորիթմն ավարտել է իր աշխատանքը։

Public void Sort(T տարրեր) ( bool swapped; do ( swapped = false; for (int i = 1; i< items.Length; i++) { if (items.CompareTo(items[i]) >0) (Փոխանակում (տարրեր, i - 1, i); փոխանակված = ճշմարիտ; ) ) ) while (swapped != false); )

Տեղադրման տեսակավորում

Տեղադրման տեսակավորումն աշխատում է զանգվածի միջով կրկնելով և ցանկալի արժեքը զանգվածի սկիզբ տեղափոխելով: Հաջորդ դիրքը մշակելուց հետո մենք գիտենք, որ բոլոր դիրքերը մինչ այն դասավորված են, իսկ դրանից հետո՝ ոչ:

Կարևոր կետ. insertion sort-ը մշակում է զանգվածի տարրերը հերթականությամբ: Քանի որ ալգորիթմը կրկնվում է տարրերի միջով ձախից աջ, մենք գիտենք, որ ընթացիկ ինդեքսի ձախ կողմում գտնվող ամեն ինչ արդեն տեսակավորված է: Այս նկարը ցույց է տալիս, թե ինչպես է զանգվածի տեսակավորված մասը աճում յուրաքանչյուր անցումով.

Աստիճանաբար մեծանում է զանգվածի տեսակավորված մասը, և վերջում զանգվածը կպատվիրվի։

Եկեք նայենք կոնկրետ օրինակ. Ահա մեր չտեսակավորված զանգվածը, որը մենք կօգտագործենք.

Ալգորիթմը սկսվում է 0 ինդեքսից և 3 արժեքից: Քանի որ սա առաջին ինդեքսն է, զանգվածը մինչև այն ներառյալ համարվում է տեսակավորված:

Այս փուլում տեսակավորվում են 0..1 ինդեքսներով տարրերը, իսկ 2..n ինդեքս ունեցող տարրերի մասին ոչինչ հայտնի չէ։

Հաջորդը ստուգվում է 4 արժեքը։ Քանի որ այն յոթից պակաս է, մենք պետք է այն տեղափոխենք ճիշտ դիրք՝ զանգվածի տեսակավորված մասում։ Հարցը մնում է՝ ինչպե՞ս սահմանել այն։ Սա կատարվում է FindInsertionIndex մեթոդով։ Այն համեմատում է իրեն փոխանցված արժեքը (4) տեսակավորված մասի յուրաքանչյուր արժեքի հետ, մինչև տեղադրելու տեղ գտնի։

Այսպիսով, մենք գտանք 1 ինդեքսը (3-ի և 7-ի արժեքների միջև): Insert մեթոդը կատարում է ներդիր՝ հեռացնելով զետեղվող արժեքը զանգվածից և տեղափոխելով բոլոր արժեքները՝ սկսած ներդիրի ինդեքսից, դեպի աջ: Այժմ զանգվածն ունի հետևյալ տեսքը.

Այժմ զանգվածի այն մասը, որը սկսվում է զրոյական տարրից և ավարտվում 2 ինդեքսով տարրով, տեսակավորված է։ Հաջորդ անցումը սկսվում է 3-րդ ինդեքսից և 4-րդ արժեքից: Քանի որ ալգորիթմն աշխատում է, մենք շարունակում ենք կատարել այս ներդիրները:

Երբ այլևս ներդիրներ չկան, զանգվածը համարվում է ամբողջությամբ տեսակավորված, և ալգորիթմն ավարտված է։

Public void Sort(T տարրեր) ( int sortedRangeEndIndex = 1; while (sortedRangeEndIndex< items.Length) { if (items.CompareTo(items) < 0) { int insertIndex = FindInsertionIndex(items, items); Insert(items, insertIndex, sortedRangeEndIndex); } sortedRangeEndIndex++; } } private int FindInsertionIndex(T items, T valueToInsert) { for (int index = 0; index < items.Length; index++) { if (items.CompareTo(valueToInsert) >0) ( վերադարձի ինդեքս; ) ) նետել նոր InvalidOperationException("The insertion index was not found"); ) private void Insert(T itemArray, int indexInsertingAt, int indexInsertingFrom) ( // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // // Գործողություններ. // 1: Պահպանել ընթացիկ ինդեքսը դեպի temp // 2. Փոխարինել indexInsertingAt ինդեքսովInsertingFrom // 3. Փոխարինել indexInsertingAt ինդեքսով InsertingFrom +1 դիրքում // Տեղափոխել տարրերը ձախ մեկով: // 4. Գրել temp-ը զանգվածի դիրքում + 1: // Քայլ 1. T temp = itemArray; // Քայլ 2. itemArray = itemArray; // Քայլ 3. համար (int current = indexInsertingFrom; ընթացիկ > indexInsertingAt; current--) ( itemArray = itemArray; ) // Քայլ 4. itemArray = temp; )

Ընտրության տեսակավորում

Սելեկցիոն տեսակավորումը մի տեսակ հիբրիդ է փուչիկների տեսակավորման և ներդրման տեսակավորման միջև: Ինչպես փուչիկների տեսակավորումը, այս ալգորիթմը նորից ու նորից կրկնվում է զանգվածի միջով՝ մեկ արժեք տեղափոխելով ճիշտ դիրք: Այնուամենայնիվ, ի տարբերություն փուչիկների տեսակավորման, այն ամենամեծի փոխարեն ընտրում է ամենափոքր չտեսակավորված արժեքը: Ինչպես ներդրման տեսակավորման դեպքում, զանգվածի պատվիրված մասը գտնվում է սկզբում, իսկ փուչիկներով տեսակավորման դեպքում՝ վերջում:

Տեսնենք, թե ինչպես է աշխատում ընտրության տեսակավորումը մեր չտեսակավորված զանգվածի վրա:

Առաջին անցման ժամանակ ալգորիթմը օգտագործում է FindIndexOfSmallestFromIndex մեթոդը՝ զանգվածի ամենափոքր արժեքը գտնելու և այն սկզբին տեղափոխելու համար։

Նման փոքր զանգվածով մենք կարող ենք անմիջապես ասել, որ ամենափոքր արժեքը 3-ն է, և այն արդեն ճիշտ դիրքում է: Այս պահին մենք գիտենք, որ զանգվածի առաջին դիրքը (ինդեքս 0) ամենափոքր արժեքն է, ուստի զանգվածի սկիզբն արդեն տեսակավորված է։ Հետևաբար, մենք սկսում ենք երկրորդ անցումը, այս անգամ 1-ից մինչև n-1 ցուցանիշներով:

Երկրորդ անցման ժամանակ մենք որոշում ենք, որ ամենափոքր արժեքը 4-ն է: Մենք այն փոխում ենք երկրորդ տարրի հետ՝ յոթ, որից հետո 4-ը դառնում է իր ճիշտ դիրքը:

Այժմ զանգվածի չտեսակավորված մասը սկսվում է 2-րդ ինդեքսից: Ալգորիթմի յուրաքանչյուր անցումով այն աճում է մեկ տարրով: Եթե ​​որևէ անցումով մենք մեկ փոխանակում չենք կատարել, դա նշանակում է, որ զանգվածը տեսակավորված է:

Եվս երկու անցումներից հետո ալգորիթմն ավարտում է իր աշխատանքը.

Public void Sort(T տարրեր) ( int sortedRangeEnd = 0; while (sortedRangeEnd< items.Length) { int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd); Swap(items, sortedRangeEnd, nextIndex); sortedRangeEnd++; } } private int FindIndexOfSmallestFromIndex(T items, int sortedRangeEnd) { T currentSmallest = items; int currentSmallestIndex = sortedRangeEnd; for (int i = sortedRangeEnd + 1; i < items.Length; i++) { if (currentSmallest.CompareTo(items[i]) >0) ( currentSmallest = կետեր[i]; currentSmallestIndex = i; ) ) վերադարձնել ընթացիկSmallestIndex; )

Միաձուլման տեսակավորում

Բաժանիր և տիրիր

Մինչ այժմ մենք դիտարկել ենք գծային ալգորիթմներ: Նրանք օգտագործում են քիչ լրացուցիչ հիշողություն, բայց ունեն քառակուսի բարդություն: Որպես օրինակ օգտագործելով միաձուլման տեսակավորումը, մենք կդիտարկենք բաժանիր և տիրիր ալգորիթմին: (բաժանիր և տիրիր).

Այս տիպի ալգորիթմներն աշխատում են՝ մեծ խնդիրը բաժանելով ավելի փոքր խնդիրների, որոնք ավելի հեշտ է լուծել: Մենք դրանք օգտագործում ենք ամեն օր։ Օրինակ, հեռախոսի գրքի որոնումը նման ալգորիթմի օրինակներից մեկն է:

Եթե ​​ուզում ես Պետրով անունով մարդ գտնել, չես սկսում որոնել A տառով սկսելով ու մեկ էջը թերթելով։ Դուք, ամենայն հավանականությամբ, գիրքը կբացեք ինչ-որ տեղ մեջտեղում։ Եթե ​​սեղմեք T-ն, մի քանի էջ հետ կշրջեք, գուցե չափազանց շատ, O-ի վրա: Այնուհետև կգնաք առաջ: Այսպիսով, գնալով ավելի քիչ թվով էջեր, դուք ի վերջո կգտնեք ճիշտը:

Որքանո՞վ են արդյունավետ այս ալգորիթմները:

Ենթադրենք, հեռախոսի գրքում կա 1000 էջ։ Եթե ​​բացեք այն մեջտեղում, ապա 500 էջ եք հեռացնում, որտեղ չկա այն մարդը, ում փնտրում եք: Եթե ​​դուք չեք հասել ցանկալի էջ, ճիշտ եք ընտրում կամ ձախ կողմև կրկին թողնել առկա տարբերակների կեսը: Այժմ դուք պետք է դիտեք 250 էջ: Այսպիսով, մենք նորից ու նորից կիսում ենք մեր առաջադրանքը և կարող ենք հեռախոսի գրքում մարդ գտնել ընդամենը 10 հարվածից: Սա էջերի ընդհանուր թվի 1%-ն է, որոնք մենք պետք է նայենք գծային որոնման ընթացքում:

Միաձուլման տեսակավորում

Միաձուլման տեսակավորման միջոցով մենք զանգվածը կիսում ենք կիսով չափ, մինչև յուրաքանչյուր հատվածը ունենա մեկ տարր: Այնուհետև այդ հատվածները ճիշտ հերթականությամբ վերադարձվում են տեղում (միաձուլվում):

Եկեք նայենք այսպիսի զանգվածին.

Եկեք կիսենք այն.

Եվ յուրաքանչյուր մասը կիսելու ենք կիսով չափ, մինչև մնան մեկ տարր ունեցող մասեր.

Այժմ, երբ մենք զանգվածը բաժանել ենք հնարավորինս կարճ մասերի, մենք դրանք միաձուլում ենք ճիշտ հերթականությամբ:

Սկզբում մենք ստանում ենք երկու տեսակավորված տարրերից բաղկացած խմբեր, այնուհետև դրանք «հավաքում» ենք չորս տարրերից բաղկացած խմբերի և վերջում ամեն ինչ հավաքում ենք դասավորված զանգվածով։

Որպեսզի ալգորիթմը աշխատի, մենք պետք է իրականացնենք հետևյալ գործողությունները.

1. Զանգվածը խմբերի ռեկուրսիվորեն բաժանելու գործողություն (տեսակավորման մեթոդ):
2. Միաձուլումը ճիշտ հերթականությամբ (Merge մեթոդ):

Հարկ է նշել, որ, ի տարբերություն գծային տեսակավորման ալգորիթմների, միաձուլման տեսակավորումը կբաժանի և սոսնձի զանգվածը՝ անկախ նրանից՝ այն ի սկզբանե տեսակավորված էր, թե ոչ։ Ուստի, չնայած այն հանգամանքին, որ ներս վատագույն դեպքումայն կաշխատի ավելի արագ, քան գծայինը, լավագույն դեպքում դրա կատարումը ցածր կլինի, քան գծայինը: Հետևաբար, միաձուլման տեսակավորումը ամենաշատը չէ Լավագույն որոշումըերբ դուք պետք է տեսակավորեք մասամբ պատվիրված զանգվածը:

Public void Sort(T տարրեր) ( if (item.Length<= 1) { return; } int leftSize = items.Length / 2; int rightSize = items.Length - leftSize; T left = new T; T right = new T; Array.Copy(items, 0, left, 0, leftSize); Array.Copy(items, leftSize, right, 0, rightSize); Sort(left); Sort(right); Merge(items, left, right); } private void Merge(T items, T left, T right) { int leftIndex = 0; int rightIndex = 0; int targetIndex = 0; int remaining = left.Length + right.Length; while(remaining >0) ( if (leftIndex >= ձախ. Երկարություն) ( տարրեր = աջ; ) else if (աջԻնդեքս >= աջ. Երկարություն) ( տարրեր = ձախ; ) else if (ձախ. Համեմատել Դեպի (աջ)< 0) { items = left; } else { items = right; } targetIndex++; remaining--; } }

Արագ տեսակավորում

Quicksort-ը «բաժանիր և նվաճիր» ալգորիթմի այլ տեսակ է: Այն աշխատում է՝ կրկնելով հետևյալ քայլերը ռեկուրսիվ կերպով.

1. Ընտրեք հիմնական ինդեքսը և դրանով զանգվածը բաժանեք երկու մասի։ Դա կարելի է անել տարբեր ճանապարհներ, բայց այս հոդվածում մենք օգտագործում ենք պատահական թիվ։
2. Բանալից մեծ բոլոր տարրերը զանգվածի աջ կողմ տեղափոխեք, իսկ բանալինից փոքր բոլոր տարրերը դեպի ձախ: Այժմ առանցքային տարրը ճիշտ դիրքում է. այն ավելի մեծ է, քան ձախ կողմում գտնվող ցանկացած տարր, և պակաս, քան աջ կողմում գտնվող ցանկացած տարր:
3. Կրկնեք առաջին երկու քայլերը, մինչև զանգվածը ամբողջությամբ դասավորված լինի:

Տեսնենք, թե ինչպես է ալգորիթմն աշխատում հետևյալ զանգվածի վրա.

Նախ, մենք պատահականորեն ընտրում ենք հիմնական տարրը.

Int pivotIndex = _pivotRng.Next(ձախ, աջ);

Այժմ, երբ մենք գիտենք հիմնական ինդեքսը (4), մենք վերցնում ենք այս ինդեքսի արժեքը (6) և արժեքները փոխանցում զանգվածում այնպես, որ բանալինից մեծ կամ հավասար թվերը լինեն աջ կողմում, իսկ բոլոր թվերը: ստեղներից պակաս են ձախ կողմում: Նկատի ունեցեք, որ առանցքային տարրի ինդեքսը կարող է փոխվել արժեքների փոխանցման ժամանակ (սա շուտով կտեսնենք):

Արժեքները տեղափոխվում են բաժանման մեթոդով:

Այս պահին մենք գիտենք, որ 6 արժեքը ճիշտ դիրքում է: Այժմ մենք կրկնում ենք այս գործընթացը զանգվածի աջ և ձախ կողմերի համար:

Մենք ռեկուրսիվ կերպով անվանում ենք արագ տեսակավորման մեթոդ յուրաքանչյուր մասի վրա: Ձախ կողմի հիմնական տարրը հինգն է: Արժեքները տեղափոխելիս այն կփոխի իր ինդեքսը: Հիմնական բանը հիշելն է, որ մեզ համար կարևոր է առանցքային արժեքն ու ոչ թե դրա ցուցանիշը։

Կրկին կիրառել արագ տեսակավորում.

Եվս մեկ անգամ.

Մեզ մնացել է մեկ չտեսակավորված արժեք, և քանի որ գիտենք, որ մնացած ամեն ինչ արդեն տեսակավորված է, ալգորիթմն ավարտվում է։

Պատահական _pivotRng = նոր Պատահական(); հանրային դատարկ տեսակավորում (T տարրեր) ( արագ տեսակավորում (տարրեր, 0, տարրեր. Երկարությունը - 1);< right) { int pivotIndex = _pivotRng.Next(left, right); int newPivot = partition(items, left, right, pivotIndex); quicksort(items, left, newPivot - 1); quicksort(items, newPivot + 1, right); } } private int partition(T items, int left, int right, int pivotIndex) { T pivotValue = items; Swap(items, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { if (items[i].CompareTo(pivotValue) < 0) { Swap(items, i, storeIndex); storeIndex += 1; } } Swap(items, storeIndex, right); return storeIndex; }

Եզրակացություն

Սա ավարտում է սկսնակների համար ալգորիթմների և տվյալների կառուցվածքների վերաբերյալ մեր հոդվածների շարքը: Այս ընթացքում մենք լուսաբանել ենք կապակցված ցուցակները, դինամիկ զանգվածները, երկուական որոնման ծառերը և հավաքածուները C# կոդի օրինակներով:

Թերևս տեսակավորման ամենապարզ ալգորիթմը ընտրության տեսակավորումն է: Դատելով սորտի անունից՝ անհրաժեշտ է ինչ-որ բան ընտրել (զանգվածի առավելագույն կամ նվազագույն տարրերը)։ Ընտրության տեսակավորման ալգորիթմը գտնում է աղբյուրի զանգվածի առավելագույն կամ նվազագույն տարրերը՝ կախված նրանից, թե ինչպես է անհրաժեշտ դասավորել զանգվածը՝ աճման կամ նվազման կարգով: Եթե ​​զանգվածը պետք է տեսակավորվի աճման կարգով, ապա նվազագույն տարրերը պետք է ընտրվեն սկզբնական զանգվածից։ Եթե ​​զանգվածը պետք է տեսակավորվի նվազման կարգով, ապա պետք է ընտրել առավելագույն տարրերը:

Ենթադրենք, մենք պետք է դասավորենք զանգվածը աճման կարգով: Բնօրինակ զանգվածում մենք գտնում ենք նվազագույն տարրը, այն փոխանակում զանգվածի առաջին տարրի հետ: Արդեն զանգվածի բոլոր տարրերից մեկ տարր իր տեղում է։ Այժմ կդիտարկենք զանգվածի չտեսակավորված մասը, այսինքն՝ զանգվածի բոլոր տարրերը, բացառությամբ առաջինի։ Զանգվածի չտեսակավորված մասում մենք կրկին փնտրում ենք նվազագույն տարրը։ Գտնված նվազագույն տարրը փոխարինվում է զանգվածի երկրորդ տարրով և այլն։ Այսպիսով, ընտրության տեսակավորման ալգորիթմի էությունը զանգվածի չտեսակավորված մասում նվազագույն (առավելագույն) տարրերի բազմիցս որոնումն է։ Տեսակավորենք յոթ թվերից բաղկացած զանգվածը՝ ըստ «Ընտրության տեսակավորում» ալգորիթմի։

բնօրինակ զանգված՝ 3 3 7 1 2 5 0
1) Այսպիսով, մենք գտնում ենք զանգվածի նվազագույն տարրը: 0-ը նվազագույն տարրն է
2) Փոխանակեք զանգվածի նվազագույն և առաջին տարրերը:
Ընթացիկ զանգված՝ 0 3 7 1 2 5 3
3) Գտեք զանգվածի չտեսակավորված մասի նվազագույն տարրը: 1 - նվազագույն տարր
4) Փոխանակե՛ք զանգվածի նվազագույն և առաջին տարրերը:
Ընթացիկ զանգված՝ 0 1 7 3 2 5 3
5) min = 2
6) Ընթացիկ զանգված՝ 0 1 2 3 7 5 3
7) min = 3
8) Ընթացիկ զանգված. 0 1 2 3 7 5 3 զանգվածում ոչինչ չի փոխվել, քանի որ 3-ն իր տեղում է
9) min = 3
10) Զանգվածի վերջնական ձևը՝ 0 1 2 3 3 5 7 - զանգվածը տեսակավորված է

Եկեք ծրագրավորենք ընտրության տեսակավորման ալգորիթմը C++-ում։

// sorting_choices.cpp. սահմանում է կոնսոլային հավելվածի մուտքի կետը: #include "stdafx.h" #include #ներառում #ներառում օգտագործելով namespace std; void ChoicesSort(int*, int); // ընտրության տեսակավորման ֆունկցիայի նախատիպ int main (int argc, char* argv) ( srand (time (NULL)); setlocale (LC_ALL, «rus»); cout<< "Введите размер массива: "; int size_array; // длинна массива cin >> չափի_զանգված; int *sorted_array = new int ; // միաչափ դինամիկ զանգված (int counter = 0; counter< size_array; counter++) { sorted_array = rand() % 100; // заполняем массив պատահական թվերկոուտ<< setw(2) << sorted_array << " "; // вывод массива на экран } cout << "\n\n"; choicesSort(sorted_array, size_array); // вызов функции сортировки выбором for (int counter = 0; counter < size_array; counter++) { cout << setw(2) << sorted_array << " "; // печать отсортированного массива } cout << "\n"; delete sorted_array; // высвобождаем память system("pause"); return 0; } void choicesSort(int* arrayPtr, int length_array) // сортировка выбором { for (int repeat_counter = 0; repeat_counter < length_array; repeat_counter++) { int temp = arrayPtr; // временная переменная для хранения значения перестановки for (int element_counter = repeat_counter + 1; element_counter < length_array; element_counter++) { if (arrayPtr >arrayPtr) ( temp = arrayPtr; arrayPtr = arrayPtr; arrayPtr = ջերմաստիճան; ) ))

Ընտրության տեսակավորման ալգորիթմը հիմնված է առավելագույն (նվազագույն) տարրը գտնելու ալգորիթմի վրա։ Փաստորեն, որոնման ալգորիթմը ընտրության տեսակավորման ամենակարևոր մասն է: Քանի որ տեսակավորման հիմնական խնդիրը զանգվածի տարրերը պատվիրելն է, պետք է կատարվեն փոխարկումներ։ Տեսակավորված զանգվածի տարրերի արժեքների փոխանակումը տեղի է ունենում տող 48—50 . Եթե ​​փոխեք > նշանը տող 46պակաս նշան, ապա զանգվածը կդասավորվի նվազման կարգով: Ծրագրի արդյունքը ներկայացված է Նկար 1-ում:

Նկար 1 - Ընտրության տեսակավորում

Ենթադրվում է, որ կենտրոնացված համակարգիչները տվյալների տեսակավորման վրա ծախսում են ժամանակի մինչև քառորդ մասը: Դա պայմանավորված է նրանով, որ շատ ավելի հեշտ է նախապես տեսակավորված զանգվածում արժեք գտնել: Թե չէ որոնումը մի քիչ նման է խոտի դեզում ասեղ փնտրելուն։

Կան ծրագրավորողներ, ովքեր իրենց ողջ աշխատանքային ժամանակը ծախսում են տեսակավորման ալգորիթմների ուսումնասիրության և ներդրման վրա։ Դա պայմանավորված է նրանով, որ բիզնեսում ծրագրային ապահովման ճնշող մեծամասնությունը ներառում է տվյալների բազայի կառավարում: Մարդիկ անընդհատ տեղեկատվություն են փնտրում տվյալների բազաներում: Սա նշանակում է, որ որոնման ալգորիթմները մեծ պահանջարկ ունեն:

Բայց կա մեկ «բայց». Որոնման ալգորիթմները շատ ավելի արագ են աշխատում տվյալների բազաների հետ, որոնք արդեն տեսակավորված են: Այս դեպքում պահանջվում է միայն գծային որոնում:

Մինչ համակարգիչները ժամանակի որոշ կետերում առանց օգտվողների են, տեսակավորման ալգորիթմները շարունակում են աշխատել տվյալների բազաների հետ: Հերթական անգամ մտնում են որոնողները, և տվյալների բազան արդեն տեսակավորվել է այս կամ այն ​​որոնման նպատակի հիման վրա:

Այս հոդվածը ներկայացնում է ստանդարտ տեսակավորման ալգորիթմների իրականացման օրինակներ:

Ընտրության տեսակավորում

Զանգվածն աճման կարգով դասավորելու համար անհրաժեշտ է յուրաքանչյուր կրկնության ժամանակ գտնել ամենամեծ արժեք ունեցող տարրը։ Դրա հետ դուք պետք է փոխեք վերջին տարրը: Ամենաբարձր արժեք ունեցող հաջորդ տարրը դառնում է նախավերջին: Դա պետք է տեղի ունենա այնքան ժամանակ, քանի դեռ զանգվածի առաջին տեղերում գտնվող տարրերը պատշաճ կարգի մեջ չեն:

C++ կոդը

void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i տվյալներ[k])( j = k; ) ) tmp = տվյալներ[i]; տվյալներ[i] = տվյալներ[j]; տվյալներ [j] = tmp; ))

Պղպջակների տեսակավորում

Bubble տեսակավորումը համեմատում է հարակից տարրերը և փոխանակում, եթե հաջորդ տարրը նախորդից փոքր է: Պահանջում է տվյալների միջոցով բազմաթիվ անցումներ: Առաջին անցման ժամանակ զանգվածի առաջին երկու տարրերը համընկնում են: Եթե ​​դրանք շարքից դուրս են, դրանք փոխվում են, ապա հաջորդ զույգի տարրերը համեմատվում են: Նույն պայմանով նրանք նույնպես փոխում են տեղերը։ Այսպիսով, տեսակավորումը տեղի է ունենում յուրաքանչյուր ցիկլում մինչև զանգվածի վերջը հասնելը:

C++ կոդը

void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i =(i+1);j--)(եթե (տվյալներ[j]

Տեղադրման տեսակավորում

Տեղադրման տեսակավորումը զանգվածը բաժանում է երկու շրջանի՝ պատվիրված և չպատվիրված: Սկզբում ամբողջ զանգվածը չպատվիրված տարածք է: Առաջին անցման ժամանակ չպատվիրված շրջանից առաջին տարրը հանվում և տեղադրվում է պատվիրված շրջանում ճիշտ դիրքում:

Յուրաքանչյուր անցումով պատվիրված շրջանի չափը մեծանում է 1-ով, իսկ չպատվիրված շրջանի չափը կրճատվում է 1-ով:

Հիմնական հանգույցն անցնում է 1-ից N-1 միջակայքում: j-րդ կրկնության ժամանակ [i] տարրը տեղադրվում է դասավորված տարածքում ճիշտ դիրքում: Դա արվում է կարգավորված շրջանի բոլոր տարրերը, որոնք մեծ են [i] մեկ դիրքից դեպի աջ: [i]-ը տեղադրվում է այն տարրերի միջև, որոնք փոքր են [i]-ից և մեծ են [i]-ից:

C++ կոդը

void SortAlgo::insertionSort(int data, int lenD) ( int key = 0; int i = 0; for (int j = 1; j =0 && data[i]>բանալին) (տվյալներ = տվյալներ[i]; i = i-1; տվյալներ=բանալին; ) )

Միաձուլման տեսակավորում

C++ կոդը

void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int միջին = lenD/2; int rem = lenD-middle; int * L = new int; int * R = նոր int; for ( int i=0;i

Արագ տեսակավորում

Quicksort-ը օգտագործում է բաժանիր և տիրիր ալգորիթմը: Այն սկսվում է սկզբնական զանգվածը երկու շրջանի բաժանելով: Այս մասերը գտնվում են նշված տարրի ձախ և աջ կողմում, որը կոչվում է առանցք: Գործընթացի վերջում մի մասը կպարունակի առանցքից փոքր տարրեր, իսկ մյուս մասը՝ առանցքայինից մեծ տարրեր:

C++ կոդը

void SortAlgo::quickSort(int * տվյալներ, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0, k = 0; եթե (lenD>1) (int * L = նոր int; int * R = նոր int; առանցք = տվյալ; համար (i=0;i