Sorting a LinkedList of objects using bubble sort
A few issues:
Your
setBookmethod -- taking a year and title -- seems to mutate the book that is assigned to the node. This is not really the right approach. You should define a method that leaves the books untouched, but assigns a different book (all together) to a node.Bubble sort will always start the inner loop from the first item in the list. The outer loop would only serve to count the number of times the inner loop has to kick in. This is not how you have implemented it. If the minimum node is not in the first or second place, your algorithm will never move it all the way back to the first position.
I would suggest to take a different approach and only mutate the next references in the list, so that you swap nodes as a whole, without having to touch the data at all. For this to work, you need a prev reference that walks "behind" the current node, so that you can rewire the preceding node to the node that gets swapped with the current node.
Here is an implementation:
public void sortByYear(){
if (head == null || head.getNext() == null) {
return;
}
for (Node iter = head; iter != null; iter = iter.getNext()) {
Node prev = null;
Node current = head;
for (Node next = current.getNext(); next != null; next = current.getNext()) {
if (current.getBook().getYear() > next.getBook().getYear()) {
if (prev == null) {
head = next;
} else {
prev.setNext(next);
}
current.setNext(next.getNext());
next.setNext(current);
prev = next;
} else {
prev = current;
current = next;
}
}
}
}
Something you could still work on
It would become even nicer if you would make your Node class comparable. That way the if statement can become more generic and less tied to your book-related implementation.
Bubble Sort Manually a Linked List in Java
The problem, as expected, comes in method sort():
public void sort() {
if (size > 1) {
for (int i = 0; i < size; i++ ) {
Node currentNode = head;
Node next = head.nextNode;
for (int j = 0; j < size - 1; j++) {
if (currentNode.data > next.data) {
Node temp = currentNode;
currentNode = next;
next = temp;
}
currentNode = next;
next = next.nextNode;
}
}
}
}
A minor problem is just do always execute the bubble sort n*n times. It is actually better check whether there was a change between any pair in the list. If it was, then there is the need to run again all over the list; if not, there isn't. Think of the marginal case in which a list of 100 elements is already sorted when sort() is called. This means that nodes in the list would be run over for 10000 times, even when there is actually nothing to do!
The main problem, though, is that you are exchanging pointers to the nodes in your list.
if (currentNode.data > next.data) {
Node temp = currentNode;
currentNode = next;
next = temp;
}
If you translate currentNode by v[i] and next by v[i - 1], as if you were sorting an array, that would do. However, you are just changing pointers that you use to run over the list, without effect in the list itself. The best solution (well, provided you are going to use BubbleSort, which is always the worst solution) would be to exchange the data inside the nodes.
if (currentNode.data > next.data) {
int temp = currentNode.data;
currentNode.data = next.data;
next.data = temp;
}
However, for a matter of illustration of the concept, I'm going to propose changing the links among nodes. These pointers are the ones which actually mark the sorting in the list. I'm talking about the nextNode attribute in the Node class.
Enough chat, here it is:
public void sort() {
if (size > 1) {
boolean wasChanged;
do {
Node current = head;
Node previous = null;
Node next = head.nextNode;
wasChanged = false;
while ( next != null ) {
if (current.data > next.data) {
/*
// This is just a literal translation
// of bubble sort in an array
Node temp = currentNode;
currentNode = next;
next = temp;*/
wasChanged = true;
if ( previous != null ) {
Node sig = next.nextNode;
previous.nextNode = next;
next.nextNode = current;
current.nextNode = sig;
} else {
Node sig = next.nextNode;
head = next;
next.nextNode = current;
current.nextNode = sig;
}
previous = next;
next = current.nextNode;
} else {
previous = current;
current = next;
next = next.nextNode;
}
}
} while( wasChanged );
}
}
The explanation for a "double" code managing the node exchange is that, since you have to change the links among nodes, and this is just a single linked list, then you have to keep track of the previous node (you don't have a header node, either), which the first time is head.
if ( previous != null ) {
Node sig = next.nextNode;
previous.nextNode = next;
next.nextNode = current;
current.nextNode = sig;
} else {
Node sig = next.nextNode;
head = next;
next.nextNode = current;
current.nextNode = sig;
}
You can find the code in IdeOne, here: http://ideone.com/HW5zw7
Hope this helps.
Bubble sorting a linked list in C
Ordinary bubble-sort implementations for sorting arrays make use of the direct addressing and a known size of the array: they naturally use indices, that is ordinal numbers of items, so they can easily shrink the area sorted as the work progresses, because they know how many items are already on their final places.
A linked list is processed purely sequentially, so it doesn't allow such simple optimization without adding artificial 'index', incremented along the list iteration. That's why it's easiest to iterate always through the whole list and terminate when no more items were swapped, hence the list is sorted:
void sort(void)
{
int swapped = 1;
while(swapped)
{
node **prev = &head, *curr, *next;
swapped = 0;
for(curr = head; curr; prev = & curr->link, curr = curr->link)
{
next = curr->link;
if(next && curr->i > next->i)
{
curr->link = next->link;
next->link = curr;
*prev = next;
swapped = 1;
}
}
}
}
EDIT – some explanations in reply to questions in Matthew2015 comments.
Logical conditions in C expect a numeric or pointer expression which are considered 'true' if they are different from zero or different from NULL, respectively. That means while(swapped) is essentially equivalent to while(swapped != 0) and next && ... is equivalent to next != NULL && .... The condition in while(swapped != 0) means the loop will terminate when some execution of internal for does not set swapped to 1, which happens when no item in the list is greater than its successor – that is, when the list is sorted.
The for loop condition expression is curr alone, equivalent to curr != NULL. That makes the for loop iterate along the list until there is no 'current' node.
The node **prev variable points to a pointer, which points to the current node. When the 'current' and the 'next' node need to be swapped, then the 'previous' link should no longer point to the 'current' node but to the 'next' node instead. Of course one might keep the pointer to the 'previous node' and assign a new value to the (previous node)->link — but that would not work in case of the first node in a list, which has no 'previous node' but is pointed to by the head variable. One must use additional condition to verify if the current node is the first node to resolve this inconsistency. Having a pointer to pointer, which originally points to head and then to 'previous node'.link makes the whole code much simpler, shorter and also a bit faster.
Bubble sort in c linked list
We beginners should help each other.:)
I did not look through all your code. However it is obviously incorrect for example due to the incorrect order of allocations of nodes in this loop
while (c < 15) {
fgets(buffer, 1024, ifp);
sscanf(buffer, "%19[^,], %d", temp->name, &temp->number);
printf("%d %s %d\n", c, temp->name, temp->number);
temp->next = malloc(sizeof(struct node));
temp = temp->next;
temp->next = NULL;
c++;
}
So the last node will have data members with indeterminate values except the data member next.
I am trying to answer your question how to write a bubble sort function for a singly-linked list.
To write a bubble sort function for a singly-linked list is not an easy task for such beginners as you and me. For example you need to write correctly a swap function for nodes of the list.
Here you are.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char name[20];
int id;
struct node *next;
};
int push_back( struct node **head, const char *name, int id )
{
struct node *tmp = malloc( sizeof( struct node ) );
int success = tmp != NULL;
if ( success )
{
while ( *head != NULL ) head = &( *head )->next;
strcpy( tmp->name, name );
tmp->id = id;
tmp->next = NULL;
*head = tmp;
}
return success;
}
void display( struct node **head )
{
for ( struct node *current = *head; current != NULL; current = current->next )
{
printf( "{ %s, %d } ", current->name, current->id );
}
}
void swap( struct node **current )
{
struct node *tmp = ( *current )->next->next;
( *current )->next->next = *current;
*current = ( *current )->next;
( *current )->next->next = tmp;
}
void bubble_sort( struct node **head, int cmp( const void *, const void * ) )
{
if ( *head != NULL )
{
for ( struct node *last = NULL, *swapped = NULL; ( *head )->next != last; last = swapped )
{
swapped = ( *head )->next;
for ( struct node **first = head; ( *first )->next != last; first = &( *first )->next )
{
if ( cmp( ( *first )->next, *first ) < 0 )
{
swap( first );
swapped = ( *first )->next;
}
}
}
}
}
int cmp_id( const void *a, const void *b )
{
const struct node *left = a;
const struct node *right = b;
return ( right->id < left->id ) - ( left->id < right->id );
}
int cmp_name( const void *a, const void *b )
{
const struct node *left = a;
const struct node *right = b;
return strcmp( left->name, right->name );
}
int main(void)
{
struct node *head = NULL;
push_back( &head, "NameA", 25 );
push_back( &head, "NameB", 33 );
push_back( &head, "NameC", 23 );
push_back( &head, "NameD", 39 );
display( &head );
putchar( '\n' );
bubble_sort( &head, cmp_id );
display( &head );
putchar( '\n' );
bubble_sort( &head, cmp_name );
display( &head );
putchar( '\n' );
return 0;
}
The program output is
{ NameA, 25 } { NameB, 33 } { NameC, 23 } { NameD, 39 }
{ NameC, 23 } { NameA, 25 } { NameB, 33 } { NameD, 39 }
{ NameA, 25 } { NameB, 33 } { NameC, 23 } { NameD, 39 }
In the demonstrative program at first the list is sorted by IDs and then by names.
Thus all you need now is to build correctly the list from data in the used file.
Implement sorting in linked list in JavaScript (bubble sort or another)
Bubble sort can be implemented by adding this method:
bubbleSort() {
let last = this.tail;
while (last) {
let node = this.head;
while (node != last) {
let next = node.next
if (node.value > next.value) { // swap
[node.value, next.value] = [next.value, node.value];
}
node = next;
}
last = last.prev; // shorten the range that must be bubbled through
}
}
Here it is combined with your code (but using plain JavaScript, and allowing the constructor to take an argument):
class LinkedListNode {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class LinkedList {
constructor(iterable) { // Allow to initialise from an iterable
this.head = null;
this.tail = null;
if (iterable) {
for (let value of iterable) this.addTailNode(value);
}
}
addHeadNode(value) {
const newLinkendListNode = new LinkedListNode(value);
if (!this.head) {
this.head = newLinkendListNode;
this.tail = newLinkendListNode;
} else {
this.head.prev = newLinkendListNode;
newLinkendListNode.next = this.head;
this.head = newLinkendListNode;
}
}
addTailNode(value) {
const newLinkendListNode = new LinkedListNode(value);
if (!this.tail) {
this.head = newLinkendListNode;
this.tail = newLinkendListNode;
} else {
this.tail.next = newLinkendListNode;
newLinkendListNode.prev = this.tail;
this.tail = newLinkendListNode;
}
}
getByIndex(index) {
let currentNode = this.head;
while (currentNode) {
if (!index--) return currentNode;
currentNode = currentNode.next;
}
return null;
}
bubbleSort() {
let last = this.tail;
while (last) {
let node = this.head;
while (node != last) {
let next = node.next
if (node.value > next.value) { // swap
[node.value, next.value] = [next.value, node.value];
}
node = next;
}
last = last.prev; // shorten the range that must be bubbled through
}
}
* [Symbol.iterator]() {
let node = this.head;
while (node) {
yield node.value;
node = node.next;
}
}
toString() {
return Array.from(this).join(",");
}
}
// Demo
let list = new LinkedList([1, 10, 5, 7, 3, 2, 9, 8, 4, 6]);
console.log("before:", String(list));
list.bubbleSort();
console.log("after: ", String(list));Related Topics
How to Determine the Amount of Linux System Ram in C++
Creating Array of Objects on the Stack and Heap
Difference Between A* Pa = New A; and A* Pa = New A();
How to Simulate a Mouse Movement
Why Must Std::Sort Compare Function Return False When Arguments Are Equal
What Is the Safe Way to Fill Multidimensional Array Using Std::Fill
Which Is Faster: X<<1 or X<<10
Shared_Ptr<> Is to Weak_Ptr<> as Unique_Ptr<> Is To... What
Can the 'Type' of a Lambda Expression Be Expressed
Are There Any Downsides to Using Upx to Compress a Windows Executable
Simpler Way to Create a C++ Memorystream from (Char*, Size_T), Without Copying the Data
C++ Memory Barriers for Atomics
Erase/Remove Contents from the Map (Or Any Other Stl Container) While Iterating It
Is Wchar_T Needed for Unicode Support
Why and How to Use Namespaces in C++