Меню

Сортування вставки на Java - Алгоритм сортування вставки та приклади

  • Головна
  • Інший
  • Сортування вставки на Java - Алгоритм сортування вставки та приклади

insertion sort java insertion sort algorithm examples

Спробуйте Наш Інструмент Для Усунення Проблем

Цей посібник пояснює сортування вставки на Java, включаючи алгоритм, псевдокод та приклади сортування масивів, однопов’язаний та подвійно пов’язаний список:

Метод алгоритму сортування вставки схожий на сортування міхурів, але трохи ефективніший. Сортування вставки є більш здійсненним та ефективним, коли задіяна невелика кількість елементів. Коли набір даних буде більшим, сортування даних займе більше часу.

=> Подивіться тут посібник для початківців Java.

DVD ripper для Windows 10 безкоштовно завантажити

Сортування вставки на Java

Що ви дізнаєтесь:

Вступ до сортування вставки в Java

У техніці вставки вставки ми припускаємо, що перший елемент у списку вже відсортований, і ми починаємо з другого елемента. Другий елемент порівнюється з першим і міняється місцями, якщо не в порядку. Цей процес повторюється для всіх наступних елементів.

Загалом, техніка вставки сортування порівнює кожен елемент з усіма його попередніми елементами та сортує елемент, щоб розмістити його у правильному положенні.

Як уже зазначалося, техніка сортування вставки є більш доцільною для меншого набору даних, і тому масиви з невеликою кількістю елементів можна сортувати за допомогою ефективної сортування вставки.

Сортування вставки особливо корисно при сортуванні зв’язаних структур даних списку. Як відомо, пов’язані списки мають покажчики, що вказують на його наступний елемент (окремо пов’язаний список) та попередній елемент (подвійний пов’язаний список). Це полегшує відстеження попереднього та наступного елементів.

Таким чином, простіше використовувати сортування вставки для сортування пов'язаних списків. Однак сортування займе багато часу, якщо елементів даних більше.

У цьому підручнику ми обговоримо техніку вставки, включаючи її алгоритм, псевдокод та приклади. Ми також реалізуємо програми Java для сортування масиву, списку з односпрямованим зв’язком та списку з подвійним зв’язком за допомогою сортування за вставкою.

Алгоритм сортування вставки

Алгоритм сортування вставки такий.

Крок 1 : Повторіть кроки 2 - 5 для K = 1 - N-1

Крок 2 : встановити температуру = A (K)

Крок 3 : встановити J = K - 1

Крок 4 :

Повторюйте під час темп<=A(J)
встановити A (J + 1) = A (J)
встановити J = J - 1
(кінець внутрішнього циклу)

Крок 5 :

встановити A (J + 1) = темп
(кінець циклу)

Крок 6 : вихід

Як відомо, сортування вставки починається з другого елемента, припускаючи, що перший елемент вже відсортований. Вищезазначені кроки повторюються для всіх елементів у списку, починаючи з другого елемента, і ставлять їх у потрібні позиції.

Псевдокод для сортування вставки

Псевдо-код для техніки сортування вставки наведено нижче.

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

Далі давайте побачимо ілюстрацію, яка демонструє сортування масиву за допомогою Insertion sort.

Сортування масиву за допомогою сортування за вставкою

Візьмемо приклад сортування вставки за допомогою масиву.

Масив для сортування має такий вигляд:

масив для сортування

Тепер для кожного проходу ми порівнюємо поточний елемент з усіма його попередніми елементами. Отже, під час першого проходу ми починаємо з другого елемента.

Порівняйте 2-й елемент з 1-м елементом

пройти 2

пройти 3

пройти 4

пройти 5

пройти 6

Таким чином, нам потрібно N кількість проходів, щоб повністю відсортувати масив, що містить N кількість елементів.

вбудовані функції c ++

Наведену вище ілюстрацію можна узагальнити у табличній формі, як показано нижче:

ПройтиНесортований списокпорівнянняВідсортований список
1{10,2,6,15,4,1}{10.2}{2,10, 6,15,4,1}
два{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}

Як показано на ілюстрації вище, в кінці кожного проходу один елемент переходить на належне місце. Отже, загалом, щоб розмістити N елементів на потрібному місці, нам потрібні проходи N-1.

