Menu

Sortowanie przez wstawianie w Javie - Algorytm sortowania przez wstawianie i przykłady

  • Główny
  • Inny
  • Sortowanie przez wstawianie w Javie - Algorytm sortowania przez wstawianie i przykłady

insertion sort java insertion sort algorithm examples

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Ten samouczek wyjaśnia sortowanie przez wstawianie w Javie, w tym jego algorytm, pseudokod i przykłady sortowania tablic, listy pojedynczo i podwójnie połączonych:

Technika algorytmu sortowania przez wstawianie jest podobna do sortowania bąbelkowego, ale jest nieco bardziej wydajna. Sortowanie przez wstawianie jest bardziej wykonalne i efektywne w przypadku niewielkiej liczby elementów. Gdy zestaw danych jest większy, sortowanie danych zajmie więcej czasu.

=> Zapoznaj się z podręcznikiem Java dla początkujących tutaj.

pytania i odpowiedzi na rozmowę z oracle tuning performance

Sortowanie przez wstawianie w Javie

Czego się nauczysz:

Wprowadzenie do sortowania przez wstawianie w Javie

W technice sortowania przez wstawianie zakładamy, że pierwszy element na liście jest już posortowany i zaczynamy od drugiego elementu. Drugi element jest porównywany z pierwszym i zamieniany, jeśli nie jest w kolejności. Proces ten powtarza się dla wszystkich kolejnych elementów.

Ogólnie rzecz biorąc, technika sortowania przez wstawianie porównuje każdy element ze wszystkimi jego poprzednimi elementami i sortuje element, aby umieścić go we właściwej pozycji.

Jak już wspomniano, technika sortowania przez wstawianie jest bardziej wykonalna w przypadku mniejszego zestawu danych, a zatem tablice z niewielką liczbą elementów można sortować za pomocą wydajnego sortowania przez wstawianie.

Sortowanie przez wstawianie jest szczególnie przydatne w sortowaniu połączonych struktur danych list. Jak wiesz, listy połączone mają wskaźniki wskazujące na następny element (lista pojedynczo połączona) i poprzedni element (lista podwójnie połączona). Ułatwia to śledzenie poprzednich i następnych elementów.

W ten sposób łatwiej jest używać sortowania przez wstawianie do sortowania połączonych list. Jednak sortowanie zajmie dużo czasu, jeśli elementów danych jest więcej.

W tym samouczku omówimy technikę sortowania przez wstawianie, w tym jej algorytm, pseudokod i przykłady. Zaimplementujemy również programy Java do sortowania tablicy, listy pojedynczo połączonej i listy podwójnie połączonej za pomocą sortowania przez wstawianie.

Algorytm sortowania przez wstawianie

Algorytm sortowania przez wstawianie jest następujący.

Krok 1 : Powtórz kroki od 2 do 5 dla K = 1 do N-1

Krok 2 : temperatura zadana = A (K)

Krok 3 : zestaw J = K - 1

Krok 4 :

Powtarzaj, gdy temp<=A(J)
zestaw A (J + 1) = A (J)
ustaw J = J - 1
(koniec wewnętrznej pętli)

Krok 5 :

zestaw A (J + 1) = temp
(koniec pętli)

Krok 6 : Wyjście

Jak wiesz, sortowanie przez wstawianie zaczyna się od drugiego elementu przy założeniu, że pierwszy element jest już posortowany. Powyższe kroki są powtarzane dla wszystkich elementów na liście od drugiego elementu wzwyż i umieszczane na ich żądanych pozycjach.

Pseudokod do sortowania przez wstawianie

Pseudokod dla techniki sortowania przez wstawianie jest podany poniżej.

procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element while freePosition > 0 and array(freePosition -1) > insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedure

Następnie zobaczmy ilustrację przedstawiającą sortowanie tablicy przy użyciu sortowania przez wstawianie.

Sortowanie tablicy przy użyciu sortowania przez wstawianie

Weźmy przykład sortowania przez wstawianie przy użyciu tablicy.

Tablica do posortowania jest następująca:

tablica do posortowania

Teraz dla każdego przebiegu porównujemy bieżący element ze wszystkimi jego poprzednimi elementami. Tak więc w pierwszym przebiegu zaczynamy od drugiego elementu.

Porównaj 2. element z 1. elementem

zdać 2

zdać 3

zaliczenie 4

zdać 5

zdać 6

