Write an implementation of bubble sort as an instance method called sort() for t

Question

Write an implementation of bubble sort as an instance method called sort() for the LinkedList class developed in lecture. sort()should take a Comparator as a parameter. You may not use arrays in your implementation. Hint 1: The simplest solution to this question will not involve changing the structure of the linked list. That is, the values in the linked list may change, but the links between nodes will not change. Hint 2: You may find it helpful to refer to the following alternative implementation of bubble sort over arrays as a reference for your implementation over linked lists.

public static void bubbleSort(T[] a, Comparator c) { boolean swapped = true; int limit = a.length; while (limit != 1 && swapped) { swapped = false; int j = 0; while (j + 1 != limit) { if (c.compare(a[j + 1], a[j]) < 0) { swapped = true; T temp = a[j + 1]; a[j + 1] = a[j]; a[j] = temp; } j++; } limit = j; } }

Explanation / Answer

Given below is the completed code for the question.
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
Please do rate the answer if it was helpful. Thank you

import java.util.NoSuchElementException;
import java.util.Comparator;
import java.util.Iterator;

public class LinkedList<T> implements List<T> {
private ListNode<T> header = new ListNode<T>();

public boolean isEmpty() {
return header.getNext() == null;
}

public T getFirst() {
ListNode<T> first = header.getNext();
if (first == null) {
throw new EmptyListException();
} else {
return first.getValue();
}
}

public void addFirst(T element) {
// Create a new node
ListNode<T> newNode = new ListNode<T>();

// Store the new element in the new node
newNode.setValue(element);

// Link the new node to the old first node
newNode.setNext(header.getNext());

// Set the new node as the first node
header.setNext(newNode);
}

public void removeFirst() {
ListNode<T> first = header.getNext();
if (first == null) {
throw new EmptyListException();
} else {
header.setNext(first.getNext());
}
}

public void clear() {
header.setNext(null);
}

private ListNode<T> findByIndex(int index) {
int k = 0;
ListNode<T> current = header.getNext();

while (k < index && current != null) {
k++;
current = current.getNext();
}

if (current == null) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + k);
} else {
return current;
}
}

public T get(int index) {
return findByIndex(index).getValue();
}

public void set(int index, T element) {
findByIndex(index).setValue(element);
}

private void scanToIndex(Iterator<T> iterator, int index) {
int k = -1;

while (k < index && iterator.hasNext()) {
k++;
iterator.next();
}

if (k < index) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + (k + 1));
}
}

private void scanToEnd(Iterator<T> iterator) {
int k = -1;

while (iterator.hasNext()) {
k++;
iterator.next();
}
}

public void add(int index, T element) {
ListIterator<T> iterator = listIterator();
scanToIndex(iterator, index - 1);
iterator.add(element);
}

public void addLast(T element) {
ListIterator<T> iterator = listIterator();
scanToEnd(iterator);
iterator.add(element);
}

public void remove(int index) {
ListIterator<T> iterator = listIterator();
scanToIndex(iterator, index);
iterator.remove();
}

public void removeLast() {
ListIterator<T> iterator = listIterator();
scanToEnd(iterator);
iterator.remove();
}

public int size() {
int k = 0;
ListNode<T> current = header.getNext();

while (current != null) {
k++;
current = current.getNext();
}

return k;
}

public String toString() {
ListNode<T> current = header.getNext();
if (current == null) {
return "[]";
} else {
StringBuilder stringBuilder = new StringBuilder("[");
stringBuilder.append(current.getValue());

while (current.getNext() != null) {
stringBuilder.append(", ");
current = current.getNext();
stringBuilder.append(current.getValue());
}

stringBuilder.append("]");
return stringBuilder.toString();
}
}

public void sort(Comparator<T> c) {
ListNode<T> min;
for(ListNode<T> i = header.getNext(); i != null; i = i.getNext()){
min = i;
for(ListNode<T> j = i.getNext(); j != null; j = j.getNext()){
if(c.compare(j, min) < 0)
{
min = j;
}
}

if(min != i){
//swap
T temp = min.getValue();
min.setValue(i.getValue());
i.setValue(temp);
}
}
}

public LinkedListIterator<T> iterator() {
return new LinkedListIterator<T>(header);
}

public LinkedListIterator<T> listIterator() {
return new LinkedListIterator<T>(header);
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.