Реалізація сортування вставки в Java

Наступна програма показує реалізацію сортування вставки в Java. Тут ми маємо масив, який потрібно відсортувати за допомогою сортування Insertion.

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

Вихід:

Оригінальний масив: (10, 6, 15, 4, 1, 45)
Відсортований масив: (1, 4, 6, 10, 15, 45)

Впровадження сортування вставки - результат

У наведеній вище реалізації видно, що сортування починається з 2йелемент масиву (змінна циклу j = 1), а потім поточний елемент порівнюється з усіма його попередніми елементами. Потім елемент розміщується у правильному положенні.

Сортування вставки ефективно працює для менших масивів та для масивів, які частково сортуються там, де сортування завершується за меншу кількість проходів.

Сортування вставки - це стабільне сортування, тобто воно підтримує порядок рівних елементів у списку.

Сортування пов’язаного списку за допомогою сортування за вставкою

Наступна програма Java демонструє сортування списку з єдиним зв’язком за допомогою сортування вставки.

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

Вихід:

Оригінальний зв’язаний список:
1 8 32 2 10
Відсортований зв’язаний список:
1 2 8 10 32

вихід - зв’язаний список

найкраще програмне забезпечення для відновлення даних для Windows -

У наведеній вище програмі ми визначили клас, який створює зв’язаний список і додає до нього вузли, а також сортує його. Оскільки однопов’язаний список має наступний вказівник, простіше відстежувати вузли при сортуванні списку.

Сортування подвійно пов’язаного списку за допомогою сортування за вставкою

Наступна програма сортує подвійно пов'язаний список за допомогою сортування вставки. Зауважте, що оскільки у подвійно пов’язаному списку є як попередній, так і наступний покажчики, під час сортування даних покажчики легко оновити та зв’язати.

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

Вихід:

Оригінальний подвійно пов’язаний список:
1 11 2 7 3 5
Сортований подвійно пов’язаний список:
1 2 3 5 7 11

Результат - подвійно пов’язаний список

Часті запитання

Q # 1) Що таке сортування вставки в Java?

Відповідь: Сортування вставки - це простий прийом сортування в Java, який ефективний для меншого набору даних і на місці. Передбачається, що перший елемент завжди сортується, а потім кожен наступний елемент порівнюється з усіма його попередніми елементами та розміщується у відповідному положенні.

Q # 2) Чому сортування вставки краще?

Відповідь: Сортування вставки швидше для менших наборів даних, коли інші методи, такі як швидке сортування, додають накладні витрати за допомогою рекурсивних викликів. Сортування вставки порівняно стабільніше, ніж інші алгоритми сортування, і вимагає менше пам'яті. Сортування вставки також працює ефективніше, коли масив майже відсортований.

Q # 3) Для чого використовується сорт вставки?

Відповідь: Сортування вставки в основному використовується в комп'ютерних програмах, які створюють складні програми, такі як пошук файлів, пошук шляхів та стиснення даних.

Q # 4)Яка ефективність сортування вставки?

Відповідь: Сортування вставки має середню ефективність випадків O (n ^ 2). Найкращий випадок для сортування вставки - це коли масив вже відсортовано, і це O (n). Найгірший показник для сортування вставки - це знову O (n ^ 2).

Висновок

Сортування вставки - це проста техніка сортування, яка працює з масивами або пов'язаними списками. Це корисно, коли набір даних менший. У міру збільшення набору даних цей прийом стає повільнішим та неефективним.

Сортування Insertion також є більш стабільним і на місці, ніж інші методи сортування. Немає накладних витрат на пам’ять, оскільки окрема структура не використовується для зберігання відсортованих елементів.

Сортування вставки добре працює при сортуванні пов'язаних списків, які є одночасно і подвійно пов'язаними списками. Це пов’язано з тим, що зв’язаний список складається з вузлів, пов’язаних за допомогою покажчиків. Отже, сортування вузлів стає простішим.

У нашому підручнику ми обговоримо ще один спосіб сортування в Java.

=> Прочитайте серію Easy Java Training.

Рекомендована література

^