Տեղադրման տեսակավորումը տեսակավորման մեկ այլ պարզ ալգորիթմ է, ինչպիսին է Փուչիկների տեսակավորում. Հնարավոր է, որ դուք չգիտեիք, բայց դուք պետք է օգտագործեիք Տեղադրման տեսակավորումը ձեր կյանքի շատ վայրերում: Իրական աշխարհում Տեղադրման տեսակավորման լավագույն օրինակներից է ՝ ինչպես եք դասավորում ձեր ձեռքը խաղաքարտերում. Դուք վերցնում եք մեկ քարտ տախտակամածից, ենթադրում եք, որ այն դասավորված է, և մենք հաջորդ քարտերը տեղադրում ենք իրենց համապատասխան դիրքում: Օրինակ, եթե ձեր առաջին քարտը Jackեքն է, իսկ հաջորդ քարտը `Թագուհին, ապա թագուհուն դնում եք afterեքի հետևից: Այժմ, եթե հաջորդ քարտը թագավորն է, մենք այն դնում ենք թագուհու հետևից, իսկ եթե ստանում ենք 9, ապա դնում ենք այն jack- ից առաջ:

Այսպիսով, եթե ուշադիր նայեք, Տեղադրման տեսակավորումը տեսակավորման կատարյալ ալգորիթմ է `արդեն իսկ նոր արժեք տեղադրելու համար դասավորված զանգված: Ահա թե ինչու է տեղադրման տեսակավորման ամենալավ բարդությունը Վրա), որի դեպքում կարող եք պարզապես նոր թիվ տեղադրել արդեն դասավորված ամբողջ թվերի ցանկում:

Մեկ այլ բան, որը պետք է հիշել, ցանկի չափն է, տեղադրման տեսակավորումը շատ լավ է փոքր ցուցակի կամ զանգվածի համար, բայց ոչ այնքան մեծ ցուցակի դեպքում, որտեղ QuickSort, MergeSort և HeapSort կանոնները:

Եկեք տեսնենք իրական կյանքից տեղադրման տեսակավորման ևս մեկ օրինակ: Նկատե՞լ եք, ինչպես են դերձակները դասավորում հաճախորդների շապիկները իրենց զգեստապահարանում, ըստ չափի: Այսպիսով, նրանք տեղադրում են նոր վերնաշապիկ համապատասխան դիրքում, դրա համար նրանք տեղաշարժում են գոյություն ունեցող վերնաշապիկները, մինչև չեն գտնում համապատասխան տեղը:

Եթե ​​զգեստապահարանը համարում եք զանգված, իսկ վերնաշապիկները `որպես տարր, ապա կպարզեք, որ մենք պետք է տեղաշարժենք առկա տարրերը` նոր տարրի համար ճիշտ տեղը գտնելու համար: Սա է ներդրման տեսակավորման ալգորիթմի առանցքը, եթե դուք հասկանում եք այս օրինակները, նույնիսկ դուք կարող եք գալ կոդավորման քայլ առ քայլ ալգորիթմ ՝ Java- ում տեղադրման տեսակավորման միջոցով ամբողջ թվերի զանգված դասավորելու համար:

Այս հոդվածում մենք կսովորենք, որ նախ հասկանալով ներդիրը դասակարգել հոսքի գծապատկերով և քայլելով օրինակով: Այդ գրելուց հետո, տեղադրման տեսակավորումը կատարելու Java մեթոդը շատ հեշտ կլինի:

Btw, Եթե դուք տվյալների կառուցվածքի և ալգորիթմների լիարժեք սկսնակ եք, ապա առաջարկում եմ միանալ նման համապարփակ դասընթացին Տվյալների կառուցվածքներ և ալգորիթմներ. Deep Dive Using Java Udemy- ի վրա, որը ոչ միայն կսովորեցնի Տեղադրման տեսակավորման ալգորիթմները, այլև տվյալների այլ էական կառուցվածքը և տեսակավորման ալգորիթմները: Այս թեմայով իմ ամենասիրած դասընթացներից է

Ինչպես է գործում Տեղադրման տեսակավորման ալգորիթմը

Եթե ​​գիտեք, թե ինչպես կարելի է տեսակավորել ձեռքի քարտերը, գիտեք, թե ինչպես է աշխատում տեղադրման տեսակավորումը. բայց շատ ծրագրավորողների համար հեշտ չէ իրական աշխարհի գիտելիքները թարգմանել աշխատանքային կոդի օրինակով:

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

