Ievietošanas šķirošanas algoritms

Šajā apmācībā jūs uzzināsiet, kā darbojas ievietošanas kārtošana. Jūs atradīsit arī piemērotus ievietošanas kārtošanas piemērus C, C ++, Java un Python.

Ievietošanas kārtošana darbojas līdzīgi kā kārtojam kārtis rokā kāršu spēlē.

Mēs pieņemam, ka pirmā karte pēc tam jau ir sakārtota, mēs izvēlamies nešķirotu karti. Ja nešķirotā karte ir lielāka par rokā esošo karti, pretējā gadījumā tā tiek novietota pa labi, pa kreisi. Tādā pašā veidā tiek paņemtas citas nešķirotas kartes un ievietotas īstajā vietā.

Līdzīgu pieeju izmanto ievietošanas kārtojumā.

Ievietošanas kārtošana ir šķirošanas algoritms, kas nešķiroto elementu ievieto piemērotā vietā katrā atkārtojumā.

Kā darbojas ievietošanas kārtošana?

Pieņemsim, ka mums ir jāšķiro šāds masīvs.

Sākotnējais masīvs
  1. Tiek pieņemts, ka masīva pirmais elements ir sakārtots. Paņemiet otro elementu un uzglabājiet to atsevišķi key.
    Salīdziniet keyar pirmo elementu. Ja pirmais elements ir lielāks par key, tad atslēga tiek novietota pirmā elementa priekšā. Ja pirmais elements ir lielāks par atslēgu, tad atslēga tiek novietota pirmā elementa priekšā.
  2. Tagad pirmie divi elementi ir sakārtoti.
    Paņemiet trešo elementu un salīdziniet to ar elementiem, kas atrodas tā kreisajā pusē. Novietojiet to tieši aiz elementa, kas ir mazāks par to. Ja nav elementa, kas būtu mazāks par to, ievietojiet to masīva sākumā. Sākumā ievietojiet 1
  3. Līdzīgi novietojiet katru nešķiroto elementu pareizajā pozīcijā. Vieta 4 aiz 1 Vieta 3 aiz 1, un masīvs ir sakārtots

Ievietošanas šķirošanas algoritms

 insertionSort (masīvs) atzīmē pirmo elementu kā sakārtotu katram nešķirotajam elementam X 'izvelk' elementu X j X pārvieto sakārtoto elementu pa labi ar 1 pārtraukuma cilpu un ievieto X šeit beigu ievietošanaSort

Python, Java un C / C ++ piemēri

Python Java C C ++ 
 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)
  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )
 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

Sarežģītība

Laika sarežģītība

  • Sliktākā gadījuma sarežģītība: Pieņemsim, ka masīvs ir augošā secībā, un jūs vēlaties to kārtot dilstošā secībā. Šajā gadījumā sliktākajā gadījumā notiek sarežģītība. Katrs elements ir jāsalīdzina ar katru citu elementu, tāpēc katram n -tajam elementam tiek veikts salīdzinājumu skaits. Tādējādi kopējais salīdzinājumu skaits =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Labākā gadījuma sarežģītība: O(n)
    kad masīvs jau ir sakārtots, ārējā cilpa darbojas nvairākas reizes, savukārt iekšējā cilpa vispār nedarbojas. Tātad ir tikai ndaudz salīdzinājumu. Tādējādi sarežģītība ir lineāra.
  • Vidējā gadījuma sarežģītība: tā notiek, ja masīva elementi ir sajaukti secībā (ne augšupejoši, ne dilstoši).O(n2)

Kosmosa sarežģītība

Kosmoss ir sarežģīts O(1)tāpēc, ka keytiek izmantots papildu mainīgais .

Programmu ievietošana

Ievietošanas kārtošana tiek izmantota, ja:

  • masīvā ir mazs elementu skaits
  • ir tikai daži elementi, kas jāšķiro

Interesanti raksti...