Learning Sorting Algorithms in Depth
Demonstrating linked lists, sort keys, and other complex concepts through sorting algorithms.
Implement a Sort into your LL in Jupyter Notebook … Here is concept.
Implementing Linked Lists
Before completing this, I had to do some reserach on what a linked list was. From research, I was able to summarize what I found.
A linked list is a linear data structure where elements are stored in nodes. Each node contains a data element and a reference (or pointer) to the next node in the sequence. Linked lists are dynamic data structures, meaning that the size of the list can be modified during program execution by adding or removing nodes.
In Java, linked lists can be implemented using the LinkedList class from the java.util package or by implementing a custom linked list.
Here’s an example of a singly linked list implementation in Java:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.display(); // Output: 1 2 3
}
}
Main.main(null);
1 2 3
In this example, each node contains an integer value (data) and a reference to the next node (next). The LinkedList class maintains a reference to the head of the list. The add() method inserts a new node at the end of the list, and the display() method prints the elements of the list.
After researching what linked lists were, the next step was to implement linked lists conceptually with sorting algorithms. Since we are going in depth with insertion sort, we will implement linked lists with insertion sort. Below is our demonstration of this:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void insert(int data) {
Node newNode = new Node(data);
if (head == null || head.data >= newNode.data) {
newNode.next = head;
head = newNode;
} else {
Node current = head;
while (current.next != null && current.next.data < newNode.data) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public void insertionSort() {
if (head == null || head.next == null)
return;
Node sortedList = null;
Node current = head;
while (current != null) {
Node next = current.next;
sortedList = sortedInsert(sortedList, current);
current = next;
}
head = sortedList;
}
private Node sortedInsert(Node sortedList, Node newNode) {
if (sortedList == null || sortedList.data >= newNode.data) {
newNode.next = sortedList;
return newNode;
} else {
Node current = sortedList;
while (current.next != null && current.next.data < newNode.data) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
return sortedList;
}
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(5);
list.insert(3);
list.insert(8);
list.insert(1);
list.insert(9);
System.out.println("Before sorting:");
System.out.println("9 1 8 3 5");
// list.display();
list.insertionSort();
System.out.println("After sorting:");
list.display();
}
}
Main.main(null);
Before sorting:
9 1 8 3 5
After sorting:
1 3 5 8 9
This program demonstrates the insertion sort algorithm on a linked list. The insert() method is responsible for adding elements to the linked list, and the insertionSort() method implements the insertion sort algorithm. The sortedInsert() method inserts a node into a sorted sublist. Finally, the display() method is used to print the elements of the linked list before and after sorting.
Capabilities of Object Overrides
To utilize the capabilities of object overrides with toString() and compareTo() methods for sorting, we can implement the Comparable interface in the Node class and override the compareTo() method to define the natural ordering of nodes based on their data. Additionally, we can override the toString() method in the Node class to provide a string representation of the node’s data, as seen in the revised code below:
class Node implements Comparable<Node> {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.data, other.data);
}
@Override
public String toString() {
return Integer.toString(data);
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void insert(int data) {
Node newNode = new Node(data);
if (head == null || head.compareTo(newNode) >= 0) {
newNode.next = head;
head = newNode;
} else {
Node current = head;
while (current.next != null && current.next.compareTo(newNode) < 0) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.toString() + " ");
current = current.next;
}
System.out.println();
}
public void insertionSort() {
if (head == null || head.next == null)
return;
Node sortedList = null;
Node current = head;
while (current != null) {
Node next = current.next;
sortedList = sortedInsert(sortedList, current);
current = next;
}
head = sortedList;
}
private Node sortedInsert(Node sortedList, Node newNode) {
if (sortedList == null || sortedList.compareTo(newNode) >= 0) {
newNode.next = sortedList;
return newNode;
} else {
Node current = sortedList;
while (current.next != null && current.next.compareTo(newNode) < 0) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
return sortedList;
}
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(5);
list.insert(3);
list.insert(8);
list.insert(1);
list.insert(9);
System.out.println("Before sorting:");
System.out.println("9 1 8 3 5");
// list.display();
list.insertionSort();
System.out.println("After sorting:");
list.display();
}
}
Main.main(null);
Before sorting:
9 1 8 3 5
After sorting:
1 3 5 8 9
In this updated code:
- The
Nodeclass implements theComparable<Node>interface, which requires the implementation of thecompareTo()method. This method compares two nodes based on theirdatavalues. - The
toString()method is overridden in theNodeclass to provide a string representation of the node’s data. - The insertion sort algorithm in the
LinkedListclass utilizescompareTo()for sorting. - When displaying the elements of the linked list, the
toString()method is called implicitly to convert each node’s data to a string representation.
To demonstrate changing sort keys with tester methods, we can modify the existing code to allow the user to specify a different attribute as the sort key. We’ll add a new method changeSortKey() in the LinkedList class that allows the user to change the sorting key. This method will accept a function or a lambda expression to extract the key from the Node objects. Additionally, we’ll update the insertionSort() method to use this key extractor when comparing nodes during sorting.
import java.util.function.Function;
class Node implements Comparable<Node> {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.data, other.data);
}
@Override
public String toString() {
return Integer.toString(data);
}
}
class LinkedList {
Node head;
Function<Node, Comparable> keyExtractor;
public LinkedList() {
this.head = null;
// Default key extractor
this.keyExtractor = node -> node.data;
}
public void insert(int data) {
Node newNode = new Node(data);
if (head == null || keyExtractor.apply(head).compareTo(keyExtractor.apply(newNode)) >= 0) {
newNode.next = head;
head = newNode;
} else {
Node current = head;
while (current.next != null && keyExtractor.apply(current.next).compareTo(keyExtractor.apply(newNode)) < 0) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.toString() + " ");
current = current.next;
}
System.out.println();
}
public void insertionSort() {
if (head == null || head.next == null)
return;
Node sortedList = null;
Node current = head;
while (current != null) {
Node next = current.next;
sortedList = sortedInsert(sortedList, current);
current = next;
}
head = sortedList;
}
private Node sortedInsert(Node sortedList, Node newNode) {
if (sortedList == null || keyExtractor.apply(sortedList).compareTo(keyExtractor.apply(newNode)) >= 0) {
newNode.next = sortedList;
return newNode;
} else {
Node current = sortedList;
while (current.next != null && keyExtractor.apply(current.next).compareTo(keyExtractor.apply(newNode)) < 0) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
return sortedList;
}
}
// Method to change the sort key extractor
public void changeSortKey(Function<Node, Comparable> keyExtractor) {
this.keyExtractor = keyExtractor;
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(5);
list.insert(3);
list.insert(8);
list.insert(1);
list.insert(9);
System.out.println("Before sorting:");
list.display();
// Default sorting by data
list.insertionSort();
System.out.println("After sorting by data:");
list.display();
// Change sorting key to the next node's data
list.changeSortKey(node -> node.next != null ? node.next.data : Integer.MAX_VALUE);
list.insertionSort();
System.out.println("After sorting by next node's data:");
list.display();
}
}
Main.main(null);
Before sorting:
1 3 5 8 9
After sorting by data:
1 3 5 8 9
After sorting by next node's data:
3 5 8 9 1
In this modified code:
- We added a new field
keyExtractorin theLinkedListclass, which is aFunction<Node, Comparable>. This function is responsible for extracting the sort key from aNodeobject. - The
changeSortKey()method allows the user to change the sorting key extractor at runtime. - In the main method, after the initial sorting, we demonstrate changing the sort key extractor to sort by the data of the next node (
node.next.data). This changes the sorting behavior of the linked list.