Basically I'm trying to adapt the quicksort algo for array based lists
for linked list as shown on a text book. This is only for learning the principles than practically effective sorting.
I have struggled to get this code to work, but stil seems to break on a few test cases. Cant figure out why? Its not elegant at all; perhaps someone can point out how to improve and get it to work please !!

heres my code:

``````//Sorting using quicksort sorting algorithm
void linkedListType::quicksort(nodeType* &start, nodeType* &end)
{
//Pointers to help traverse the list
nodeType *current;
nodeType *trailCurrent;
nodeType *mid;
nodeType *smallIndex;
nodeType *trailSmall;
nodeType *index;
int temp;
int pivot;

if(start == NULL || start == end)//Empty or one element list
return;
//Locate the middle element - i.e pivot
else {
mid = start;
trailCurrent = start;
current = start->link;
if(current != end->link)
{
trailCurrent = current;
current = current->link;
}
while(current != end->link)
{
trailCurrent = current;
current = current->link;
mid = mid->link;
if(current != end->link)
{ trailCurrent = current;
current = current->link;
}
}

}
//Swap pivot element with first element
temp = start->info;
start->info = mid->info;
mid->info = temp;
pivot = first->info;
//partition list with left sublist < pivot
//and right sublist > pivot
smallIndex = start;
trailSmall = start;
index = start->link;
do
{
if(index->info < pivot)
{
trailSmall = smallIndex;
smallIndex = smallIndex->link;
temp = smallIndex->info;
smallIndex->info = index->info;
index->info = temp;
index = index->link;
}
else
index = index->link;
}while(index != end->link);

temp = smallIndex->info;
smallIndex->info = start->info;
start->info = temp;
quicksort(start, trailSmall);
quicksort(smallIndex->link, trailCurrent);
return;

}

int main(){

linkedListType myList;
cout<<"Enter any number of integers:";
int num;
cin>>num;
while(cin && !(num == 99))
{
myList.insertLast(num);
cin>>num;
}
cout<<"This list has "<<myList.length()<<" elements"<<endl;
cout<<"first node is "<<myList.front()<<endl;
cout<<"last node is "<<myList.back()<<endl;
cout<<"This list contains the elements:"<<endl<<"["<<myList<<"]"<<endl;
myList.quicksort(myList.first, myList.last);
cout<<endl;
cout<<"After sorting with quicksort, now myList is :"<<endl;
cout<<"["<<myList<<"]"<<endl;
system("pause");
return 0;
}``````

And the linkedListType header file:

``````#ifndef H_LinkedListType
#define H_LinkedListType

#include <iostream>
using namespace std;

struct nodeType{
int info;
nodeType* link;
};

