Question

How would I make a bubble sort and an optimized bubble sort with the code given? I also need to implement a timer into each sort and display runtime with the sorts.

NODE.H
_______________________________________________________________________________________________________

/* node.h */
/*

two classes 1: node.h 2. singlylinkedlist.h

nod1 (value + pointer) ---> node2 ---> node3 ---> |||| <--- node.h
^
| singlylinkedlist
----------------*node head;

*/

#ifndef NODE_H
#define NODE_H

#include <iostream>
using namespace std;

class Node {
   friend class singlyLinkedList;
public:
   Node();
   Node (int value);
   ~Node();
   int displayValue();
private:
   int value;
   Node* next;
};

#endif

SINGLYLINKEDLIST.H
_______________________________________________________________________________________________________

/* singlylinkedlist.h */

#ifndef SINGLY_LINKED_LIST_H
#define SINGLY_LINKED_LIST_H

#include <iostream>
using namespace std;

#include "node.h"

class singlyLinkedList
{
public:
   singlyLinkedList();
   ~singlyLinkedList();
   void addFront(Node* newNode);
   void displaySinglyLinkedList();
   void bubbleSort();
   void optimizedBubbleSort();
private:
   Node *head;
};

#endif

NODE.CPP
_______________________________________________________________________________________________________

/* node.cpp */

#include <iostream>
using namespace std;

#include "node.h"

Node::Node()
{
   value = 0;
   next = NULL;
}

Node::Node(int v)
{
   value = v;
   next = NULL;
}

Node::~Node()
{
}

int Node::displayValue()
{
   return value;
}

SINGLYLINKEDLIST.CPP
_______________________________________________________________________________________________________

/* singlylinkedlist */

#include <iostream>
using namespace std;

#include "singlylinkedlist.h"

singlyLinkedList::singlyLinkedList()
{
   head = NULL;
}

singlyLinkedList::~singlyLinkedList()
{
}

void singlyLinkedList::addFront(Node *newNode)
{
   if (head == NULL)
       head = newNode;
   else
   {
       // Add code here!
       /* node1-->||| (before) what is after node2 --> node1 -->||| */

       newNode->next = head;
       head = newNode;
   };
}

void singlyLinkedList::displaySinglyLinkedList()
{
   Node *tempHead;

   tempHead = head;

   while (tempHead != NULL)
   {
       cout << tempHead->value << " ";
       tempHead = tempHead->next;
   }
   cout << endl;
}

void singlyLinkedList:: bubbleSort()
{
   // Your Code Starts Here!
   // Please display the runtime for this task before exit
   // start clock
   // ....
   // stop the clock
   // display the (stop-clock - start-clock
}

void singlyLinkedList:: optimizedBubbleSort()
{
   // Your Code Starts Here!
   // Please display the runtime for this task before exit
   // start clock
   // ....
   // stop the clock
   // display the (stop-clock - start-clock
}

MAIN.CPP
_______________________________________________________________________________________________________

// In Project 1, your are required to implement the code for bubble sort and optimized bubble sort
// using the data structure of sinngly linked list (nothing else).

/* Bubble Sort:
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
{
if (A[i] > A[j])
{
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
*/

/* Optimized Bubble Sort:
flag = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n-1; j++)
{
if (A[j] > A[j+1])
{
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
   flag = 1; // if swapping occurs
}
}
   if (flag == 0)
break; // the input list already sorted, no need for the inner loop
}
*/

// The main program will create 10 nodes for storing a sequence of 10 integers
// bubble Sort() will be invoked to sort these 10 integers
// then optimizedBubbleSort will be invoked to sort the sorted sequence (degenerate case) again
// You will find out optimizedBubbleSort will take O(1) running time to do the sorting
// unlike bubbleSort taking O(n^2) run time to sort a sorted sequence.

// Lastly, in order to see the differences of bubbleSort and optimizedBubbleSort,
// also implement timer into both code, after the sorting, print out the runtime
// of sorting the sequence. For bubbleSort, no matter sorted or unsorted, it always
// take O(n^2) runtime. But for optimizedBubbleSort, for unsorted sequence, like
// bubbleSort, it takes O(n^2) runtime. However, for a sorted sequence,
// optimizedBubbleSort will take O(1) only. For a sorted sequence as a
// degenerate case, optimizedBubbleSort is more efficienct than bubbleSort
// for sorting a sequence of integers.

// You MUST use this provided code for Project 1

#include <iostream>
using namespace std;