Dlatego potrzebujemy N liczby przebiegów, aby całkowicie posortować tablicę zawierającą N liczby elementów.

selenowy webdriver z przykładem zaćmienia ogórka

Powyższą ilustrację można podsumować w formie tabelarycznej, jak pokazano poniżej:

PrzechodzićNiesortowana listaporównaniePosortowana lista
1{10,2,6,15,4,1}{10.2}{2,10, 6,15,4,1}
dwa{2,10, 6,15,4,1}{2,10, 6}{2,6,10,15,4,1}
3{2,6,10,15,4,1}{2,6, 10,15}{2,6,10,15,4,1}
4{2,6,10,15,4,1}{2.6, 10.15.4}{2,4,6,10,15,1}
5{2,4,6,10,15,1}{2,4,6,10,15,1}{1, 2, 4, 6, 10, 15}
6{}{}{1, 2, 4, 6, 10, 15}

Jak pokazano na powyższej ilustracji, na końcu każdego przejścia jeden element trafia na swoje właściwe miejsce. Dlatego generalnie, aby umieścić N elementów we właściwym miejscu, potrzebujemy przejść N-1.

Implementacja sortowania przez wstawianie w Javie

Poniższy program przedstawia implementację sortowania przez wstawianie w Javie. Tutaj mamy tablicę do posortowania przy użyciu sortowania przez wstawianie.