Հիմա, ինչպես եք դասավորում ամբողջ թվերի զանգվածը օգտագործելով այս ալգորիթմը Կարող եք ասել, որ մենք կարող ենք այս զանգվածին վերաբերվել որպես քարտերի տախտակամած, և մենք կօգտագործենք մեկ այլ զանգված `տարրը մի տեղից մյուսը ընտրելու և տեղադրելու համար: Դե, դա կաշխատի, բայց դա տարածության վատնում է (հիշողություն), քանի որ այն, ինչ դուք անում եք, համեմատում և փոխում է, ինչը նույնպես հնարավոր է անել տեղում նույն զանգվածում:

Ահա, քայլ առ քայլ ուղեցույց Java- ում տեղադրման տեսակավորման ալգորիթմի կոդավորման համար:

1) Համարեք, որ առաջին տարրը դասավորված է և այն գտնվում է պատշաճ տեղում, դա ձեր զանգվածի 0 ինդեքսն է:

2) Այժմ անցեք երկրորդ տարրին (զանգվածի ինդեքս 1) և համեմատեք այն ձեր ձեռքի հետ (զանգվածի այն հատվածը, որն արդեն դասավորված է): Սա նշանակում է, որ դուք համեմատում եք այս տարրը հետընթաց դեպի ինդեքս զրո:

3) Եթե ընթացիկ թիվը նախորդից փոքր է (որը տեղին է), մենք պետք է դրանից առաջ դնենք մեր ընթացիկ թիվը: Ինչպե՞ս կանենք դա: Դե դրա համար մենք պետք է տեղափոխենք առկա թիվը:

Բայց ի՞նչ կլինի, եթե կա մեկ այլ տարր, որն ավելի մեծ է, քան մեր ներկայիս տարրը: Դա նշանակում է, որ մենք պետք է շարունակենք համեմատությունը, քանի դեռ չենք գտել մեր ներկա համարի համապատասխան տեղը, ինչը կրկին նշանակում է ընթացիկ համար> առկա թիվ կամ մենք ցուցակի սկզբում ենք (ինդեքս 0 զանգվածում):

4) needանկի բոլոր թվերի համար պետք է կրկնել այս գործընթացը: Դա ավարտելուց հետո դուք ունեք տեսակավորված ցուցակ կամ զանգված:

Մի խոսքով, տեղադրման տեսակավորումը ամեն ինչի մասին է ընթացիկ թվի համապատասխան տեղը գտնելը. Երբ գտնեք համապատասխան տեղը, դուք պետք է տեղաշարժեք առկա տարրը ՝ այս նոր համարի համար տեղ ստեղծելու համար: Եթե ​​ցանկանում եք ավելին իմանալ Տեղադրման տեսակավորման և տեսակավորման այլ ալգորիթմների մասին, կարող եք նաև տեսնել դասընթացը Ալգորիթմներ և տվյալների կառուցվածքներ – մաս 1 և 2 կամ նման լավ գիրք Ալգորիթմներ Nutshell- ում որը ֆանտաստիկ դասընթաց է համակարգչային գիտության կարևոր ալգորիթմներ սովորելու համար:

Տեղադրման տեսակավորման ալգորիթմի տեսողական բացատրություն

Այդպես է ասված «Նկարը հազար բառ արժե», սա միանգամայն ճիշտ է տեսակավորման ալգորիթմները հասկանալու դեպքում: Ավելի վաղ մենք տեսել էինք, թե որքան հեշտ էր դա հասկանալ QuickSort ալգորիթմը ՝ օգտագործելով GIF պատկերը, և այժմ մենք նորից կսովորենք, թե ինչպես է աշխատում Տեղադրման տեսակավորումը ՝ հետևելով այս գծապատկերին: Այս օրինակով չափազանց պարզ է դառնում բացատրելը, թե ինչպես է գործում ներդիրի տեսակավորումը:

Այստեղ մենք ունենք ինչպես դրական, այնպես էլ բացասական թվերի մի ամբողջ շարք պատահական կարգով: Մեր խնդիրն է տեսակավորել այս չտեսակավորված զանգվածը ՝ օգտագործելով Insertion Sort in աճման կարգով, ինչը նշանակում է, որ ամենափոքր տարրը պետք է լինի զանգվածի սկզբում, իսկ ամենամեծ տարրը `զանգվածի վերջում:

Աշխատանքը սկսելու համար մենք ենթադրում ենք, որ մեր առաջին տարրը գտնվում է ճիշտ դիրքում (հիշեք ձեր ձեռքի առաջին քարտը) և սկսեք երկրորդ ամբողջ թվից, որը -5 է: Այժմ մենք այն համեմատում ենք 7 -ի հետ, քանի որ – 5 -ը 7 -ից փոքր է, մենք նախ 7 -ը տեղափոխում ենք -5 -ի փոխարեն:

