Կան մի քանի հիմնական ալգորիթմներ զանգվածի տեսակավորման խնդիրը լուծելու համար: Դրանցից ամենահայտնիներից մեկը ներդիրային տեսակն է: Իր պարզության և պարզության, բայց ցածր արդյունավետության շնորհիվ այս մեթոդը կիրառվում է հիմնականում ծրագրավորման դասավանդման ժամանակ։ Այն թույլ է տալիս հասկանալ հիմնական տեսակավորման մեխանիզմները:
Ալգորիթմի նկարագրություն
Ներդիրների տեսակավորման ալգորիթմի էությունն այն է, որ սկզբնական զանգվածի ներսում ձևավորվում է ճիշտ դասավորված հատված: Յուրաքանչյուր տարր մեկ առ մեկ համեմատվում է ստուգված մասի հետ և տեղադրվում է ճիշտ տեղում: Այսպիսով, բոլոր տարրերը կրկնելուց հետո դրանք շարվում են ճիշտ հերթականությամբ։
Էլեմենտների ընտրության հերթականությունը կարող է լինել ցանկացած, դրանք կարող են ընտրվել կամայականորեն կամ ըստ ինչ-որ ալգորիթմի։ Ամենից հաճախ հաջորդական թվարկումն օգտագործվում է զանգվածի սկզբից, որտեղ ձևավորվում է դասավորված հատված։
Տեսակավորման սկիզբը կարող է այսպիսի տեսք ունենալ.
- Վերցրեք զանգվածի առաջին տարրը:
- Քանի որ դրա հետ համեմատելու ոչինչ չկա, վերցրեք տարրն ինքնին, ինչպես պատվիրված էհաջորդականություն.
- Անցնել երկրորդ կետին։
- Համեմատե՛ք այն առաջինի հետ՝ հիմնվելով տեսակավորման կանոնի վրա։
- Անհրաժեշտության դեպքում փոխեք տարրերը տեղերով:
- Վերցրեք առաջին երկու տարրերը որպես դասավորված հաջորդականություն:
- Անցեք երրորդ կետին:
- Համեմատե՛ք այն երկրորդի հետ, անհրաժեշտության դեպքում փոխե՛ք։
- Եթե փոխարինումն արված է, համեմատեք այն առաջինի հետ։
- Վերցրեք երեք տարր որպես դասավորված հաջորդականություն:
Եվ այսպես մինչև սկզբնական զանգվածի ավարտը:
Իրական կյանքում ներդրման տեսակավորում
Հստակության համար արժե օրինակ բերել, թե ինչպես է այս տեսակավորման մեխանիզմն օգտագործվում առօրյա կյանքում:
Վերցրեք, օրինակ, դրամապանակը: Հարյուր, հինգ հարյուր և հազար դոլարանոց թղթադրամները անսարք են թղթադրամների խցիկում։ Սա խառնաշփոթ է, նման հովանոցում դժվար է անմիջապես գտնել ճիշտ թղթի կտորը: Թղթադրամների զանգվածը պետք է տեսակավորված լինի։
Առաջինը 1000 ռուբլիանոց թղթադրամ է, իսկ դրանից անմիջապես հետո՝ 100։ Վերցնում ենք հարյուրը և դնում դիմացը։ Երրորդն անընդմեջ 500 ռուբլի է, դրա արժանի տեղը հարյուրից հազար է։
Նույն ձևով մենք դասավորում ենք ստացված քարտերը «Fool» խաղալիս՝ դրանցով նավարկելը հեշտացնելու համար։
Օպերատորներ և օգնական գործառույթներ
Ներդրման տեսակավորման մեթոդը որպես մուտք է վերցնում տեսակավորվող սկզբնական զանգվածը, համեմատության ֆունկցիան և, անհրաժեշտության դեպքում, գործառույթը, որը որոշում է տարրերի թվարկման կանոնը: Ամենից հաճախ օգտագործվում է դրա փոխարենսովորական հանգույցի հայտարարություն։
Առաջին տարրն ինքնին կարգավորված բազմություն է, ուստի համեմատությունը սկսվում է երկրորդից:
Ալգորիթմը հաճախ օգտագործում է օգնական ֆունկցիա երկու արժեք փոխանակելու համար (փոխանակում): Այն օգտագործում է լրացուցիչ ժամանակավոր փոփոխական, որը սպառում է հիշողությունը և մի փոքր դանդաղեցնում կոդը:
Այլընտրանքն է զանգվածային տեղաշարժը տարրերի խումբը և այնուհետև ընթացիկը ազատ տարածության մեջ մտցնելը: Այս դեպքում անցումը հաջորդ տարրին տեղի է ունենում, երբ համեմատությունը տվել է դրական արդյունք, որը ցույց է տալիս ճիշտ հերթականությունը։
Իրականացման օրինակներ
Հատուկ իրականացումը մեծապես կախված է օգտագործվող ծրագրավորման լեզվից, դրա շարահյուսությունից և կառուցվածքներից:
Դասական C-ի իրականացում՝ օգտագործելով ժամանակավոր փոփոխական՝ արժեքները փոխանակելու համար.
int i, j, temp; համար (i=1; i =0; j--) { if (զանգված[j] < ջերմաստիճան) ընդմիջում; զանգված[j + 1]=զանգված[j]; զանգված[j]=ջերմաստիճան; } }
PHP իրականացում.
function insertion_sort(&$a) { համար ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Այստեղ, նախ, բոլոր տարրերը, որոնք չեն համապատասխանում տեսակավորման պայմանին, տեղափոխվում են աջ, այնուհետև ընթացիկ տարրը տեղադրվում է ազատ տարածության մեջ:
Java կոդը՝ օգտագործելով while loop՝
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Կոդի ընդհանուր իմաստը մնում է անփոփոխ. զանգվածի յուրաքանչյուր տարր հաջորդաբար համեմատվում է նախորդների հետ և անհրաժեշտության դեպքում փոխարինվում նրանց հետ:
Գնահատված գործարկման ժամանակը
Ակնհայտ է, որ լավագույն դեպքում ալգորիթմի մուտքագրումը կլինի արդեն իսկ ճիշտ ձևով պատվիրված զանգված։ Այս իրավիճակում ալգորիթմը պարզապես պետք է ստուգի յուրաքանչյուր տարր՝ համոզվելու համար, որ այն ճիշտ տեղում է՝ առանց փոխանակումներ կատարելու: Այսպիսով, գործարկման ժամանակը ուղղակիորեն կախված կլինի սկզբնական զանգվածի երկարությունից O(n).
Վատագույն դեպքում մուտքագրումը հակադարձ կարգով դասավորված զանգվածն է: Սա կպահանջի մեծ թվով փոխարկումներ, գործարկման ժամանակի ֆունկցիան կախված կլինի քառակուսի տարրերի քանակից:
Լրիվ չդասավորված զանգվածի փոխարկումների ճշգրիտ թիվը կարելի է հաշվարկել՝ օգտագործելով բանաձևը՝
n(n-1)/2
որտեղ n-ը սկզբնական զանգվածի երկարությունն է: Այսպիսով, 100 տարրը ճիշտ հերթականությամբ դասավորելու համար կպահանջվի 4950 փոխարկում։
Ներդիր մեթոդը շատ արդյունավետ է փոքր կամ մասամբ տեսակավորված զանգվածները տեսակավորելու համար: Այնուամենայնիվ, խորհուրդ չի տրվում այն կիրառել ամենուր՝ հաշվարկների մեծ բարդության պատճառով։
Ալգորիթմն օգտագործվում է որպես օժանդակ շատ այլ ավելի բարդ տեսակավորման մեթոդներում:
Տեսակավորել հավասար արժեքներ
Տեղադրման ալգորիթմը պատկանում է այսպես կոչված կայուն տեսակներին։ Դա նշանակում է,որ այն չի փոխանակում նույնական տարրերը, այլ պահպանում է դրանց սկզբնական կարգը։ Կայունության ինդեքսը շատ դեպքերում կարևոր է ճիշտ պատվիրելու համար:
Վերոնշյալը պարի մեջ ներդիրի տեսակավորման հիանալի տեսողական օրինակ է:
