Algoritam sortiranja umetanja

U ovom vodiču naučit ćete kako funkcionira sortiranje umetanja. Također ćete pronaći radne primjere sortiranja umetanja u C, C ++, Java i Python.

Razvrstavanje umetanja djeluje slično kao što u igri karata razvrstavamo karte u ruci.

Pretpostavljamo da je prva karta tada već sortirana, odabiremo nesortiranu kartu. Ako je nerazvrstana karta veća od karte u ruci, ona se inače postavlja desno, lijevo. Na isti način uzimaju se i druge nesortirane karte i postavljaju se na svoje pravo mjesto.

Sličan pristup koristi se sortiranjem umetanja.

Sortiranje umetanja algoritam je sortiranja koji postavlja nesortirani element na odgovarajuće mjesto u svakoj iteraciji.

Kako sortiranje umetanja djeluje?

Pretpostavimo da trebamo sortirati sljedeći niz.

Početni niz

Pretpostavlja se da je prvi element u polju sortiran. Uzmite drugi element i spremite ga odvojeno u key.
Usporedite keys prvim elementom. Ako je prvi element veći od key, tada se ključ postavlja ispred prvog elementa. Ako je prvi element veći od ključa, tada se ključ postavlja ispred prvog elementa.
Sada su prva dva elementa razvrstana.
Uzmite treći element i usporedite ga s elementima s lijeve strane. Postavio ga je odmah iza elementa manjeg od njega. Ako nema elementa manjeg od njega, stavite ga na početak niza. Mjesto 1 na početku
Slično tome, svaki nerazvrstani element postavite na točan položaj. Mjesto 4 iza 1 Mjesto 3 iza 1 i niz je sortiran

Algoritam sortiranja umetanja

 insertionSort (array) označi prvi element sortiranim za svaki nerazvrstani element X 'izvadi' element X za j X pomakni razvrstani element udesno za 1 prekidnu petlju i umetni X ovdje završi insertionSort

Primjeri Pythona, Java i C / C ++

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

Složenost

Složenost vremena

Najgora složenost slučaja: Pretpostavimo da je niz u uzlaznom redoslijedu i želite ga sortirati u opadajućem redoslijedu. U ovom se slučaju događa najgora složenost slučaja. Svaki se element mora usporediti sa svim ostalim elementima, tako da se za svaki n-ti element vrši usporedba. Dakle, ukupan broj usporedbi =O(n²)

(n-1)
n*(n-1) ~ n²
Složenost najboljeg slučaja: O(n)
Kada je niz već sortiran, vanjska petlja se pokreće nnekoliko puta, dok se unutarnja petlja uopće ne izvodi. Dakle, postoji samo nbroj usporedbi. Dakle, složenost je linearna.
Prosječna složenost slučaja: Događa se kada su elementi niza pomiješanim redoslijedom (niti uzlazno niti silazno).O(n²)