Algoritmus třídění vložení

V tomto kurzu se dozvíte, jak funguje třídění vkládání. Také najdete pracovní příklady řazení typu C, C ++, Java a Python.

Třídění vložení funguje podobně, jako když v karetní hře třídíme karty v ruce.

Předpokládáme, že první karta je již seřazená, potom vybereme netříděnou kartu. Pokud je netříděná karta větší než karta v ruce, je umístěna vpravo, jinak vlevo. Stejným způsobem jsou odebrány další netříděné karty a umístěny na správné místo.

Podobný přístup používá třídění vkládání.

Insertion sort je třídicí algoritmus, který v každé iteraci umístí netříděný prvek na vhodné místo.

Jak funguje třídění vložení?

Předpokládejme, že musíme seřadit následující pole.

Počáteční pole

Předpokládá se, že první prvek v poli bude seřazen. Vezměte druhý prvek a uložte jej samostatně do key.
Porovnejte keys prvním prvkem. Pokud je první prvek větší než key, pak je klíč umístěn před první prvek. Pokud je první prvek větší než klíč, pak je klíč umístěn před první prvek.
Nyní jsou první dva prvky seřazeny.
Vezměte třetí prvek a porovnejte jej s prvky nalevo od něj. Umístil ji těsně za prvek menší než on. Pokud není žádný prvek menší než on, umístěte jej na začátek pole. Umístěte 1 na začátek
Podobně umístěte každý netříděný prvek do správné polohy. Umístěte 4 za 1 Umístěte 3 za 1 a pole je tříděno

Algoritmus třídění vložení

 insertionSort (pole) označit první prvek jako tříděný pro každý netříděný prvek X 'extrahovat' prvek X pro j X přesunout seřazený prvek doprava o 1 smyčku přerušení a vložit X sem konec insertionSort

Python, Java a C / C ++ příklady

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žitost

Časové složitosti

Složitost nejhoršího případu: Předpokládejme, že pole je ve vzestupném pořadí a chcete jej seřadit v sestupném pořadí. V tomto případě nastává nejhorší složitost. Každý prvek musí být porovnán s každým z ostatních prvků, takže pro každý n-tý prvek je provedeno několik srovnání. Celkový počet srovnání tedy =O(n²)

(n-1)
n*(n-1) ~ n²
Nejlepší případová složitost: O(n)
Když je pole již tříděno, vnější smyčka běží nněkolikrát, zatímco vnitřní smyčka vůbec nefunguje. Existuje tedy pouze nněkolik srovnání. Složitost je tedy lineární.
Průměrná složitost případu: Nastane, když jsou prvky pole v neuspořádaném pořadí (ani vzestupně, ani sestupně).O(n²)