logo

TechCodeview

Lisäyslajittelu – Tietorakenteen ja algoritmin opetusohjelmat

Lisäyslajittelu on yksinkertainen lajittelualgoritmi, joka toimii iteratiivisesti lisäämällä lajittelemattoman luettelon jokaisen elementin oikeaan paikkaan luettelon lajitellussa osassa. Se on a vakaa lajittelu algoritmi, mikä tarkoittaa, että elementit, joilla on samat arvot, säilyttävät suhteellisen järjestyksensä lajitetussa lähdössä.

Lisäyslajittelu on kuin pelikorttien lajittelua käsissäsi. Jaat kortit kahteen ryhmään: lajitellut kortit ja lajittelemattomat kortit. Sitten valitset kortin lajittelemattomasta ryhmästä ja asetat sen oikeaan paikkaan lajiteltuun ryhmään.



Lisäyslajittelualgoritmi:

Lisäyslajittelu on yksinkertainen lajittelualgoritmi, joka toimii rakentamalla lajiteltu taulukko elementti kerrallaan. Sitä pidetään an paikallaan lajittelualgoritmi, mikä tarkoittaa, että se ei vaadi ylimääräistä muistitilaa alkuperäisen taulukon lisäksi.

Algoritmi:

Suorita lisäyslajittelu seuraavasti:



  • Meidän on aloitettava taulukon toisesta elementistä, koska taulukon ensimmäisen elementin oletetaan olevan lajiteltu.
  • Vertaa toista elementtiä ensimmäiseen elementtiin ja tarkista, onko toinen elementti pienempi, ja vaihda ne.
  • Siirry kolmanteen elementtiin ja vertaa sitä toiseen elementtiin, sitten ensimmäiseen elementtiin ja vaihda tarpeen mukaan asettaaksesi se oikeaan paikkaan kolmen ensimmäisen elementin joukossa.
  • Jatka tätä prosessia vertaamalla jokaista elementtiä sitä edeltäviin ja vaihtamalla niitä tarpeen mukaan, jotta se sijoittuu oikeaan paikkaan lajiteltujen elementtien joukossa.
  • Toista, kunnes koko taulukko on lajiteltu.

Lisäyslajittelualgoritmin toiminta:

Harkitse taulukkoa, jossa on elementtejä : {23, 1, 10, 5, 2}

Ensimmäinen passi:



  • Nykyinen elementti on 23
  • Taulukon ensimmäisen elementin oletetaan olevan lajiteltu.
  • Lajiteltu osa asti 0 indeksi on: [23]

Toinen passi:

  • Vertailla 1 kanssa 23 (nykyinen elementti lajitellun osan kanssa).
  • Siitä asti kun 1 on pienempi, aseta 1 ennen 23 .
  • Lajiteltu osa asti 1 indeksi on: [1, 23]

Kolmas passi:

  • Vertailla 10 kanssa 1 ja 23 (nykyinen elementti lajitellun osan kanssa).
  • Siitä asti kun 10 on suurempi kuin 1 ja pienempi kuin 23 , aseta 10 välillä 1 ja 23 .
  • Lajiteltu osa asti 2 indeksi on: [1, 10, 23]

Neljäs passi:

  • Vertailla 5 kanssa 1 , 10 , ja 23 (nykyinen elementti lajitellun osan kanssa).
  • Siitä asti kun 5 on suurempi kuin 1 ja pienempi kuin 10 , aseta 5 välillä 1 ja 10 .
  • Lajiteltu osa asti 3 indeksi on : [1, 5, 10, 23]

Viides passi:

  • Vertailla 2 kanssa 1, 5, 10 , ja 23 (nykyinen elementti lajitellun osan kanssa).
  • Siitä asti kun 2 on suurempi kuin 1 ja pienempi kuin 5 lisää 2 välillä 1 ja 5 .
  • Lajiteltu osa asti 4 indeksi on: [1, 2, 5, 10, 23]

Lopullinen taulukko:

  • Lajiteltu matriisi on: [1, 2, 5, 10, 23]
Suositeltu käytännön lisäyslajittelu Kokeile sitä!

Lisäyslajittelun toteutus:

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]> avain) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = avain;  } } // Aputoiminto tulostaa taulukon // koon n void printArray(int arr[], int n) { int i;  for (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]> avain) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = avain;  } } // Aputoiminto, jolla tulostetaan taulukko, jonka koko on n void printArray(int arr[], int n) { int i;  for (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]> avain) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = avain;  } } /* Aputoiminto, jolla tulostetaan taulukko, jonka koko on n*/ staattinen 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 ja avain< 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]> avain) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = avain;  } } // Aputoiminto tulostaa // matriisin koko n staattinen 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>>  
  Lähtö      Aika monimutkaisuus:    O(N^2)  
    Aputila:    O(1)
 
 Lisäyslajittelun monimutkaisuusanalyysi :
    Lisäyslajittelun aika monimutkaisuus    
  •     Paras tapaus:         Päällä)    , Jos luettelo on jo lajiteltu, missä n on luettelon elementtien lukumäärä.
  •     Keskimääräinen tapaus:         Päällä       2       )    , Jos luettelo on satunnaisessa järjestyksessä
  •     Pahimmassa tapauksessa:         Päällä       2       )    , Jos luettelo on käänteisessä järjestyksessä
Avaruuden monimutkaisuus    lisäyslajittelusta    
  •     Aputila:    O(1), lisäyslajittelu vaatii    O(1)    lisää tilaa, mikä tekee siitä tilaa säästävän lajittelualgoritmin.
Edut    lisäyslajittelu:    
  • Yksinkertainen ja helppo toteuttaa.
  • Vakaa lajittelualgoritmi.
  • Tehokas pienille luetteloille ja lähes lajiteltuille luetteloille.
  • Tilatehokas.
Haitat    lisäyslajittelu:    
  • Tehoton suurille listoille.
  • Ei yhtä tehokas kuin muut lajittelualgoritmit (esim. yhdistäminen, pikalajittelu) useimmissa tapauksissa.
Sovellukset    lisäyslajittelu:    
Lisäyslajittelua käytetään yleisesti tilanteissa, joissa:
 
  • Lista on pieni tai lähes lajiteltu.
  • Yksinkertaisuus ja vakaus ovat tärkeitä.
Usein kysytyt kysymykset lisäyslajittelusta
    Q1. Mitkä ovat lisäyslajittelualgoritmin rajatapaukset?    
java indexof

  
Lisäyslajittelu vie maksimiajan lajitteluun, jos elementit lajitellaan käänteisessä järjestyksessä. Ja se vie minimiajan (n järjestys), kun elementit on jo lajiteltu.
 
    Q2. Mikä on lisäyslajittelualgoritmin algoritminen paradigma?    
  
Lisäyslajittelu-algoritmi noudattaa inkrementaalista lähestymistapaa.
 
    Q3. Onko Insertion Sort -lajittelualgoritmi paikallaan?    
  
Kyllä, lisäyslajittelu on paikan päällä oleva lajittelualgoritmi.
 
    Q4. Onko lisäyslajittelu vakaa algoritmi?    
  
Kyllä, lisäyslajittelu on vakaa lajittelualgoritmi.
 
    Q5. Milloin Insertion Sort -algoritmia käytetään?    
  
Lisäyslajittelua käytetään, kun elementtien lukumäärä on pieni. Siitä voi olla hyötyä myös silloin, kun syöttötaulukko on melkein lajiteltu ja vain muutama elementti on väärässä täydellisessä suuressa taulukossa.