logo

TechCodeview

Ievietošanas kārtošana — datu struktūras un algoritmu apmācības

Ievietošanas kārtošana ir vienkāršs kārtošanas algoritms, kas darbojas, iteratīvi ievietojot katru nešķirota saraksta elementu tā pareizajā vietā sakārtotajā saraksta daļā. Tas ir stabila šķirošana algoritms, kas nozīmē, ka elementi ar vienādām vērtībām saglabā savu relatīvo secību sakārtotajā izvadē.

Ievietošanas kārtošana ir kā spēļu kāršu šķirošana rokās. Jūs sadalāt kārtis divās grupās: šķirotajās un nešķirotajās. Pēc tam jūs izvēlaties kartīti no nešķirotās grupas un ievietojat to pareizajā vietā sakārtotajā grupā.



Ievietošanas kārtošanas algoritms:

Ievietošanas kārtošana ir vienkāršs kārtošanas algoritms, kas darbojas, veidojot sakārtotu masīvu pa vienam elementam. Tas tiek uzskatīts par vietā šķirošanas algoritms, kas nozīmē, ka tam nav nepieciešama papildu atmiņas vieta ārpus sākotnējā masīva.

Algoritms:

Lai veiktu ievietošanas kārtošanu, veiciet šīs darbības:



  • Mums jāsāk ar otro masīva elementu, jo tiek pieņemts, ka pirmais elements masīvā ir sakārtots.
  • Salīdziniet otro elementu ar pirmo elementu un pārbaudiet, vai otrais elements ir mazāks, tad nomainiet tos.
  • Pārejiet uz trešo elementu un salīdziniet to ar otro elementu, pēc tam ar pirmo elementu un pēc vajadzības samainiet to, lai tas atrastos pareizajā pozīcijā starp pirmajiem trim elementiem.
  • Turpiniet šo procesu, salīdzinot katru elementu ar tiem, kas bija pirms tā, un pēc vajadzības samainot, lai to novietotu pareizā pozīcijā starp sakārtotajiem elementiem.
  • Atkārtojiet, līdz viss masīvs ir sakārtots.

Ievietošanas kārtošanas algoritma darbība:

Apsveriet masīvu ar elementiem : {23, 1, 10, 5, 2}

Pirmā caurlaide:



  • Pašreizējais elements ir 23
  • Tiek pieņemts, ka pirmais elements masīvā ir sakārtots.
  • Sašķirotā daļa līdz 0 indekss ir: [23]

Otrā caurlaide:

  • Salīdzināt 1 ar 23 (pašreizējais elements ar sakārtoto daļu).
  • Kopš 1 ir mazāks, ievietojiet 1 pirms tam 23 .
  • Sašķirotā daļa līdz 1 indekss ir: [1, 23]

Trešā caurlaide:

  • Salīdzināt 10 ar 1 un 23 (pašreizējais elements ar sakārtoto daļu).
  • Kopš 10 ir labāks par 1 un mazāks par 23 , ievietojiet 10 starp 1 un 23 .
  • Sašķirotā daļa līdz 2 indekss ir: [1, 10, 23]

Ceturtā caurlaide:

mākoņdatošanas lietojumprogrammas
  • Salīdzināt 5 ar 1 , 10 , un 23 (pašreizējais elements ar sakārtoto daļu).
  • Kopš 5 ir labāks par 1 un mazāks par 10 , ievietojiet 5 starp 1 un 10 .
  • Sašķirotā daļa līdz 3 indekss ir : [1, 5, 10, 23]

Piektā caurlaide:

  • Salīdzināt 2 ar 1, 5, 10 , un 23 (pašreizējais elements ar sakārtoto daļu).
  • Kopš 2 ir labāks par 1 un mazāks par 5 ievietot 2 starp 1 un 5 .
  • Sašķirotā daļa līdz 4 indekss ir: [1, 2, 5, 10, 23]

Galīgais masīvs:

  • Sakārtotais masīvs ir: [1, 2, 5, 10, 23]
Ieteicamā prakse ievietošanas kārtošana Izmēģiniet to!

Ievietošanas kārtošanas ieviešana:

C++ 
// C++ program for insertion sort #include  using namespace std; // Function to sort an array using // insertion sort void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,   // to one position ahead of their  // current position  while (j>= 0 && arr[j]> taustiņš) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = atslēga;  } } // Lietderības funkcija n izmēra masīva drukāšanai // void printArray(int arr[], int n) { int i;  par (i = 0; i< n; i++)  cout << arr[i] << ' ';  cout << endl; } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int N = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, N);  printArray(arr, N);  return 0; } // This is code is contributed by rathbhupendra>
C 
// C program for insertion sort #include  #include  /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> taustiņš) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = atslēga;  } } // Lietderības funkcija n izmēra masīva drukāšanai void printArray(int arr[], int n) { int i;  par (i = 0; i< n; i++)  printf('%d ', arr[i]);  printf('
'); } /* Driver program to test insertion sort */ int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int n = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, n);  printArray(arr, n);  return 0; }>
Java 
// Java program for implementation of Insertion Sort public class InsertionSort {  /*Function to sort array using insertion sort*/  void sort(int arr[])  {  int n = arr.length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> taustiņš) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = atslēga;  } } /* Lietderības funkcija, lai drukātu masīvu ar izmēru n*/ static void printArray(int arr[]) { int n = arr.length;  for (int i = 0; i< n; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver method  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } }; /* This code is contributed by Rajat Mishra. */>
Python 
# Python program for implementation of Insertion Sort # Function to do insertion sort def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j>= 0 un atslēga< arr[j] : arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) for i in range(len(arr)): print ('% d' % arr[i]) # This code is contributed by Mohit Kumra>
C# 
// C# program for implementation of Insertion Sort using System; class InsertionSort {  // Function to sort array  // using insertion sort  void sort(int[] arr)  {  int n = arr.Length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,  // to one position ahead of  // their current position  while (j>= 0 && arr[j]> taustiņš) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = atslēga;  } } // Lietderības funkcija drukāšanai // n izmēra masīvs static void printArray(int[] arr) { int n = arr.Length;  for (int i = 0; i< n; ++i)  Console.Write(arr[i] + ' ');  Console.Write('
');  }  // Driver Code  public static void Main()  {  int[] arr = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } } // This code is contributed by ChitraNayal.>
Javascript 
>>PHP>>  
  Izvade      Laika sarežģītība:    O(N^2)  
    Palīgtelpa:    O(1)
 
 Ievietošanas kārtošanas sarežģītības analīze :
    Ievietošanas kārtošanas laika sarežģītība    
  •     Labākais gadījums:         O(n)    , Ja saraksts jau ir sakārtots, kur n ir elementu skaits sarakstā.
  •     Vidējais gadījums:         O(n       2       )    , Ja saraksts ir nejauši sakārtots
  •     Sliktākajā gadījumā:         O(n       2       )    , Ja saraksts ir apgrieztā secībā
Kosmosa sarežģītība    no ievietošanas kārtošanas    
  •     Palīgtelpa:    O(1), ievietošanas kārtošanai nepieciešams    O(1)    papildu telpa, padarot to par vietu taupošu šķirošanas algoritmu.
Priekšrocības    no ievietošanas kārtošanas:    
  • Vienkāršs un viegli īstenojams.
  • Stabils šķirošanas algoritms.
  • Efektīva maziem sarakstiem un gandrīz sakārtotiem sarakstiem.
  • Telpefektīvs.
Trūkumi    no ievietošanas kārtošanas:    
  • Neefektīvi lieliem sarakstiem.
  • Vairumā gadījumu nav tik efektīvi kā citi šķirošanas algoritmi (piemēram, sapludināšanas kārtošana, ātrā kārtošana).
Lietojumprogrammas    no ievietošanas kārtošanas:    
Ievietošanas kārtošanu parasti izmanto situācijās, kad:
 
  • Saraksts ir mazs vai gandrīz sakārtots.
  • Svarīga ir vienkāršība un stabilitāte.
Bieži uzdotie jautājumi par ievietošanas kārtošanu
    Q1. Kādi ir ievietošanas kārtošanas algoritma robežgadījumi?    
  
Ievietošanas kārtošana aizņem maksimālo kārtošanas laiku, ja elementi tiek kārtoti apgrieztā secībā. Un tas aizņem minimālu laiku (n-kārtība), kad elementi jau ir sakārtoti.
 
    Q2. Kas ir ievietošanas kārtošanas algoritma algoritmiskā paradigma?    
  
Ievietošanas kārtošanas algoritms izmanto pakāpenisku pieeju.
 
    Q3. Vai ievietošanas kārtošana ir kārtošanas algoritms vietā?    
  
Jā, ievietošanas kārtošana ir kārtošanas algoritms vietā.
 
    Q4. Vai ievietošanas kārtošana ir stabils algoritms?    
  
Jā, ievietošanas kārtošana ir stabils kārtošanas algoritms.
 
    Q5. Kad tiek izmantots ievietošanas kārtošanas algoritms?    
  
Ievietošanas kārtošana tiek izmantota, ja elementu skaits ir mazs. Tas var būt noderīgi arī tad, ja ievades masīvs ir gandrīz sakārtots un tikai daži elementi ir nepareizi ievietoti pilnā lielajā masīvā.