class linkedListType{
friend ostream& operator<<(ostream&, const linkedListType&);
//Overload the stream insertion operator.

public:
const linkedListType& operator=(const linkedListType&);
//Overload the assignment operator
void initializeList();
//Function to initialise list to an empty state.
//Postcondition: first=NULL; last=NULL; count=0.
bool isEmptyList();
//Function to determine whether the list is empty.
//Postcondition: Returns true is the list is empty
//               otherwise returns false.
int length();
//Function to return the number of nodes in the list
//Postcondition: The value of count is returned.
void destroyList();
//Function to delete all the nodes from the list.
//Postcondition: first=NULL; last=NULL; count=0.
int front();
//Function to return the first element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, the program terminates;
//otherwise, the first element of  the list is returned
int back();
//Function to return the last element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, then the program
//               terminates; otherwise, the last element of
//               the list is returned.
bool search(const int& searchItem);
//Function to determine whether the searchItem is in the list
//Postcondition: Returns true if searchItem is found in the list;
//               otherwise returns false.
void insertFirst(const int& newItem);
//Function to insert newItem in the list.
//Postcondition: first points to the new list, newItem
//               is inserted at the beginning of the list,
//               last points to the last node and count
//               is incremented by 1.
void insertLast(const int& newItem);
//Function to insert newItem at the end of the list.
//Postcondition: first ponts to the new list, newItem
//               is inserted at the end of the list,
//               last points to the last node in the list,
//               and count is incremented by 1.
void deleteNode(const int& deleteItem);
//Function to delete deleteItem from the list
//Postcondition: If found, the node containing deleteItem
//               is deleted from the list, first points to
//               the first node, last points to the last node
//               of the updated list, and count is decremeneted
//               by 1.
linkedListType();
//Default constructor.
//Initilises the list to an empty state.
//Postcontion: first=NULL; last=NULL; count=0.
linkedListType(const linkedListType& otherList);
//copy constructor
~linkedListType();
//Destructor
//Deletes all the nodes from the list.
//Postcondition: The list object is destroyed.
void quicksort(nodeType* &st, nodeType* &en);
//Sort list using quicksort sorting algorithm

// protected:
int count;   //Variable to store the number of elements
//in the list
nodeType* first;   //Pointer to the first node of the list
nodeType* last;   //Pointer to the last node of the list.

private:
void copyList(const linkedListType& otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and
//assigned to this list.
};

#endif``````

## Recommended Answers

Either post the problem you're facing
or
post full code so someone can reproduce it.

Just looking at this much of code, finding and fixing a prob is difficult at best.

## All 2 Replies

Either post the problem you're facing
or
post full code so someone can reproduce it.

Just looking at this much of code, finding and fixing a prob is difficult at best.

Either post the problem you're facing
or
post full code so someone can reproduce it.

Just looking at this much of code, finding and fixing a prob is difficult at best.

Ok sorry maybe I wasn't clear; my problem is that this appears to be erratic i.e sometimes sorts the input ok sometimes not; so there appear to be some logic errors in it:

Here is all the code if someone needs to run it and test:

``````#include <iostream>
#include "linkedListType.h"
using namespace std;

bool linkedListType::isEmptyList()
{
return(first == NULL);
}

linkedListType::linkedListType() // default constructor
{
first = NULL;
last = NULL;
count = 0;
}

void linkedListType::destroyList()
{
nodeType* temp;   //pointer to deallocate the memory
//occupied by the node
while(first != NULL)    //while there are nodes in the list
{
temp = first;        //set temp to the current node
first = first->link; //advance first to the next node
delete temp;         //deallocate memory occupied by temp
}

last = NULL;	//initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}

void linkedListType::initializeList()
{
destroyList(); //if the list has any nodes, delete them
}

int linkedListType::length()
{
return count;
}  // end length

int linkedListType::front()
{
assert(first != NULL);
return first->info; //return the info of the first node
}//end front

int linkedListType::back()
{
assert(last != NULL);
return last->info; //return the info of the first node
}//end back

bool linkedListType::search(const int& searchItem)
{
nodeType* current; //pointer to traverse the list
bool found;

current = first; //set current to point to the
//first node in the list
found = false;   //set found to false

while(current != NULL && !found)		//search the list
if(current->info == searchItem)     //the item is found
found = true;
else
current = current->link; //make current point
//to the next node

return found;
}//end search

void linkedListType::insertFirst(const int& newItem)
{
nodeType* newNode;  //pointer to create new node

newNode = new nodeType; //create the new node

assert(newNode != NULL);	//If unable to allocate memory,
//terminate the program

newNode->info = newItem; 	   //store the new item in the node
newNode->link = first;        //insert newNode before first
first = newNode;              //make first point to the
//actual first node
count++; 			   //increment count

if(last == NULL)   //if the list was empty, newNode is also
//the last node in the list
last = newNode;
}

void linkedListType::insertLast(const int& newItem)
{
nodeType* newNode;  //pointer to create the new node

newNode = new nodeType; //create the new node

assert(newNode != NULL);	//If unable to allocate memory,
//terminate the program

newNode->info = newItem;      //store the new item in the node
newNode->link = NULL;         //set the link field of newNode
//to NULL

if(first == NULL)	//if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
count++;		//increment count
}
else			//the list is not empty, insert newNode after last
{
last->link = newNode; //insert newNode after last
last = newNode;   //make last point to the actual last node
count++;		//increment count
}
}//end insertLast

void linkedListType::deleteNode(const int& deleteItem)
{
nodeType *current; //pointer to traverse the list
nodeType *trailCurrent; //pointer just before current
bool found;

if(first == NULL)    //Case 1; list is empty.
cerr<<"Can not delete from an empty list.\n";
else
{
if(first->info == deleteItem) //Case 2
{
current = first;
first = first->link;
count--;
if(first == NULL)    //list has only one node
last = NULL;
delete current;
}
else  //search the list for the node with the given info
{
found = false;
trailCurrent = first;   //set trailCurrent to point to
//the first node
current = first->link;  //set current to point to the
//second node

while(current != NULL && !found)
{
if(current->info != deleteItem)
{
trailCurrent = current;
current = current->link;
}
else
found = true;
} // end while

if(found) //Case 3; if found, delete the node
{
trailCurrent->link = current->link;
count--;

if(last == current)      //node to be deleted was
//the last node
last = trailCurrent;  //update the value of last

delete current;  //delete the node from the list
}
else
cout<<"Item to be deleted is not in the list."<<endl;
} //end else
} //end else
} //end deleteNode

//Overloading the stream insertion operator
ostream& operator<<(ostream& osObject, const linkedListType& list)
{
nodeType *current; //pointer to traverse the list

current = list.first;   //set current so that it points to
//the first node
while(current != NULL) //while more data to print
{
osObject<<current->info<<" ";
current = current->link;
}

return osObject;
}

linkedListType::~linkedListType() // destructor
{
destroyList();
}//end destructor

void linkedListType::copyList
(const linkedListType& otherList)
{
nodeType *newNode; //pointer to create a node
nodeType *current; //pointer to traverse the list

if(first != NULL)	//if the list is nonempty, make it empty
destroyList();

if(otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first;  //current points to the
//list to be copied
count = otherList.count;

//copy the first node
first = new nodeType;  //create the node

assert(first != NULL);

first->info = current->info; //copy the info
first->link = NULL;  	     //set the link field of
//the node to NULL
last = first;    		     //make last point to the
//first node
current = current->link;     //make current point to
//the next node

//copy the remaining list
while(current != NULL)
{
newNode = new nodeType;  //create a node

assert(newNode!= NULL);

newNode->info = current->info;	//copy the info
newNode->link = NULL;   	    //set the link of
//newNode to NULL
last->link = newNode; 		//attach newNode after last
last = newNode;   			//make last point to
//the actual last node
current = current->link;	//make current point to
//the next node
}//end while
}//end else
}//end copyList

//copy constructor
linkedListType::linkedListType
(const linkedListType& otherList)
{
first = NULL;

copyList(otherList);

}//end copy constructor

//overload the assignment operator
const linkedListType& linkedListType::operator=
(const linkedListType& otherList)
{
if(this != &otherList) //avoid self-copy
copyList(otherList);

return *this;
}

//Sorting using quicksort sorting algorithm
void linkedListType::quicksort(nodeType* &start, nodeType* &end)
{
//Pointers to help traverse the list
nodeType *current;
nodeType *trailCurrent;
nodeType *mid;
nodeType *smallIndex;
nodeType *trailSmall;
nodeType *index;
int temp;
int pivot;

if(start == NULL || start == end)//Empty or one element list
return;
//Locate the middle element - i.e pivot
else {
mid = start;
trailCurrent = start;
current = start->link;
if(current != end->link)
{
trailCurrent = current;
current = current->link;
}
while(current != end->link)
{
trailCurrent = current;
current = current->link;
mid = mid->link;
if(current != end->link)
{ trailCurrent = current;
current = current->link;
}
}

}
//Swap pivot element with first element
temp = start->info;
start->info = mid->info;
mid->info = temp;
pivot = first->info;
//partition list with left sublist < pivot
//and right sublist > pivot
smallIndex = start;
trailSmall = start;
index = start->link;
do
{
if(index->info < pivot)
{
trailSmall = smallIndex;
smallIndex = smallIndex->link;
temp = smallIndex->info;
smallIndex->info = index->info;
index->info = temp;
index = index->link;
}
else
index = index->link;
}while(index != end->link);

temp = smallIndex->info;
smallIndex->info = start->info;
start->info = temp;
quicksort(start, trailSmall);
quicksort(smallIndex->link, trailCurrent);
return;

}

int main(){

linkedListType myList;
cout<<"Enter any number of integers:";
int num;
cin>>num;
while(cin && !(num == 99))
{
myList.insertLast(num);
cin>>num;
}
cout<<"This list has "<<myList.length()<<" elements"<<endl;
cout<<"first node is "<<myList.front()<<endl;
cout<<"last node is "<<myList.back()<<endl;
cout<<"This list contains the elements:"<<endl<<"["<<myList<<"]"<<endl;
myList.quicksort(myList.first, myList.last);
cout<<endl;
cout<<"After sorting with quicksort, now myList is :"<<endl;
cout<<"["<<myList<<"]"<<endl;
system("pause");
return 0;
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.