Դրանից հետո մենք կարիք չունենք -5 -ը համեմատելու որևէ այլ թվի հետ, որովհետև մենք հասել ենք ձախ սահմանին, ուստի ներկայիս տեղում կդնենք -5 -ը: Այժմ մենք ընտրում ենք երրորդ տարրը, որը 2 -ն է: Մենք համեմատում ենք 2 -ը 7 -ի հետ և պարզեցինք, որ 2 -ը նույնպես 7 -ից փոքր է, ինչը նշանակում է, որ 7 -ը տեղափոխվել է 2 -ի փոխարեն:

Հաջորդը, մենք համեմատում ենք 2 -ը -5 -ի հետ, այժմ 2 -ը մեծ է -5 -ից, ուստի այն տեղադրում ենք այս վայրում: Դրանից հետո մենք ընտրում ենք չորրորդ տարրը, որը 16 -ն է: Քանի որ 16 -ը 7 -ից մեծ է, ոչ մեկին տեղաշարժելու կարիք չկա, 16 -ը կմնա իր տեղում:

Այժմ վերջին 4 -րդ տարրը, 16 -ից պակաս է, 16 -ը կտեղափոխվի 4 -ի փոխարեն, հաջորդը մենք 4 -ը համեմատում ենք 7 -ի հետ, կրկին 4 -ը պակաս է, քան 7 -ը կտեղափոխվի, սրանից հետո մենք 4 -ը համեմատում ենք 2 -ի հետ, վա it’sյ, 2 -ից մեծ է: , ուստի մենք գտել ենք համապատասխան տեղ 4. -ի համար: Մենք այնտեղ տեղադրում ենք 4 -ը: Այժմ զանգված չկա, այլևս զանգված չկա մեր զանգվածը այժմ դասավորված է.

Բացատրություն, թե ինչպես է աշխատում Տեղադրման տեսակավորման ալգորիթմը

Դուք կարող եք տեսնել, որ վերջին քայլին մեր զանգվածը դասավորված է աճման կարգով `սկսած – 5 -ից և ավարտվում 16 -ով:

Ի դեպ, ալգորիթմները կարող են ավելի լավ հասկանալ ՝ դիտելով հոսքի գծապատկերը կամ իրական օրինակ ՝ թվերով կամ միանալով լավ առցանց դասընթացին, ինչպիսին է Տվյալների կառուցվածքների և ալգորիթմների արտացոլում Java- ում, որը նաև հիանալի միջոց է տվյալների հիմնական կառուցվածքը և ալգորիթմները սովորելու համար:

Տեղադրման տեսակավորումը Java- ում `օրինակով

Շատ հեշտ է իրականացնել Տեղադրման տեսակավորումը Java- ում: Մնում է միայն կրկնել զանգվածի վրայով և գտնել յուրաքանչյուր տարրի համապատասխան դիրքը, դրա համար անհրաժեշտ է տեղաշարժել տարրը, և դա կարող եք անել փոխանակելով: Տեղադրման տեսակավորման ալգորիթմի միջոցով ամբողջ զանգվածը տեսակավորելու տրամաբանությունը մեթոդի ներսում է insertionSort (ներ[]).

Java- ում կարող եք նաև տեսակավորել ցանկացած օբյեկտ, օրինակ ՝ String այս ալգորիթմի միջոցով, այն ամենը, ինչ ձեզ հարկավոր է անել ՝ օգտագործել a Համեմատելի ինտերֆեյս քանի որ դա ձեզ կտրամադրի մեխանիզմ ՝ համեմատելու երկու օբյեկտ: Այժմ> (մեծից) կամ <(փոքրից) օպերատոր օգտագործելու փոխարեն, մենք պետք է օգտագործենք համեմատել () մեթոդը:

Դրա համար մենք որոշեցինք ծանրաբեռնել մեր insertionSort () մեթոդը, որտեղ գերծանրաբեռնված տարբերակը վերցնում է օբյեկտի զանգված ՝ an- ի փոխարեն ներ զանգված Երկու մեթոդներն էլ տեսակավորում են տարրերը ՝ օգտագործելով տեղադրման տեսակավորման տրամաբանությունը:

Ի դեպ, իրական աշխարհում պետք չէ անիվը նորից հորինել, java.util.Ararays class- ն ապահովում է զանգվածների վրա աշխատելու մի քանի օգտակար մեթոդ, որոնցից մեկը տեսակավորումն է:

Կա մի քանի գերբեռնված տարբերակ տեսակավորել () պարզունակ և օբյեկտային զանգվածների տեսակավորման մեթոդ: Այս մեթոդը օգտագործում է կրկնակի առանցք QuickSort պարզունակ զանգվածը տեսակավորելու և MergeSort դեպի տեսակավորել օբյեկտների զանգվածը.

Ամեն դեպքում, ահա մեր ամբողջական կոդի օրինակը ՝ Java- ում Insertion sort- ը գործարկելու համար: Եթե ​​դուք օգտագործում եք Eclipse IDE, ապա պարզապես պատճենեք և տեղադրեք կոդը src ձեր Java ծրագրի և Eclipse- ի թղթապանակը ինքնին կստեղծի նույն անունով փաթեթներ և աղբյուրի ֆայլեր: Մնում է միայն այն գործարկել որպես Java ծրագիր:

import java.util.Arrays;

/**
 * Java program to sort an array using Insertion sort algorithm.
 * Insertion sort works great with already sorted, small arrays but 
 * not suitable for large array with random order.
 *
 * @author Javin Paul
 */
public class InsertionSort {

  public static void main(String args[]) {

  // getting unsorted integer array for sorting
  int[] randomOrder = getRandomArray(9);
  System.out.println("Random Integer array before Sorting : " 
                          + Arrays.toString(randomOrder));

  // sorting array using insertion sort in Java
  insertionSort(randomOrder);
  System.out.println("Sorted array uisng insretion sort : " 
                            + Arrays.toString(randomOrder));

  // one more example of sorting array using insertion sort
  randomOrder = getRandomArray(7);
  System.out.println("Before Sorting : " + Arrays.toString(randomOrder));
  insertionSort(randomOrder);
  System.out.println("After Sorting : " + Arrays.toString(randomOrder));

  // Sorting String array using Insertion Sort in Java
  String[] cities = {"London", "Paris", "Tokyo", "NewYork", "Chicago"};
  System.out.println("String array before sorting : "
                           + Arrays.toString(cities));
  insertionSort(cities);

  System.out.println("String array after sorting : " 
                           + Arrays.toString(cities));
  }

  public static int[] getRandomArray(int length) {
    int[] numbers = new int[length];
    for (int i = 0; i < length; i++) {
      numbers[i] = (int) (Math.random() * 100);
    }
    return numbers;
  }

  /*
  * Java implementation of insertion sort algorithm to sort
  * an integer array.
  */
  public static void insertionSort(int[] array) {
  // insertion sort starts from second element
  for (int i = 1; i < array.length; i++) {
    int numberToInsert = array[i];

    int compareIndex = i;
    while (compareIndex > 0 && array[compareIndex - 1] > numberToInsert) {
       array[compareIndex] = array[compareIndex - 1]; // shifting element
       compareIndex--; // moving backwards, towards index 0
    }

    // compareIndex now denotes proper place for number to be sorted
     array[compareIndex] = numberToInsert;
   }
 }

  /*
  * Method to Sort String array using insertion sort in Java.
  * This can also sort any object array which implements
  * Comparable interface.
  */
  public static void insertionSort(Comparable[] objArray) {
  // insertion sort starts from second element
  for (int i = 1; i < objArray.length; i++) {
      Comparable objectToSort = objArray[i];

      int j = i;
      while (j > 0 && objArray[j - 1].compareTo(objectToSort) > 1) {
         objArray[j] = objArray[j - 1];
         j--;
      }
     objArray[j] = objectToSort;
   }
 }

}

Output:
Random Integer array before Sorting : [74, 87, 27, 6, 25, 94, 53, 91, 15]
Sorted array uisng insretion sort : [6, 15, 25, 27, 53, 74, 87, 91, 94]
Before Sorting : [71, 5, 60, 19, 4, 78, 42]
After Sorting : [4, 5, 19, 42, 60, 71, 78]
String array before sorting : [London, Paris, Tokyo, NewYork, Chicago]
String array after sorting : [Chicago, London, NewYork, Paris, Tokyo]

Այս օրինակից սովորելու ևս մեկ օգտակար բան է ինչպես ստեղծել պատահական թվեր Java- ում. Դուք կարող եք տեսնել, որ մեր getRandomArray (երկարություն int) մեթոդը ստեղծում է տվյալ երկարության պատահական զանգված:

Սա օգտագործում է ստատիկ օգտակարության մեթոդը Math.random () որը կրկնակի արժեք է վերադարձնում 0.0 -ից 0.1 -ի միջև, եթե ձեզ անհրաժեշտ է այն վերածել ամբողջի, 0 -ից 99 -ի սահմաններում, այն պետք է բազմապատկել 100 -ով: Դրանից հետո կարող եք այն գցել ներ տասնորդականներից ազատվելու համար:

Այսքանը դրա մասին է Տեղադրման տեսակավորում Java- ում. Դա իսկապես գեղեցիկ ալգորիթմներից մեկն է և լավագույնս աշխատում է արդեն դասավորված ցուցակի համար: Այն ունի բազմաթիվ գործնական օգտագործում, բայց ունի նաև սահմանափակումներ: Թվերի մեծ ցուցակը տեսակավորելու համար չպետք է օգտագործեք Տեղադրման տեսակավորում, քանի որ դրա լավագույն դեպքում կատարումը ըստ կարգի է Վրա), որը կարող է շատ բարձր լինել ասենք 1 միլիոն ամբողջ թվերի ցուցակի համար:

Այդ ցուցակները կարճացնելու համար ձեզ հարկավոր են տեսակավորման ալգորիթմներ, որոնք ունեն լոգարիթմական բարդություն. O (nNogn), քանի որ տեղեկամատյանը նվազեցնում է ուժը 10^ն մեջ n մոտ 1 միլիոն կդառնա 10^6 նշանակում է 6.

Որպեսզի հիշեք Insertion տեսակավորման ալգորիթմը, պարզապես հիշեք, թե ինչպես եք դասավորում ձեր ձեռքը պոկերում կամ քարտային ցանկացած խաղում: Եթե ​​դա կոշտ է, պարզապես հիշեք, թե ինչպես եք ձեր վերնաշապիկները դասավորում զգեստապահարանում:

Այլ զանգվածների վրա հիմնված կոդավորման խնդիրներ Հարցազրույցների համար.

  • Ինչպե՞ս իրականացնել արագընթաց ալգորիթմ ՝ առանց Java- ում հետընթաց կատարելու: (լուծում)
  • Ինչպե՞ս ջնջել տարրը զանգվածից Java- ում: (լուծում)
  • 20 Հարցազրույցների կոդավորման համար ալգորիթմների հարցերի տեսակավորում (հարցեր)
  • Տարբերությունը Quicksort- ի և Counting Sort Algorithm- ի միջև: (պատասխանել)
  • Տվյալների կառուցվածքի և ալգորիթմների թոփ 10 դասընթացներ Java ծրագրավորողների համար (դասընթացներ)
  • Ինչպե՞ս Java- ում գտնել չտեսակավորված զանգվածից կրկնօրինակներ: (լուծում)
  • Տարբերությունը Counting Sort- ի և Bucket Sort- ի ալգորիթմի միջև: (պատասխանել)
  • Ինչպես գտնել զանգվածի բոլոր զույգերը, որոնց գումարը հավասար է k (լուծում)
  • Ինչպե՞ս հեռացնել կրկնօրինակները զանգվածից Java- ում: (լուծում)
  • Ինչպե՞ս գտնել 1 -ից 100 պարունակող զանգվածից բացակայող արժեք: (լուծում)
  • 50+ Տվյալների կառուցվածք և ալգորիթմներ Հարցազրույցների խնդիրներ (հարցեր)
  • Տարբերությունը Quicksort- ի և Mergesort ալգորիթմի միջև: (պատասխան)
  • Որոշ անվճար դասընթացներ ՝ տվյալների կառուցվածքը խորությամբ սովորելու համար (FreeCodeCamp)
  • Ինչպե՞ս հակադարձել զանգվածը Java- ում: (լուծում)
  • Ինչպե՞ս հաշվել Java- ում տրված երկուական ծառի տերևային հանգույցների թիվը: (լուծում)
  • Ռեկուրսիվ InOrder անցման ալգորիթմ (լուծում)
  • 10 Տվյալների կառուցվածքի և ալգորիթմի անվճար դասընթացներ ծրագրավորողների համար (դասընթացներ)
  • 100+ Տվյալների կառուցվածքի կոդավորման խնդիրներ հարցազրույցներից (հարցեր)

Շնորհակալություն այս հոդվածը մինչ այժմ կարդալու համար: Եթե ​​ձեզ դուր է գալիս Java Array- ի այս ձեռնարկը, ապա այն կիսեք ձեր ընկերների և գործընկերների հետ: Եթե ​​ունեք որևէ հարց կամ կարծիք, խնդրում ենք թողնել մեկնաբանություն:

Հ.Գ – Եթե դուք փնտրում եք անվճար Ալգորիթմների դասընթացներ ՝ տվյալների կառուցվածքի և ալգորիթմների վերաբերյալ ձեր պատկերացումն բարելավելու համար, ապա ավելի լավ սովորելու համար պետք է նաև ստուգեք տվյալների կառուցվածքի այս անվճար դասընթացները: