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