(Last Updated On: 27/10/2023)
// Insertion Sort in Java
public class InsertionSortEx {
/*Function to sort array using insertion sort*/
void sort(int arr[])
{
int num = arr.length;
for (int i = 1; i < num; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
/* A utility function to print array of size n*/
static void printArray(int arr[])
{
int num = arr.length;
System.out.println("the sorted array is");
for (int i = 0; i < num; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method
public static void main(String args[])
{
int arr[] = { 8, 1, 2, 9, 6, 3, 7 };
InsertionSortEx ob = new InsertionSortEx();
ob.sort(arr);
printArray(arr);
}
};
Output:
the sorted array is
1 2 3 6 7 8 9
Sorting A Linked List Using Insertion Sort
// Insertion Sort in Java
import java.util.*;
class InsertionSortEx {
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 insertionSort(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
Insertsorted(current);
// now next becomes current
current = next;
}
// update head to point to linked list
head = sorted;
}
//insert a new node in sorted list
void Insertsorted(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 < newNode.val) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
//display nodes of the linked list
void print_Llist(node head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
}
}
class Main{
public static void main(String[] args)
{
//define linked list object
InsertionSortEx list = new InsertionSortEx();
//add nodes to the list
list.add(5);
list.add(9);
list.add(10);
list.add(4);
list.add(3);
//print the original list
System.out.println("Original Linked List:");
list.print_Llist(list.head);
//sort the list using insertion sort
list.insertionSort(list.head);
//print the sorted list
System.out.println("\nSorted Linked List:");
list.print_Llist(list.head);
}
}
Output:
Original Linked List:
3 4 10 9 5
Sorted Linked List:
3 4 5 9 10
Sorting A Doubly-Linked List Using Insertion Sort
// Insertion Sort in Java
public class InsertionSortEx {
// 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 < newNode.data)
current = current.next;
//update the pointers
newNode.next = current.next;
if (current.next != null)
newNode.next.prev = newNode;
current.next = newNode;
newNode.prev = current;
}
return head_ref;
}
// sort a doubly linked list using insertion sort
static Node insertion_Sort(Node head_ref) {
// sorted doubly linked list - initially empty
Node sorted = null;
// Traverse the DLL and insert nodes to sorted list
Node current = head_ref;
while (current != null) {
// current.next goes into next
Node next = current.next;
// set all links to null
current.prev = current.next = null;
// current goes in sorted DLL
sorted=insert_Sorted(sorted, current);
// next now becomes current
current = next;
}
// Update head_ref to point to sorted doubly linked list
head_ref = sorted;
return head_ref;
}
// function to print the doubly linked list
static void print_DLL(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
// add new node to DLL at the beginning
static Node addNode(Node head_ref, int newData){
// create a new node
Node newNode = new Node();
// assign data
newNode.data = newData;
// Make next of new node as head and previous as null
newNode.next = (head_ref);
newNode.prev = null;
// head=>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, 6);
head=addNode(head, 4);
head=addNode(head, 2);
head=addNode(head, 8);
head=addNode(head, 9);
head=addNode(head, 3);
System.out.println( "Original doubly linked list:");
print_DLL(head);
head=insertion_Sort(head);
System.out.println("\nSorted Doubly Linked List:");
print_DLL(head);
}
}
Output:
Original doubly linked list:3 9 8 2 4 6
Sorted Doubly Linked List:
2 3 4 6 8 9
