Lisälajittelualgoritmi

Tässä opetusohjelmassa opit, miten lisäyslaji toimii. Löydät myös toimivia esimerkkejä lisäyslajittelusta C, C ++, Java ja Python.

Lisälajittelu toimii samalla tavalla kuin lajittelemme kädessämme olevat kortit korttipelissä.

Oletetaan, että ensimmäinen kortti on jo lajiteltu, valitsemme lajittelemattoman kortin. Jos lajittelematon kortti on suurempi kuin kädessä oleva kortti, se asetetaan muuten oikealle, vasemmalle. Samalla tavalla muut lajittelemattomat kortit otetaan ja asetetaan oikeaan paikkaan.

Samanlaista lähestymistapaa käytetään lisäyslajittelussa.

Lisälajittelu on lajittelualgoritmi, joka sijoittaa lajittelemattoman elementin sopivaan paikkaan jokaisessa iteraatiossa.

Kuinka lisäyslajittelu toimii?

Oletetaan, että meidän on lajiteltava seuraava taulukko.

Alkuperäinen taulukko
  1. Matriisin ensimmäisen elementin oletetaan olevan lajiteltu. Ota toinen elementti ja säilytä se erikseen key.
    Vertaa keyensimmäiseen elementtiin. Jos ensimmäinen elementti on suurempi kuin key, avain sijoitetaan ensimmäisen elementin eteen. Jos ensimmäinen elementti on suurempi kuin avain, avain sijoitetaan ensimmäisen elementin eteen.
  2. Kaksi ensimmäistä elementtiä on nyt lajiteltu.
    Ota kolmas elementti ja vertaa sitä vasemmalla oleviin elementteihin. Sijoita se juuri sitä pienemmän elementin taakse. Jos sitä ei ole pienempi elementti, aseta se matriisin alkuun. Aseta 1 alkuun
  3. Aseta vastaavasti jokainen lajittelematon elementti oikeaan paikkaan. Sijoita 4 1 taakse 3 Aseta 1 taakse ja taulukko on lajiteltu

Lisälajittelualgoritmi

 insertionSort (matriisi) merkitse ensimmäinen elementti lajiteltuina jokaiselle lajittelemattomalle elementille X 'purkaa' elementti X j X siirtää lajiteltu elementti oikealle 1 katkaisusilmukalla ja lisää X tähän loppuun insertionSort

Python-, Java- ja C / C ++ -esimerkkejä

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); )

Monimutkaisuus

Ajan monimutkaisuus

  • Pahimman tapauksen monimutkaisuus: Oletetaan, että taulukko on nousevassa järjestyksessä ja haluat lajitella sen laskevassa järjestyksessä. Tässä tapauksessa tapahtuu pahimman tapauksen monimutkaisuus. Kutakin elementtiä on verrattava muihin elementteihin, joten jokaiselle n: lle elementille tehdään useita vertailuja. Siten vertailujen kokonaismäärä =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Parhaan tapauksen monimutkaisuus: O(n)
    Kun matriisi on jo lajiteltu, ulompi silmukka kulkee nuseita kertoja, kun taas sisempi silmukka ei toimi ollenkaan. Joten nvertailuja on vain useita. Siten monimutkaisuus on lineaarista.
  • Keskimääräinen tapauksen monimutkaisuus: Se tapahtuu, kun matriisin elementit ovat sekaisin (ei nousevia eikä laskevia).O(n2)

Avaruuden monimutkaisuus

Avaruuden monimutkaisuus johtuu O(1)siitä, että käytetään ylimääräistä muuttujaa key.

Lisälajittelusovellukset

Lisäyslajittelua käytetään, kun:

  • taulukossa on pieni määrä elementtejä
  • lajiteltavana on vain muutama elementti

Mielenkiintoisia artikkeleita...