Question: Write in Java to implement the BubbleSort that is presented in algorit
ID: 3886709 • Letter: Q
Question
Question: Write in Java to implement the BubbleSort that is presented in algorithm 1. In your implementation use a singly linked list data structure and make sure that your data structure doesn’t make your BubbleSort implementation less efficient than standard BubbleSort.
Hint: you can use any implementation of linked list but you cannot use those operations that are accessing nodes in two-ways (your usage must comply with singly linked list). The second requirement is total time complexity, don’t simply assume all linked list operations are of O(1) complexity. With these requirements if you think java linked list is suitable go ahead and use it otherwise implement linked list yourself or use another implementation.
And please explain each line of code that you write :-)
Array Inversion Let a be a list data structure of length n >0 and let i,j e [0,...,n-1) with i a[] Example Consider indexes: (0,1,2,3,4,5) a= (1,2, 4,3,5,0) then a has the following inversions set of inversions: t(0,5), (1,5), (2,5), (2,3), (3,5), (4,5)) values of the inversions: (1,0), (2,0), (4,0), (4,3), (3,0), (5,0)) Notice that the inversions are the pairs of indices, not pairs of values. The reason is of course that indices are unique, while value are not necessarily unique Algorithm 1 BubbleSort Require: a is a list data structure of length n>0 swapped true while R 2 0 and swapped = true do swapped false for i 0 to R do if a[i] > asi+ 1] thern swapped true SWAP(a, i,i +1) end if end for RR-1 end while Ensure: a is an ordered permutation of à Stable Sorting Let be a list data structure of length n > 0.Furthermore let S be a sorting algorithm and a be the ordered permutation of after applying S according to the total order relation with associated equality relation =. We call S stable if and only if for all a, y € with [i] = z-y = [3] and iExplanation / Answer
Please find my implementation.
class Node {
int data;
Node nextNode;
public Node(int data) {
this.data = data;
this.nextNode = null;
}
public int getData() {
return this.data;
}
}
public class BubbleSort {
private Node head;
private int size;
public Node sort() {
if (size > 1) {
boolean isSwapped;
do {
Node current = head;
Node previous = null;
Node next = head.nextNode;
isSwapped = false;
while ( next != null ) {
// if current node data value is greater than next node value
if (current.data > next.data) {
// make this flag as true
isSwapped = true;
// swapping current and next node
if ( previous != null ) {
Node sig = next.nextNode;
previous.nextNode = next;
next.nextNode = current;
current.nextNode = sig;
} else { // head node is out of order
Node sig = next.nextNode;
head = next;
next.nextNode = current;
current.nextNode = sig;
}
previous = next;
next = current.nextNode;
} else { // moving forward
previous = current;
current = next;
next = next.nextNode;
}
}
} while( isSwapped ); // if there is swap in previous iteration then go for next iteration
}
return head;
}
public void add(int data) {
Node node = new Node(data);
if (head == null) {
head = node;
} else {
Node currentNode = head;
while(currentNode.nextNode != null) {
currentNode = currentNode.nextNode;
}
currentNode.nextNode = node;
}
size++;
}
public void printData() {
Node currentNode = head;
while(currentNode != null) {
int data = currentNode.getData();
System.out.println(data);
currentNode = currentNode.nextNode;
}
}
public static void main (String[]args) {
BubbleSort obj = new BubbleSort();
obj.add(8);
obj.add(7);
obj.add(6);
obj.add(4);
obj.add(3);
obj.add(1);
System.out.println("Before sorting: ");
obj.printData();
obj.sort();
System.out.println("After sorting: ");
obj.printData();
}
}
/*
Sample output:
Before sorting:
8
7
6
4
3
1
After sorting:
1
3
4
6
7
8
*/
Time Complexity: O(n^2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.