Sorting algorithms are foundational tools in computer science, providing a structured way to arrange data efficiently. Among these algorithms, the Insertion Sort algorithm stands out for its simplicity and effectiveness. In this introduction, we’ll provide a brief overview of sorting algorithms, introduce the Insertion Sort algorithm, and highlight its importance and use cases in Java programming.
Sorting algorithms are methods or procedures that systematically organize elements in a collection or array in a specific order. The efficiency of these algorithms is crucial for optimizing search and retrieval operations in various applications.
What is Insertion Sort Algorithm?
Insertion Sort is a straightforward algorithm that builds the final sorted array one element at a time. It iterates through an input array, comparing each element with the ones before it and placing it in the correct position. The process continues until the entire array is sorted.
Importance and Use Cases in Java Programming
Insertion Sort’s simplicity and efficiency make it a valuable tool in Java programming. It is particularly useful for small datasets or partially sorted arrays, where its straightforward implementation provides an advantage. Understanding the Insertion Sort algorithm is fundamental for any Java developer aiming to master sorting techniques and optimize the performance of their applications.
Insertion sort using function
// 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);
}
};
Learn more about the Bubble Sort in Java and Binary Search in Java now!
Explanation of the code:
This Java code implements the Insertion Sort algorithm to arrange an array in ascending order. Here’s an explanation:
1. Function `sort(int arr[])`:
- Iterates through each element starting from the second.
- Takes the current element as `key` and compares it with the elements before it, shifting them to the right until finding the correct position for `key`.
- Inserts `key` in its sorted position.
2. Static Method `printArray(int arr[])`:
- Prints the sorted array to the console.
3. `main` Method:
- Initializes an array `arr` with unsorted elements.
- Creates an instance of `InsertionSortEx` class.
- Calls the `sort` method to sort the array.
- Calls the `printArray` method to display the sorted array.
The insertion sort is a simple and efficient algorithm for sorting small datasets. It builds the sorted array one element at a time, making it suitable for partially sorted arrays or real-time applications.
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);
}
}
Explanation of the code:
This Java code implements the Insertion Sort algorithm for a singly linked list. Here’s an explanation:
1. Node Class `node`: Defines a node structure for the linked list with an integer value (`val`) and a reference to the next node (`next`).
2. `add` Method: Adds a new node with a given value to the linked list. The new node is added at the beginning of the list.
3. `insertionSort` Method:
Sorts the linked list using the insertion sort algorithm. The sorted list is represented by the `sorted` variable, initially set to `null`. The method traverses the original linked list, and for each node, it calls the `Insertsorted` method to insert the node into the sorted list.
4. `Insertsorted` Method: Inserts a new node into the sorted list in ascending order. Handles the case when the new node becomes the new head of the sorted list. Finds the correct position for the new node in the sorted list.
5. `print_Llist` Method: Prints the nodes of the linked list.
6. `main` Method:
- Creates a linked list object (`list`) and adds nodes to it.
- Prints the original linked list.
- Calls `insertionSort` to sort the linked list using insertion sort.
- Prints the sorted linked list.
This code demonstrates how to perform insertion sort on a singly linked list in Java.
Dive into Linear Search in Java Now!
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);
}
}
Explanation of the code: This Java code implements the Insertion Sort algorithm for a doubly linked list.
1. Node Class `Node`: Defines a doubly linked list node structure with integer data, a reference to the previous node (`prev`), and a reference to the next node (`next`).
2. `getNode` Function:Returns a new node in the doubly linked list with the provided data.
3. `insert_Sorted` Function:
Inserts a new node into the sorted doubly linked list in ascending order.
Handles cases when the list is empty, or the new node becomes the new head of the list.
4. `insertion_Sort` Function:
Sorts the doubly linked list using insertion sort.
Initializes an initially empty sorted list and traverses the original list, inserting nodes into the sorted list.
5. `print_DLL` Function: Prints the nodes of the doubly linked list.
6. `addNode` Function: Adds a new node with the given data to the beginning of the doubly linked list.
7. `main` Method:
- Creates an empty doubly linked list (`head`).
- Adds nodes to the list.
- Prints the original list.
- Calls `insertion_Sort` to sort the doubly linked list using insertion sort.
- Prints the sorted list.
This code demonstrates how to perform insertion sort on a doubly linked list in Java.
Output:
Original doubly linked list:3 9 8 2 4 6
Sorted Doubly Linked List:
2 3 4 6 8 9 We hope you find our ‘Insertion Sort in Java’ useful and informative. For more courses visit our official website Newtum, where you can find resources to master coding in different languages such as JS, Java, and Python.
About The Author