#include "node.h"
#include "singlylinkedlist.h"

int main()
{
   /* create 10 nodes */
   Node *n1 = new Node(23); // objects creation (class instantiation)
   Node *n2 = new Node(-20);
   Node *n3 = new Node(7);
   Node *n4 = new Node(174);
   Node *n5 = new Node(56);
   Node *n6 = new Node(-98);
   Node *n7 = new Node(101);
   Node *n8 = new Node(46);
   Node *n9 = new Node(31);
   Node *n10 = new Node(5);

   /* create singly linked list */
   singlyLinkedList *sLL;
   sLL = new singlyLinkedList();

   /* insert 10 nodes into the singly linked list in First in, Last out manner */
   sLL->addFront(n1);
   sLL->addFront(n2);
   sLL->addFront(n3);
   sLL->addFront(n4);
   sLL->addFront(n5);
   sLL->addFront(n6);
   sLL->addFront(n7);
   sLL->addFront(n8);
   sLL->addFront(n9);
   sLL->addFront(n10);

   /* display the contents of the 10 nodes in the singly linked list */
   sLL->displaySinglyLinkedList();

   /* The following code will act it is supposed to do
   when you are successfully implment bubbleSort and
   optimizedBubbleSort. */
   sLL->bubbleSort(); // bubble sort the unsorted sequence
   sLL->displaySinglyLinkedList(); // a sorted sequence displayed

   sLL->optimizedBubbleSort(); // optimized bubble sort the already sorted sequence (a degenerate case)
   // the runtime should show O(1), it means time should be musch less than runtime
   // of bubbleSort()
   sLL->displaySinglyLinkedList(); // a sorted sequence displayed

   system("PAUSE");
   return 0;
}

Answer 1

The changes has been made in 'singlylinkedlist.cpp' only.
So, C++ code of 'singlylinkedlist' is :

/* singlylinkedlist */

#include <iostream>
#include <time.h>
using namespace std;

#include "singlylinkedlist.h"

singlyLinkedList::singlyLinkedList()
{
   head = NULL;
}

singlyLinkedList::~singlyLinkedList()
{
}

void singlyLinkedList::addFront(Node *newNode)
{
   if (head == NULL)
       head = newNode;
   else
   {
       // Add code here!
       /* node1-->||| (before) what is after node2 --> node1 -->||| */

       newNode->next = head;
       head = newNode;
   };
}

void singlyLinkedList::displaySinglyLinkedList()
{
   Node *tempHead;

   tempHead = head;

   while (tempHead != NULL)
   {
       cout << tempHead->value << " ";
       tempHead = tempHead->next;
   }
   cout << endl;
}

void singlyLinkedList:: bubbleSort()
{
  time_t start, end;
  
  int n=0;
  Node *ptr = head;
  while(ptr)
  {
    n++;
    ptr = ptr->next;
  }

  Node *ptr2;
  ptr = head;
  ptr2 = ptr;
  int temp;
  time(&start);
  for (int i = 0; i < n; i++)
  {
    ptr = ptr2;
    for (int j = i; j < n; j++)
    {
      if (ptr2->value > ptr->value)
      {
        temp = ptr2->value;
        ptr2->value = ptr->value;
        ptr->value = temp;
      }
      ptr = ptr->next;
    }
    ptr2 = ptr2->next;
  }
    time(&end);
    cout << "\nBubble Sort time: " << difftime(end, start) << "sec\n";
}

void singlyLinkedList:: optimizedBubbleSort()
{
    time_t start, end;

  int n=0;
  Node *ptr = head;
  while(ptr)
  {
    n++;
    ptr = ptr->next;
  }

  Node *ptr2;
  ptr = head;
  ptr2 = ptr;
  time(&start);
   int flag = 0, temp;
    for (int i = 0; i < n; i++)
    {
      flag = 0;
      ptr = ptr2;
      for (int j = 0; j < n-1; j++)
      {
        if (ptr->value > ptr->next->value)
        {
          temp = ptr->value;
          ptr->value = ptr->next->value;
          ptr->next->value = temp;
           flag = 1; // if swapping occurs
        }
        ptr = ptr->next;
      }
     if (flag == 0)
        break; // the input list already sorted, no need for the inner loop
      ptr2 = ptr2->next;
    }
   time(&end);
   cout << "\nOptimezed Bubble Sort time: " << difftime(end, start) << "sec\n";
}

Output sample:

Note that time is 0 sec. This is because the size of data is very small so it takes almost no time to sort.

Hope it helps.