import java.util.*; public class Main { public static void main(String() args) { //declare an array and print the original contents int() numArray = {10,6,15,4,1,45}; System.out.println('Original Array:' + Arrays.toString(numArray)); //apply insertion sort algorithm on the array for(int k=1; k=0 && temp <= numArray(j)) { numArray(j+1) = numArray(j); j = j-1; } numArray(j+1) = temp; } //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(numArray)); } }

Wynik:

Oryginalna tablica: (10, 6, 15, 4, 1, 45)
Posortowana tablica: (1, 4, 6, 10, 15, 45)

Implementacja sortowania przez wstawianie - wyjście

W powyższej implementacji widać, że sortowanie zaczyna się od 2ndelement tablicy (zmienna pętli j = 1), a następnie bieżący element jest porównywany ze wszystkimi jego poprzednimi elementami. Element jest następnie umieszczany we właściwej pozycji.

Sortowanie przez wstawianie działa efektywnie w przypadku mniejszych tablic i tablic, które są częściowo sortowane, w których sortowanie jest zakończone w mniejszej liczbie przebiegów.

Sortowanie przez wstawianie jest sortowaniem stabilnym, tj. Zachowuje kolejność równych elementów na liście.

Sortowanie połączonej listy za pomocą sortowania przez wstawianie

Poniższy program w języku Java przedstawia sortowanie pojedynczo połączonej listy przy użyciu sortowania przez wstawianie.

import java.util.*; class Linkedlist_sort { node head; node sorted; //define node of a linked list class node { int val; node next; public node(int val) { this.val = val; } } //add a node to the linked list void add(int val) { //allocate a new node node newNode = new node(val); //link new node to list newNode.next = head; //head points to new node head = newNode; } // sort a singly linked list using insertion sort void insertion_Sort(node headref) { // initially, no nodes in sorted list so its set to null sorted = null; node current = headref; // traverse the linked list and add sorted node to sorted list while (current != null) { // Store current.next in next node next = current.next; // current node goes in sorted list Insert_sorted(current); // now next becomes current current = next; } // update head to point to linked list head = sorted; } //insert a new node in sorted list void Insert_sorted(node newNode) { //for head node if (sorted == null || sorted.val >= newNode.val) { newNode.next = sorted; sorted = newNode; } else { node current = sorted; //find the node and then insert while (current.next != null && current.next.val

Wynik:

Oryginalna połączona lista:
1 8 32 2 10
Posortowana połączona lista:
1 2 8 10 32

wyjście - Lista połączona

W powyższym programie zdefiniowaliśmy klasę, która tworzy połączoną listę i dodaje do niej węzły oraz ją sortuje. Ponieważ lista pojedynczo połączona ma następny wskaźnik, łatwiej jest śledzić węzły podczas sortowania listy.

Sortowanie listy podwójnie połączonej za pomocą sortowania przez wstawianie

Poniższy program sortuje listę podwójnie połączoną przy użyciu sortowania przez wstawianie. Zauważ, że ponieważ podwójnie połączona lista zawiera zarówno poprzednie, jak i następne wskaźniki, łatwo jest zaktualizować i ponownie połączyć wskaźniki podczas sortowania danych.

class Main { // doubly linked list node static class Node { int data; Node prev, next; }; // return a new node in DLL static Node getNode(int data){ //create new node Node newNode = new Node(); // assign data to node newNode.data = data; newNode.prev = newNode.next = null; return newNode; } // insert a node in sorted DLL static Node insert_Sorted(Node head_ref, Node newNode) { Node current; //list is empty if (head_ref == null) head_ref = newNode; // node is inserted at the beginning of the DLL else if ((head_ref).data >= newNode.data) { newNode.next = head_ref; newNode.next.prev = newNode; head_ref = newNode; } else { current = head_ref; // find the node after which new node is to be inserted while (current.next != null && current.next.data prev points to new node / if ((head_ref) != null) (head_ref).prev = newNode; // move the head to point to the new node / (head_ref) = newNode; return head_ref; } public static void main(String args()) { // create empty DLL Node head = null; // add nodes to the DLL head=addNode(head, 5); head=addNode(head, 3); head=addNode(head, 7); head=addNode(head, 2); head=addNode(head, 11); head=addNode(head, 1); System.out.println( 'Original doubly linked list:'); print_DLL(head); head=insertion_Sort(head); System.out.println(' Sorted Doubly Linked List:'); print_DLL(head); } }

Wynik:

Oryginalna lista podwójnie połączona:
1 11 2 7 3 5
Lista posortowana podwójnie połączona:
1 2 3 5 7 11

Wynik - Lista podwójnie połączona

Często Zadawane Pytania

P # 1) Co to jest sortowanie przez wstawianie w Javie?

Odpowiedź: Sortowanie przez wstawianie to prosta technika sortowania w Javie, która jest wydajna w przypadku mniejszego zestawu danych i na miejscu. Zakłada się, że pierwszy element jest zawsze sortowany, a następnie każdy kolejny element jest porównywany ze wszystkimi jego poprzednimi elementami i umieszczany w odpowiednim miejscu.

Pytanie nr 2) Dlaczego sortowanie przez wstawianie jest lepsze?

Odpowiedź: Sortowanie przez wstawianie jest szybsze w przypadku mniejszych zestawów danych, gdy inne techniki, takie jak szybkie sortowanie, dodają narzut przez wywołania rekurencyjne. Sortowanie przez wstawianie jest stosunkowo stabilniejsze niż inne algorytmy sortowania i wymaga mniej pamięci. Sortowanie przez wstawianie działa również wydajniej, gdy tablica jest prawie posortowana.

Pytanie 3) Do czego służy sortowanie przez wstawianie?

Odpowiedź: Sortowanie przez wstawianie jest najczęściej używane w aplikacjach komputerowych, które tworzą złożone programy, takie jak wyszukiwanie plików, znajdowanie ścieżek i kompresja danych.

Pytanie 4)Jaka jest wydajność sortowania przez wstawianie?

najlepsze darmowe programy do czyszczenia rejestru dla systemu Windows 10

Odpowiedź: Sortowanie przez wstawianie ma średnią wydajność wielkości liter O (n ^ 2). Najlepszym przypadkiem sortowania przez wstawianie jest sytuacja, w której tablica jest już posortowana i ma wartość O (n). W najgorszym przypadku wydajność sortowania przez wstawianie ponownie wynosi O (n ^ 2).

Wniosek

Sortowanie przez wstawianie to prosta technika sortowania, która działa na tablicach lub połączonych listach. Jest to przydatne, gdy zestaw danych jest mniejszy. W miarę powiększania się zestawu danych technika ta staje się wolniejsza i nieefektywna.

Sortowanie przez wstawianie jest również bardziej stabilne i na miejscu niż inne techniki sortowania. Nie ma narzutu pamięci, ponieważ do przechowywania posortowanych elementów nie jest używana oddzielna struktura.

Sortowanie przez wstawianie działa dobrze w przypadku sortowania list połączonych, które są zarówno listami połączonymi pojedynczo, jak i podwójnie. Dzieje się tak, ponieważ połączona lista składa się z węzłów połączonych za pomocą wskaźników. Stąd sortowanie węzłów staje się łatwiejsze.

W naszym nadchodzącym samouczku omówimy jeszcze inną technikę sortowania w Javie.

=> Przeczytaj serię szkoleń Easy Java.

rekomendowane lektury

^