Мени

Сортирање уметања у Јави - Алгоритам сортирања уметања и примери

  • Главни
  • Остало
  • Сортирање уметања у Јави - Алгоритам сортирања уметања и примери

insertion sort java insertion sort algorithm examples

Испробајте Наш Инструмент За Елиминисање Проблема

Овај водич објашњава сортирање уметања на Јави, укључујући његов алгоритам, псеудо-код и примере сортирања низова, појединачно повезане и двоструко повезане листе:

Техника алгоритма сортирања уметања је слична сортирању мехурића, али је мало ефикаснија. Разврставање уметања је изводљивије и ефикасније када је у питању мали број елемената. Када је скуп података већи, биће потребно више времена за сортирање података.

=> Овде погледајте водич за почетнике Јава.

бесплатни ИоуТубе за мп4 конвертер за мац

Сортирање уметања на Јави

Шта ћете научити:

Увод у сортирање уметања на Јави

У техници сортирања уметањем претпостављамо да је први елемент на листи већ сортиран и започињемо са другим елементом. Други елемент се упоређује са првим и замењује се ако није у реду. Овај поступак се понавља за све наредне елементе.

Генерално, техника сортирања уметањем упоређује сваки елемент са свим претходним елементима и сортира елемент тако да га постави у одговарајући положај.

Као што је већ поменуто, техника сортирања уметањем изводљивија је за мањи скуп података, па се стога низови са малим бројем елемената могу сортирати помоћу ефикасне сортирања уметањем.

Сортирање уметања је посебно корисно при сортирању повезаних структура података листе. Као што знате, повезане листе имају показиваче који воде на следећи елемент (појединачно повезана листа) и претходни елемент (двоструко повезана листа). Ово олакшава праћење претходних и следећих елемената.

Стога је једноставније користити сортирање уметања за сортирање повезаних листа. Међутим, сортирање ће потрајати пуно времена ако је више података.

У овом упутству ћемо размотрити технику сортирања уметања, укључујући њен алгоритам, псеудо-код и примере. Такође ћемо применити Јава програме за сортирање низа, појединачно повезану листу и двоструко повезану листу помоћу сортирања уметањем.

Алгоритам сортирања уметања

Алгоритам сортирања уметања је следећи.

Корак 1 : Поновите кораке 2 до 5 за К = 1 до Н-1

Корак 2 : постављена темп = А (К)

3. корак : скуп Ј = К - 1

4. корак :

Поновите док је темп<=A(J)
скуп А (Ј + 1) = А (Ј)
скуп Ј = Ј - 1
(крај унутрашње петље)

Корак 5 :

поставите А (Ј + 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

Даље, погледајмо илустрацију која приказује сортирање низа помоћу сортирања Инсертион.

Сортирање низа помоћу сортирања уметања

Узмимо пример сортирања уметањем помоћу низа.

Низ који ће се сортирати је следећи:

низ који се сортира

Сада за сваки пролаз упоређујемо тренутни елемент са свим претходним елементима. Дакле, у првом додавању почињемо са другим елементом.

Упоредите 2. елемент са 1. елементом

проћи 2

проћи 3

проћи 4

проћи 5

проћи 6

Дакле, потребан нам је Н број пролаза да бисмо у потпуности сортирали низ који садржи Н број елемената.

како учинити подразумевани мрежни пролаз доступним

Горња илустрација може се резимирати у табеларном облику као што је приказано доле:

ПассНесортирана листапоређењеСортирана листа
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}

Као што је приказано на горњој илустрацији, на крају сваког проласка један елемент иде на своје место. Отуда генерално, да бисмо поставили Н елемената на одговарајуће место, потребни су нам Н-1 пролази.

Имплементација сортирања уметања у Јави

Следећи програм приказује имплементацију сортирања Инсертион у Јави. Овде имамо низ који ћемо сортирати помоћу сортирања Инсертион.

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нделемент низа (променљива петље ј = 1), а затим се тренутни елемент упоређује са свим претходним елементима. Затим се елемент поставља у правилан положај.

Сортирање уметањем ефикасно функционише за мање низове и за низове који су делимично сортирани тамо где је сортирање завршено у мање пролаза.

Сортирање уметања је стабилна сорта, тј. Одржава редослед једнаких елемената на листи.

Сортирање повезане листе помоћу сортирања уметања

Следећи Јава програм приказује сортирање појединачно повезане листе помоћу сортирања Инсертион.

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

излаз - повезана листа

У горњем програму дефинисали смо класу која креира повезану листу и додаје јој чворове, као и сортира је. Како појединачно повезана листа има следећи показивач, лакше је водити евиденцију чворова приликом сортирања листе.

Сортирање двоструко повезане листе помоћу сортирања уметања

Следећи програм сортира двоструко повезану листу помоћу сортирања уметањем. Имајте на уму да, пошто двоструко повезана листа има и претходне и следеће показиваче, показиваче је лако ажурирати и повезати док сортирате податке.

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

Излаз - двоструко повезана листа

Често постављана питања

П # 1) Шта је сортирање уметања у Јави?

Одговор: Сортирање уметањем је једноставна техника сортирања у Јави која је ефикасна за мањи скуп података и на месту. Претпоставља се да се први елемент увек сортира, а затим се сваки следећи елемент упоређује са свим претходним елементима и поставља у свој одговарајући положај.

К # 2) Зашто је сортирање уметања боље?

Одговор: Сортирање уметања је брже за мање скупове података када се друге технике попут брзог сортирања додају преко рекурзивних позива. Сортирање уметања је релативно стабилније од осталих алгоритама за сортирање и захтева мање меморије. Сортирање уметања такође делује ефикасније када је низ скоро сортиран.

К # 3) За шта се користи сорта уметања?

која је разлика између линука и уника

Одговор: Разврставање уметања углавном се користи у рачунарским апликацијама које граде сложене програме попут претраживања датотека, проналажења путање и компресије података.

К # 4)Која је ефикасност сортирања уметања?

Одговор: Сортирање уметања има просечне перформансе случаја од О (н ^ 2). Најбољи случај за сортирање уметања је када је низ већ сортиран и то је О (н). Најгоре перформансе за сортирање уметања су поново О (н ^ 2).

Закључак

Сортирање уметањем је једноставна техника сортирања која ради на низовима или повезаним листама. Корисно је када је скуп података мањи. Како се скуп података повећава, ова техника постаје све спорија и неефикаснија.

Сорта уметања је такође стабилнија и стабилнија од осталих техника сортирања. Не постоји додатна меморија јер се засебна структура не користи за чување сортираних елемената.

Сортирање уметања добро делује на сортирању повезаних листа које су и појединачно и двоструко повезане листе. То је зато што повезану листу чине чворови повезани преко показивача. Стога сортирање чворова постаје лакше.

У нашем предстојећем упутству, разговараћемо о још једној техници сортирања у Јави.

=> Прочитајте серију Еаси Јава Траининг.

Препоручено читање

^