// bareBonesListInsetSorted.cpp // // 2017-02-11 //
#include <iostream>
#include <string>
using std::ostream;
using std::string;
template < typename T >
struct Node
{
T data;
Node* next;
// ctors...
Node( const T& data= T(), Node* next = 0 ) : data(data), next(next) {}
// def'n for overloaded << for Node< T > objects ,,,
friend ostream& operator << ( ostream& os, const Node* nd )
{
return os << nd->data;
}
} ;
template< typename T >
struct List
{
Node< T >* head;
// default ctor...
List() : head(0) {}
// dtor...
~List() { clear(); }
void clear()
{
Node< T >* del;
while( head )
{
del = head;
head = head->next;
delete del;
}
// Note that head is set to 0 when done //
}
/*
void push_front( const T& data )
{
// Note that this also sets the next to 'head' //
Node< T >* newNode = new Node< T >( data, head );
head = newNode; // update the head pointer //
}
*/
// insert sorted by <= def'n of objects ...
void insert( const T& data )
{
Node< T >* nNode = new Node< T > (data); // recall next set to 0 //
// case 1 : NOT inserted as the head node
if( head != 0 && head->data <= data )
{
// find Node to insert after
Node< T >* prev = head;
Node< T >* cur = head->next;
while( cur != 0 && cur->data <= data )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
//if( cur ) // NOT at end
nNode->next = cur; // link next to 'next' //
}
else // case 2 : insert at head ...
{
nNode->next = head;
head = nNode; // update head //
}
}
// def'n of overloaded << for List objects ...
friend ostream& operator << ( ostream& os, const List< T >& lst )
{
for( Node< T >* cur = lst.head; cur != 0; cur = cur->next )
{
os << cur << '\n'; //uses overloaded << for Node above //
}
return os;
}
} ;
struct Student
{
string name;
int id;
// ctors...
Student( string name = "", int id = 0 ) : name(name), id(id) {}
// for insert sorted method ...
bool operator <= ( const Student& st ) const
{
return id <= st.id;
}
friend ostream& operator << ( ostream& os, const Student& st )
{
return os << st.name << ' ' << st.id;
}
} ;
int main()
{
using std::cout;
using std::cin;
List< Student > studs;
studs.insert( Student("Sam", 3) );
studs.insert( Student("James", 1) );
studs.insert( Student("Annie", 4) );
studs.insert( Student("Jill", 2) );
cout << "studs now are: \n" << studs;
cout << "\nPress 'Enter' to continue/exit ... ";
cin.get();
}
// bareBonesListInsetSorted_classVersion.cpp // // 2017-02-11 //
#include <iostream>
#include <string>
using std::ostream;
using std::string;
template < typename T > class List; // forward declaration //
template < typename T >
class Node
{
public:
// ctors...
Node( const T& data= T(), Node* next = 0 ) : data(data), next(next) {}
private:
T data;
Node* next;
// def'n for overloaded << for Node< T > objects ,,,
friend ostream& operator << ( ostream& os, const Node* nd )
{
return os << nd->data;
}
friend class List < T >;
} ;
template< typename T >
class List
{
public:
// default ctor...
List() : head(0) {}
// dtor...
~List() { clear(); }
void clear()
{
while( head )
{
Node< T >* del = head;
head = head->next;
delete del;
}
// Note that head is set to 0 when done //
}
void push_front( const T& data )
{
// Note that this alos sets the next to 'head' //
Node< T >* newNode = new Node< T >( data, head );
head = newNode; // update the head pointer //
}
// insert sorted by <= def'n of objects ...
void insert( const T& data )
{
Node< T >* nNode = new Node< T > (data); // recall next set to 0 //
// case 1 : NOT inserted as the head node
if( head != 0 && head->data <= nNode->data )
{
// find Node to insert after
Node< T >* prev = head;
Node< T >* cur = head->next;
while( cur != 0 && cur->data <= nNode->data )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
//if( cur ) // NOT at end
nNode->next = cur; // link next to 'next' //
}
else // case 2 : insert at head ...
{
nNode->next = head;
head = nNode; // update head //
}
}
void print( ostream& os ) const
{
Node< T >* cur = head;
for( ; cur != 0 ; cur = cur->next )
os << cur << '\n'; //uses overloaded << for Node above //
}
private:
Node< T >* head;
} ;
// def'n of overloaded << for List objects ...
template < typename T >
ostream& operator << ( ostream& os, const List< T >& lst )
{
lst.print( os );
return os;
}
class Student
{
public:
// ctors...
Student( string name="", int id=0 ) : name(name), id(id) {}
// for insert sorted method ...
bool operator <= ( const Student& st ) const
{
return id <= st.id;
}
private:
string name;
int id;
friend ostream& operator << ( ostream& os, const Student& st )
{
return os << st.name << ' ' << st.id;
}
} ;
int main()
{
using std::cout;
using std::cin;
List< Student > studs;
studs.insert( Student("Sam", 3) );
studs.insert( Student("James", 1) );
studs.insert( Student("Annie", 4) );
studs.insert( Student("Jill", 2) );
cout << "studs now are: \n" << studs;
cout << "\nPress 'Enter' to continue/exit ... ";
cin.get();
}
// bareBonesListInsetSorted_classVersion_nestedNode.cpp // // 2017-02-11 //
#include <iostream>
#include <string>
using std::ostream;
using std::string;
template< typename T >
class List
{
public:
// default ctor...
List() : head(0) {}
// dtor...
~List() { clear(); }
void clear()
{
while( head )
{
Node* del = head;
head = head->next;
delete del;
}
// Note that head is set to 0 when done //
}
void push_front( const T& data )
{
// Note that this alos sets the next to 'head' //
Node* newNode = new Node( data, head );
head = newNode; // update the head pointer //
}
// insert sorted by <= def'n of objects ...
void insert( const T& data )
{
Node* nNode = new Node( data ); // recall next set to 0 //
// case 1 : NOT inserted as the head node
if( head != 0 && head->data <= nNode->data )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur != 0 && cur->data <= nNode->data )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
//if( cur ) // NOT at end
nNode->next = cur; // link next to 'next' //
}
else // case 2 : insert at head ...
{
nNode->next = head;
head = nNode; // update head //
}
}
void print( ostream& os ) const
{
Node* cur = head;
for( ; cur != 0 ; cur = cur->next )
os << cur->data << '\n';
}
private:
struct Node
{
Node( const T& data= T(), Node* next = 0 ) : data(data), next(next) {}
T data;
Node* next;
} ;
Node* head;
} ;
// def'n of overloaded << for List objects ...
template < typename T >
ostream& operator << ( ostream& os, const List< T >& lst )
{
lst.print( os );
return os;
}
class Student
{
public:
// ctors...
Student( string name="", int id=0 ) : name(name), id(id) {}
// for insert sorted method ...
bool operator <= ( const Student& st ) const
{
return id <= st.id;
}
private:
string name;
int id;
friend ostream& operator << ( ostream& os, const Student& st )
{
return os << st.name << ' ' << st.id;
}
} ;
int main()
{
using std::cout;
using std::cin;
List< Student > studs;
studs.insert( Student("Sam", 3) );
studs.insert( Student("James", 1) );
studs.insert( Student("Annie", 4) );
studs.insert( Student("Jill", 2) );
cout << "studs now are: \n" << studs;
cout << "\nPress 'Enter' to continue/exit ... ";
cin.get();
}
// insertSortedEraseSLL.h // // 2017-02-11 //
// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used here. //
#ifndef _insertSortedEraseSLL_H_
#define _insertSortedEraseSLL_H_
template< typename T >
struct List
{
struct Node
{
T val;
Node* next;
Node( const T& val = T(), Node* next = 0 ) : val(val), next(next) {}
} ;
Node* head;
Node* tail;
size_t len;
List() : head(0), tail(0), len(0) {}
~List() { clear(); }
void clear()
{
while( head )
{
Node* del = head;
head = head->next;
delete del;
}
tail = 0;
len = 0;
}
void push_front( const T& val )
{
head = new Node( val, head );
++len;
}
void push_back( const T& val )
{
Node* nNode = new Node( val );
if( len )
{
tail->next = nNode; // B->N
tail = nNode;
}
else tail = head = nNode;
++len;
}
// insert sorted by <= def'n of objects ...
void insert_sorted( const T& val )
{
Node* nNode = new Node( val ); // recall next set to 0 //
// case 1 : NOT inserted as the head node
if( head != 0 && head->val <= val )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur != 0 && cur->val <= val )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
//if( cur ) // NOT at end
nNode->next = cur; // link next to 'next' //
if( !cur ) tail = nNode;
}
else // case 2 : insert at head ...
{
nNode->next = head;
head = nNode; // update head //
if( !len ) tail = head;
}
++ len;
}
// used by method insert_sort() that follows ...
void insert_sorted( Node* nNode )
{
// case 1 : NOT inserted as the head node
if( head != 0 && head->val <= nNode->val )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur != 0 && cur->val <= nNode->val )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
// if( cur ) // NOT at end
nNode->next = cur; // link next to 'next' //
if( !cur ) tail = nNode;
}
else // case 2 : insert at head ...
{
nNode->next = head;
head = nNode; // update head //
if( !len ) tail = head;
}
++ len;
}
// calls above method insert_sorted( Node* nNode ) //
void insert_sort()
{
if( len > 1 ) // then head and cur != 0 //
{
Node* cur = head; // get copy //
Node* next = cur->next; // get copy //
head = tail = 0;
len = 0;
for( ; ; )
{
insert_sorted( cur );
cur = next; // UPDATE from COPY //
if( !cur ) break;
next = cur->next;
}
}
}
bool erase( Node* ptr )
{
Node* prev = 0;
Node* cur = head;
for( ; cur && cur != ptr; cur = cur->next )
{
prev = cur;
}
// check end conditions //
if( cur ) // found //
{
if( prev )
prev->next = cur->next;
else
head = head->next;
if( cur == tail ) tail = prev;
delete cur;
-- len;
return true;
}
// NOT found //
return false;
}
size_t size() const { return len; }
} ;
#endif
// insertSortedEraseSLL.cpp // // 2017-02-13 //
#include <iostream>
#include <string>
// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used here. //
#include "insertSortedEraseSLL.h"
template< typename T >
void print( const List< T >& lst, std::ostream& os = std::cout )
{
typename List< T >::Node* cur;
cur = lst.head;
while( cur )
{
os << cur->val << ' ';
cur = cur->next;
}
os << "size() = " << lst.size();
}
typedef List< std::string >::Node* MyNode;
MyNode find( List< std::string >& lst, const std::string& val )
{
MyNode cur = lst.head;
while( cur )
{
if( cur->val == val ) return cur;
cur = cur->next;
}
return 0; // NOT found
}
int main()
{
using namespace std;
List< string > my_lst;
cout << "Now testing push_front: ";
my_lst.push_front( "Billy" );
my_lst.push_front( "Sam" );
my_lst.push_front( "Joe" );
my_lst.push_front( "Anne" );
my_lst.push_front( "Jill" );
print( my_lst );
my_lst.insert_sort();
cout << "\nAfter calling my_lst.insert_sort(): ";
print( my_lst );
my_lst.clear();
cout << "\n\nNow testing push_back: ";
my_lst.push_back( "Billy" );
my_lst.push_back( "Sam" );
my_lst.push_back( "Joe" );
my_lst.push_back( "Anne" );
my_lst.push_back( "Jill" );
print( my_lst );
my_lst.insert_sort();
cout << "\nAfter calling my_lst.insert_sort(): ";
print( my_lst );
my_lst.clear();
cout << "\n\nNow testing insert_sorted: ";
my_lst.insert_sorted( "Sam" );
my_lst.insert_sorted( "Joe" );
my_lst.insert_sorted( "Anne" );
my_lst.push_back( "Billy" );
my_lst.push_front( "Jill" );
my_lst.insert_sort();
print( my_lst );
cout << "\n\nFind Billy ... ";
MyNode cur = find( my_lst, "Billy" );
if( cur )
{
cout << "Found ... erasing Billy ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Billy ...\n";
print( my_lst );
cout << "\n\nFind Anne ... ";
cur = find( my_lst, "Anne" );
if( cur )
{
cout << "Found ... erasing Anne ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Anne ...\n";
print( my_lst );
cout << "\n\nFind Sam ... ";
cur = find( my_lst, "Sam" );
if( cur )
{
cout << "Found ... erasing Sam ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Sam ...\n";
print( my_lst );
cout << "\n\nFind Jill ... ";
cur = find( my_lst, "Jill" );
if( cur )
{
cout << "Found ... erasing Jill ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Jill ...\n";
print( my_lst );
cout << "\n\nFind Joe ... ";
cur = find( my_lst, "Joe" );
if( cur )
{
cout << "Found ... erasing Joe ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Joe ...\n";
print( my_lst );
cout << "\nPress 'Enter' to continue/exit ..." << flush;
cin.get();
}
// insertSortedEraseDLL.h // // 2017-02-11 //
// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used here. //
#ifndef _insertSortedEraseDLL_H_
#define _insertSortedEraseDLL_H_
template< typename T >
struct List
{
struct Node
{
T val;
Node* prev;
Node* next;
Node( const T& val = T() ) : val(val), prev(0), next(0) {}
} ;
Node* head;
Node* tail;
size_t len;
List() : head(0), tail(0), len(0) {}
~List() { clear(); }
void clear()
{
while( head )
{
Node* del = head;
head = head->next;
delete del;
}
tail = 0;
len = 0;
}
void push_front( const T& val )
{
Node* nNode = new Node( val );
if( len )
{
nNode->next = head; // N->A
head->prev = nNode; // N<-A
head = nNode;
}
else tail = head = nNode;
++len;
}
void push_back( const T& val )
{
Node* nNode = new Node( val );
if( len )
{
tail->next = nNode; // B->N
nNode->prev = tail; // B<-N
tail = nNode;
}
else tail = head = nNode;
++len;
}
void insert_sorted( const T& val )
{
Node* nNode = new Node( val );
// case 1 ... NOT inserted as the head node
if( head && head->val <= val )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur && cur->val <= val )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
nNode->prev = prev;
if( cur ) // NOT at tail
{
cur->prev = nNode;
nNode->next = cur;
}
else // at tail
{
tail = nNode;
}
}
else // insert at head ...
{
if( len )
{
nNode->next = head;
head->prev = nNode;
head = nNode;
}
else tail = head = nNode;
}
++ len;
}
void insert_sorted( Node* nNode ) // nNode is a local copy //
{
nNode->next = nNode->prev = 0;
// case 1 ... NOT inserted as the head node
if( head && head->val <= nNode->val )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur && cur->val <= nNode->val )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
nNode->prev = prev;
if( cur ) // NOT at tail
{
cur->prev = nNode;
nNode->next = cur;
}
else // at tail
{
tail = nNode;
}
}
else // insert at head ...
{
if( len )
{
nNode->next = head;
head->prev = nNode;
head = nNode;
}
else tail = head = nNode;
}
++ len;
}
// calls above method insert_sorted( Node* nNode ) //
void insert_sort()
{
if( len > 1 ) // then head and cur != 0 //
{
Node* cur = head; // get copy //
Node* next = cur->next; // get copy //
head = tail = 0;
len = 0;
for( ; ; )
{
insert_sorted( cur );
cur = next; // UPDATE from COPY //
if( !cur ) break;
next = cur->next;
}
}
}
// *** ASSUMPTION here *IS* that p passed in *IS* a *VALID* Node *** //
void erase( Node* p )
{
if( p->prev && p->next )
{
p->prev->next = p->next;
p->next->prev = p->prev;
}
else if( p->prev )
{
p->prev->next = 0;
tail = p->prev;
}
else if( p->next )
{
p->next->prev = 0;
head = p->next;
}
delete p;
--len;
if( !len ) head = tail = 0;
}
size_t size() const { return len; }
} ;
#endif
// insertSortedEraseDLL.cpp // // 2017-02-11 //
#include <iostream>
#include <string>
// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used here. //
#include "insertSortedEraseDLL.h"
template< typename T >
void print( const List< T >& lst, std::ostream& os = std::cout )
{
typename List< T >::Node* cur;
cur = lst.head;
while( cur )
{
os << cur->val << ' ';
cur = cur->next;
}
os << "size() = " << lst.size();
}
template< typename T >
void print_reversed( const List< T >& lst, std::ostream& os = std::cout )
{
typename List< T >::Node* cur;
cur = lst.tail;
while( cur )
{
os << cur->val << ' ';
cur = cur->prev;
}
os << "size() = " << lst.size();
}
typedef List< std::string >::Node* MyNode;
MyNode find( List< std::string >& lst, const std::string& val )
{
MyNode cur = lst.head;
while( cur )
{
if( cur->val == val ) return cur;
cur = cur->next;
}
return 0; // NOT found
}
int main()
{
using namespace std;
List< string > my_lst;
cout << "Now testing push_front: ";
my_lst.push_front( "Sam" );
my_lst.push_front( "Joe" );
my_lst.push_front( "Anne" );
print( my_lst );
cout << "\nPrinting reversed: ";
print_reversed( my_lst );
my_lst.clear();
cout << "\n\nNow testing push_back: ";
my_lst.push_back( "Sam" );
my_lst.push_back( "Joe" );
my_lst.push_back( "Anne" );
print( my_lst );
my_lst.insert_sort();
my_lst.push_back( "Ann" );
my_lst.push_front( "Zoe" );
my_lst.insert_sort();
cout << "\nAfter calling my_lst.insert_sort(): ";
print( my_lst );
cout << "\nPrinting reversed: ";
print_reversed( my_lst );
my_lst.clear();
cout << "\n\nNow testing insert_sorted: ";
my_lst.insert_sorted( "Anne" );
my_lst.insert_sorted( "Sam" );
my_lst.insert_sorted( "Zoe" );
my_lst.insert_sorted( "Ann" );
my_lst.insert_sorted( "Joe" );
print( my_lst );
cout << "\nPrinting reversed: ";
print_reversed( my_lst );
cout << "\n\nFind Ann ... ";
MyNode cur = find( my_lst, "Ann" );
if( cur )
{
cout << "Found ... erasing Ann ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Ann ...\n";
cout << "Printing reversed: ";
print_reversed( my_lst );
cout << "\n\nFind Joe ... ";
cur = find( my_lst, "Joe" );
if( cur )
{
cout << "Found ... erasing Joe ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Joe ...\n";
cout << "Printing reversed: ";
print_reversed( my_lst );
cout << "\n\nFind Sam ... ";
cur = find( my_lst, "Sam" );
if( cur )
{
cout << "Found ... erasing Sam ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Sam ...\n";
cout << "Printing reversed: ";
print_reversed( my_lst );
cout << "\n\nFind Zoe ... ";
cur = find( my_lst, "Zoe" );
if( cur )
{
cout << "Found ... erasing Zoe ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Zoe ...\n";
cout << "Printing reversed: ";
print_reversed( my_lst );
cout << "\n\nFind Anne ... ";
cur = find( my_lst, "Anne" );
if( cur )
{
cout << "Found ... erasing Anne ...\n";
my_lst.erase( cur );
}
else cout << "NOT Found ... NOT erasing Anne ...\n";
cout << "Printing reversed: ";
print_reversed( my_lst );
cout << "\nPress 'Enter' to continue/exit ..." << flush;
cin.get();
}
// DLLinsertSorted.h // // revised: 2017-02-13 //
#ifndef DDL_INSERT_SORTED_H
#define DDL_INSERT_SORTED_H
#include <iostream>
template < typename T >
class List
{
// forward declaration ... so can use inside nested iterator class //
struct Node;
public:
// ctor...
List() : head(0), tail(0), len(0) {}
//dtor...
~List() { clear(); }
void clear()
{
Node* del;
while( head )
{
del = head;
head = head->next;
delete del;
}
tail = 0;
len = 0;
}
// copy ctor...
List ( const List& other )
{
head = tail = 0;
len = 0;
for( Node* cur = other.head; cur != 0; cur = cur->next )
push_back( cur->data );
}
// overloaded operator = (the assignment operator) //
List& operator = ( const List& other )
{
if( this != &other )
{
clear();
for( Node* cur = other.head; cur != 0; cur = cur->next )
push_back( cur->data );
}
return *this;
}
size_t size() const { return len; }
void push_front( const T& data )
{
Node* nNode = new Node( data );
if( len )
{
nNode->next = head; // N->H
head->prev = nNode; // N<-H
head = nNode;
}
else tail = head = nNode;
++len;
}
void push_back( const T& data )
{
Node* nNode = new Node( data );
if( len )
{
tail->next = nNode; // T->N
nNode->prev = tail; // T<-N
tail = nNode;
}
else tail = head = nNode;
++len;
}
// (forward iterators) now added here ...
// so can easily access elements ...
// and here ... to ease testing of BOTH insert sorted methods //
class iterator
{
Node* ptr;
public:
// ctor(s) ...
iterator( Node* ptr=0 ) : ptr(ptr) {}
iterator& operator ++ () { ptr = ptr->next; return *this; }
// Note that you canNOT update via this as a COPY returned //
iterator operator ++ ( int ) { iterator cpy(*this); ptr = ptr->next; return cpy; }
bool operator != ( const iterator& it ) const { return ptr != it.ptr; }
bool operator == ( const iterator& it ) const { return ptr == it.ptr; }
const T& operator * () const { return ptr->data; }
T& operator * () { return ptr->data; }
const T* operator -> () const { return &ptr->data; }
T* operator -> () { return &ptr->data; }
} ;
iterator begin() { return iterator(head); }
iterator end() { return iterator(0); }
typedef iterator const_iterator;
const_iterator begin() const { return iterator(head); }
const_iterator end() const { return iterator(0); }
void insert_sorted( const T& data )
{
Node* nNode = new Node( data );
// case 1 ... NOT inserted as the head node
if( head && head->data <= data )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur && cur->data <= data )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
nNode->prev = prev;
if( cur ) // NOT at end
{
cur->prev = nNode;
nNode->next = cur;
}
else // at end
{
tail = nNode;
}
}
else // insert at head ...
{
if( len )
{
nNode->next = head;
head->prev = nNode;
head = nNode;
}
else tail = head = nNode;
}
++ len;
}
void insert_sort() // uses power of DLL //
{
if( len > 1 )
{
Node* cur = head->next;
// start with set of just the first 2 elements (if exists) //
for( ; cur != 0; cur = cur->next )
{
// get copy of this new cmp element on each outer loop //
T cmp = cur->data;
// get Node of element just to the left of the above 'cmp'
// to start the comparisons //
Node* prev = cur->prev;
while( prev != 0 && cmp < prev->data )
{
// copy element 'up' to open up 'insertion-hole' //
prev->next->data = prev->data;
// 'decrement' in preparation for next inner loop //
prev = prev->prev;
}
// insert element at prev->next (since prev was 'decremented' above) //
if( prev ) prev->next->data = cmp;
else head->data = cmp;
}
}
}
void select_sort()
{
Node* cur = head;
while( cur )
{
Node* min = cur;
Node* next = cur->next;
while( next )
{
if( next->data < min->data ) min = next; // update if needed //
next = next->next;
}
if( cur != min ) // swap min and cur //
{
T tmp = cur->data;
cur->data = min->data;
min->data = tmp;
}
cur = cur->next;
}
}
void bubble_sort()
{
if( len > 1 )
{
Node* cur = head->next; // start 1 element in //
int size = len;
bool swap;
do
{
swap = false;
// added to speed up the bubble-up to *each decreasing new* top //
int i = 0;
//while( cur != 0 )
// added to speed up the bubble-up to *each decreasing new* top //
while( ++i < size )
{
if( cur->data < cur->prev->data ) // swap //
{
T tmp = cur->data;
cur->data = cur->prev->data;
cur->prev->data = tmp;
swap = true;
}
cur = cur->next;
}
--size;
// get ready ready for next outer (do) loop //
cur = head->next;
}
while( swap );
//while( size > 1 );
}
}
// merge sort the whole list in place (a 'divide and sort' recursive sort) //
void merge_sort()
{
Node* p = head;
merge_sort( p, len ); // p is updated in recursion using pass by ref.
set_head_tail( p );
}
// 3 utilities used for testing //
void print( std::ostream& os = std::cout ) const
{
Node* cur = head;
while( cur )
{
os << cur->data << ' ';
cur = cur->next;
}
}
void printReversed( std::ostream& os = std::cout ) const
{
Node* cur = tail;
while( cur )
{
os << cur->data << ' ';
cur = cur->prev;
}
}
bool isSorted() const
{
if( len > 1 )
{
Node* cur = head;
while( cur->next )
{
if( cur->next->data < cur->data ) return false;
cur = cur->next;
}
}
return true;
}
private:
struct Node
{
T data;
Node* prev;
Node* next;
// ctor...
Node( const T& data = T() ) : data(data), prev(0), next(0) {}
} ;
Node* head;
Node* tail;
size_t len;
// defined below class ...
void merge_sort( Node*& head, int len ); // returns updated head by ref.
// merge two sorted lists with heads 'a' and 'b' ... in sorted order
Node* merge( Node* a, Node* b )
{
if( a == 0 ) return b;
if( b == 0 ) return a;
Node* sorted; // now get appropriate new head for merged list
if( a->data <= b->data )
{
sorted = a;
a = a->next;
}
else
{
sorted = b;
b = b->next;
}
Node* new_merged_head = sorted;
// now merge lists ...
while( a != 0 && b != 0 )
{
if( a->data <= b->data )
{
sorted->next = a;
sorted = sorted->next;
a = a->next;
}
else
{
sorted->next = b;
sorted = sorted->next;
b = b->next;
}
}
// now ... append the ONE part that might have been left-over above ...
if( a != 0 )
sorted->next = a;
else if( b != 0 )
sorted->next = b;
return new_merged_head;
}
void update()
{
tail = head;
if( tail == 0 ) return;
Node* prev = 0;
while( tail->next != 0 )
{
prev = tail;
tail = tail->next;
tail->prev = prev;
}
head->prev = 0;
}
void set_head_tail( Node* p ) { head = p; update(); }
} ;
/////////////////// BEGIN MERGE SORT ///////////////////////
// divide list into two halves and then recursively sort each half ...
// then merge the two sorted halves using the above merge function
// Note: calling 'head' is updated by using 'pass by ref'
template < typename T >
void List< T >::merge_sort( Node*& p1, int len )
{
if( len < 2 ) return;
Node* pHead2;
Node* pEnd1;
int size2 = len/2;
int size1 = len - size2;
// split the list into two lists ... the first half begins with head
pEnd1 = p1; // first set pEnd1 to the head address ...
for( int i = 1; i < size1; ++i )
pEnd1 = pEnd1->next;
pHead2 = pEnd1->next; // second half begins with pHead2
pEnd1->next = 0; // breaking the chain here... so we can have two lists
// merge the lists after recusively merge_sorting them
merge_sort( p1, size1 );
merge_sort( pHead2, size2 );
p1 = merge( p1, pHead2 );
}//////////////////////////////// END MERGE SORT ///////////
#endif
// 6sorts_timed_all_auto_version.cpp // // revised: 2017-02-13 //
#include "DLLinsertSorted.h"
// include <iostream> // included above //
#include <string>
#include <cstdlib> // re, rand, srand
#include <ctime> // re, time clock
#include <climits> // re. RAND_MAX
#include <cctype> // re. tolower
#include <cmath> // re. log
#include <list> // to compare c++ library 'list sort' times with 'list sort' times //
const int MAX_PRINT = 11;
const int MAX_NxN = 30000;
// 3 utilities to ease coding here ...
template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
T val = T();
while( true )
{
std::cout << msg;
if( std::cin >> val && std::cin.get() == '\n' )
break;
else
{
std::cout << errMsg;
std::cin.clear(); // clear error flasgs
std::cin.sync(); // 'flush' cin stream ...
}
}
return val;
}
char takeInChr( const std::string& msg )
{
std::cout << msg;
std::string reply;
getline( std::cin, reply );
if( reply.size() )
return reply[0];
// else ...
return 0;
}
bool more( const std::string& text = "" )
{
char reply = takeInChr( "More " + text + "(y/n) ? " );
if( reply == 'n' || reply == 'N' )
return false;
// else ...
return true;
}
// get a List of random ints in range 0..MAX_RAND
void fillUpList( List< int >& lst, int num )
{
std::cout << "RAND_MIN = " << 0 << ", RAND_MAX = " << RAND_MAX << '\n';
for( int i = 0; i < num; ++ i )
lst.push_back( rand() );
}
template < typename T >
std::ostream& operator << ( std::ostream& os, const List< T >& lst )
{
typename List< T >::const_iterator it;
for( it = lst.begin(); it != lst.end(); ++ it ) os << *it << ' ';
return os;
}
int main()
{
using std::cout; using std::cin;
using std::string;
srand( time(0) ); // seed the random generator //
do
{
int num = 0;
for( ; ; )
{
num = takeIn< int >( "How many numbers to sort (10..2000000): " );
if( num >= 10 && num <= 2000000 ) break;
//else ///
cout << "\nTry again with a value in range 10..2000000 ...\n\n";
}
List< int > lstCpy;
fillUpList( lstCpy, num );
List< int > lst;
List< int >::const_iterator cit;
double dt, t1, k;
if( num <= MAX_NxN )
{
lst = lstCpy; // get from a copy //
t1 = clock();
lst.insert_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to insert_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
// t = k*n*n;
// k = t/n/n
k = dt/num/num;
lst = lstCpy;
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.push_back( *cit );
// Now size is doubled //
t1 = clock();
lst.insert_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to insert_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << 4*k*num*num << '\n';
lst.clear();
t1 = clock();
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.insert_sorted( *cit );
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to insert_sorted was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
k = dt/num/num;
lst.clear();
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.insert_sorted( *cit );
for( cit = lstCpy.begin(); cit != lstCpy.end(); cit ++ ) // test POST ++ //
lst.insert_sorted( *cit );
// Now size is doubled //
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to insert_sorted was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << 4*k*num*num << '\n';
lst = lstCpy; // restore from copy //
t1 = clock();
lst.select_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to select_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
k = dt/num/num;
lst = lstCpy; // restore from copy //
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.push_back( *cit );
// Now size is doubled //
t1 = clock();
lst.select_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to select_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << 4*k*num*num << '\n';
lst = lstCpy; // restore from copy //
t1 = clock();
lst.bubble_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to bubble_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
k = dt/num/num;
lst = lstCpy; // restore from copy //
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.push_back( *cit );
// Now size is doubled //
t1 = clock();
lst.bubble_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to bubble_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << 4*k*num*num << '\n';
}
lst = lstCpy; // restore from copy //
if( num <= MAX_PRINT ) cout << "\nUnsorted: " << lst << '\n';
t1 = clock();
lst.merge_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to merge_sort was " << dt<< " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
if( num <= MAX_PRINT )
{
cout << "\nSorted : " << lst << "\nReversed: ";
lst.printReversed();
cout << '\n';
}
// t = k*n*log(n)
// k = t/n*/log(n)
k = dt/num/log(num);
lst = lstCpy; // restore from copy //
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.push_back( *cit );
// Now size is doubled //
t1 = clock();
lst.merge_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to merge_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << k*2*num*log(2*num) << '\n';
// compare with C++ library list ...
std::list< int > cppLst;
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
cppLst.push_back( *cit );
t1 = clock();
cppLst.sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nC++ library list sort was " << dt << " seconds.";
k = dt/num/log(num);
cppLst.clear();
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
cppLst.push_back( *cit );
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
cppLst.push_back( *cit );
// Now size is doubled //
t1 = clock();
cppLst.sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nC++ library list sort was " << dt << " seconds.";
cout << " Expected: " << k*2*num*log(2*num) << '\n';
cout << '\n';
}
while( more() );
}
// 6sorts_timed_all_menu_version.cpp // // revised: 2016-05-05 //
#include "DLLinsertSorted.h"
// include <iostream> // included above //
#include <string>
#include <sstream> // re. istringstream
#include <cstdlib> // re, rand, srand
#include <ctime> // re, time clock
#include <climits> // re. RAND_MAX
#include <cctype> // re. tolower
#include <cmath> // re. log
#include <list> // to compare c++ library 'list sort' times with 'list sort' times //
const int MAX_PRINT = 5;
const int MAX_NxN = 20000;
const int MAX = 2000000;
const std::string MENU =
"1) Insert sort\n"
"2) Insert sorted\n"
"3) Select sort\n"
"4) Bubble sort\n"
"5) Merge sort\n"
"6) C++ list sort\n"
"0) Exit program\n"
"Your choice 0..6 ";
// 2 utilities to ease coding here ...
template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
T val = T();
while( true )
{
std::cout << msg;
if( std::cin >> val && std::cin.get() == '\n' )
break;
else
{
std::cout << errMsg;
std::cin.clear(); // clear error flags
std::cin.sync(); // 'flush' cin stream ...
}
}
return val;
}
char takeInChr( const std::string& msg )
{
std::cout << msg;
std::string reply;
getline( std::cin, reply );
if( reply.size() )
return reply[0];
// else ...
return 0;
}
// get a List of random ints in range 0..MAX_RAND
void fillUpList( List< int >& lst, int num )
{
std::cout << "RAND_MIN = " << 0 << ", RAND_MAX = " << RAND_MAX << '\n';
for( int i = 0; i < num; ++ i )
lst.push_back( rand() );
}
template < typename T >
std::ostream& operator << ( std::ostream& os, const List< T >& lst )
{
typename List< T >::const_iterator it;
for( it = lst.begin(); it != lst.end(); ++ it ) os << *it << ' ';
return os;
}
char showMenuGetChoice()
{
return takeInChr( MENU );
}
int main()
{
using std::cout; using std::cin;
using std::string; using std::istringstream;
srand( time(0) ); // seed the random generator //
for( ; ; )
{
int num = 0;
List< int > lst, lstCpy;
List< int >::const_iterator cit;
std::list< int > cppLst; // to compare times //
double dt, t1, k;
char choice = showMenuGetChoice();
if( choice == '0' )
break;
int max_size = MAX;
if( '1' <= choice && choice <= '4' )
max_size = MAX_NxN;
if( '1' <= choice && choice <= '6' )
{
// form prompt ...
std::ostringstream oss;
oss << "How many numbers to sort (3.." << max_size << ") : ";
for( ; ; )
{
cout << "To see numbers printed, choose a number <= " << MAX_PRINT << '\n';
num = takeIn< int >( oss.str() );
if( num >= 3 && num <= max_size )
break;
// else ...
cout << "\nTry again with a value in range 3.." << max_size << " ...\n\n";
}
fillUpList( lstCpy, num );
}
switch( choice )
{
case '1':
lst = lstCpy; // get from a copy //
t1 = clock();
lst.insert_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to insert_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
// t = k*n*n;
// k = t/n/n
k = dt/num/num;
lst = lstCpy;
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.push_back( *cit );
// Now size is doubled //
t1 = clock();
lst.insert_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to insert_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << 4*k*num*num << '\n';
break;
case '2':
lst.clear();
t1 = clock();
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.insert_sorted( *cit );
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to insert_sorted was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
k = dt/num/num;
lst.clear();
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.insert_sorted( *cit );
for( cit = lstCpy.begin(); cit != lstCpy.end(); cit ++ ) // test POST ++ //
lst.insert_sorted( *cit );
// Now size is doubled //
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to insert_sorted was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << 4*k*num*num << '\n';
break;
case '3':
lst = lstCpy; // restore from copy //
t1 = clock();
lst.select_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to select_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
k = dt/num/num;
lst = lstCpy; // restore from copy //
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.push_back( *cit );
// Now size is doubled //
t1 = clock();
lst.select_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to select_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << 4*k*num*num << '\n';
break;
case '4':
lst = lstCpy; // restore from copy //
t1 = clock();
lst.bubble_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to bubble_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
k = dt/num/num;
lst = lstCpy; // restore from copy //
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.push_back( *cit );
// Now size is doubled //
t1 = clock();
lst.bubble_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to bubble_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << 4*k*num*num << '\n';
break;
case '5':
lst = lstCpy; // restore from copy //
if( num <= MAX_PRINT ) cout << "\nUnsorted: " << lst << '\n';
t1 = clock();
lst.merge_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to merge_sort was " << dt<< " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
// t = k*n*log(n)
// k = t/n/og(n)
k = dt/num/log(num);
lst = lstCpy; // restore from copy //
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
lst.push_back( *cit );
// Now size is doubled //
t1 = clock();
lst.merge_sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nTime to merge_sort was " << dt << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << " Expected: " << k*2*num*log(2*num) << '\n';
break;
case '6':
// compare with C++ library list ...
cppLst.clear();
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
cppLst.push_back( *cit );
t1 = clock();
cppLst.sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nC++ library list sort was " << dt << " seconds.";
k = dt/num/log(num);
cppLst.clear();
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
cppLst.push_back( *cit );
for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
cppLst.push_back( *cit );
// Now size is doubled //
t1 = clock();
cppLst.sort();
dt = (clock() - t1)/CLOCKS_PER_SEC;
cout << "\nC++ library list sort was " << dt << " seconds.";
cout << " Expected: " << k*2*num*log(2*num) << '\n';
break;
default: cout << "choice '" << choice << "' is NOT implemented here ...\n";
} // end switch //
if( num <= MAX_PRINT )
{
if( '1' <= choice && choice <= '5' )
{
cout << "\nSorted : " << lst << "\nReversed: ";
lst.printReversed();
}
else if( choice == '6' )
{
cout << "\nSorted : ";
std::list< int >::const_iterator ccit;
for( ccit = cppLst.begin(); ccit != cppLst.end(); ++ ccit )
cout << *ccit << ' ';
cout << "\nReversed: ";
std::list< int >::const_reverse_iterator rit;
for( rit = cppLst.rbegin(); rit != cppLst.rend(); ++ rit )
cout << *rit << ' ';
}
}
cout << '\n';
} // end while //
}
// DDLsorts.h // // 2017-02-13 //
#ifndef DDLSORTS_H
#define DDLSORTS_H
#include <iostream>
template < typename T >
class List
{
struct Node
{
T data;
Node* prev;
Node* next;
Node( const T& data = T() ) : data(data), prev(0), next(0) {}
} ;
Node* head;
Node* tail;
size_t len;
public:
// ctor...
List() : head(0), tail(0), len(0) {}
//dtor...
~List() { clear(); }
void clear()
{
while( head )
{
Node* del = head;
head = head->next;
delete del;
}
tail = 0;
len = 0;
}
// copy ctor...
List ( const List& other )
{
head = tail = 0;
len = 0;
for( Node* cur = other.head; cur != 0; cur = cur->next )
push_back( cur->data );
}
// for ... def'n of overloaded (assignment) operator =
// see def'n below //
List& operator = ( const List& other ) ;
/*
{
if( this != &other )
{
clear();
for( Node* cur = other.head; cur != 0; cur = cur->next )
push_back( cur->data );
}
return *this;
}
*/
size_t size() const { return len; }
void push_front( const T& data )
{
Node* nNode = new Node( data );
if( len )
{
nNode->next = head; // N->A
head->prev = nNode; // N<-A
head = nNode;
}
else tail = head = nNode;
++len;
}
void push_back( const T& data )
{
Node* nNode = new Node( data );
if( len )
{
tail->next = nNode; // B->N
nNode->prev = tail; // B<-N
tail = nNode;
}
else tail = head = nNode;
++len;
}
void insert_sorted( const T& data )
{
Node* nNode = new Node( data );
// case 1 ... NOT inserted as the head node
if( head && head->data <= data )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur && cur->data <= data )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
nNode->prev = prev;
if( cur ) // NOT at end
{
cur->prev = nNode;
nNode->next = cur;
}
else // at end
{
tail = nNode;
}
}
else // insert at head ...
{
if( len )
{
nNode->next = head;
head->prev = nNode;
head = nNode;
}
else tail = head = nNode;
}
++ len;
}
// a re-link method ... might be faster? for LARGE data records ? //
void insert_sorted( Node* nNode )
{
// case 1 ... NOT inserted as the head node
if( head && head->data <= nNode->data )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur && cur->data <= nNode->data )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
nNode->prev = prev;
if( cur ) // NOT at end
{
cur->prev = nNode;
nNode->next = cur;
}
else // at end
{
nNode->next = 0;
tail = nNode;
}
}
else // insert at head ...
{
nNode->prev = 0;
if( len )
{
nNode->next = head;
head->prev = nNode;
head = nNode;
}
else { nNode->next= 0 ; tail = head = nNode; }
}
++ len;
}
// Note! This method, (moving and re-linking Nodes),
// is MUCH slower than that below, for small (int) data records tested //
void relink_insert_sort()
{
if( len > 1 ) // then head and cur != 0 //
{
Node* cur = head;
Node* next = cur->next;
head = tail = 0;
len = 0;
for( ; ; next = cur->next )
{
insert_sorted( cur );
cur = next;
if( !cur ) break;
}
}
}
void insert_sort()
{
if( len > 1 )
{
Node* cur = head->next;
for( ; cur != 0; cur = cur->next ) /* start with set of just the first 2 elements (if exists) */
{
T cmp = cur->data; /* get copy of this new cmp element on each outer loop ... */
Node* prev = cur->prev; /* get Node of element just to the left of the above 'cmp' to start comparisons */
while( prev != 0 && cmp < prev->data )
{
prev->next->data = prev->data; /* copy element 'up' ... */
prev = prev->prev; /* decrement j in preparation for next inner loop ... */
}
/* insert element at prev->next (since prev was 'decremented' above) */
if( prev ) prev->next->data = cmp;
else head->data = cmp;
}
}
}
void select_sort()
{
Node* cur = head;
while( cur )
{
Node* min = cur;
Node* next = cur->next;
while( next )
{
if( next->data < min->data ) min = next; // update if needed //
next = next->next;
}
if( cur != min ) // swap min and cur //
{
T tmp = cur->data;
cur->data = min->data;
min->data = tmp;
}
cur = cur->next;
}
}
void select_sort_simpler()
{
Node* cur = head;
while( cur )
{
Node* min = cur;
Node* next = cur->next;
while( next )
{
if( next->data < min->data ) min = next; // update if needed //
next = next->next;
}
T tmp = cur->data;
cur->data = min->data;
min->data = tmp;
cur = cur->next;
}
}
void bubble_sort()
{
if( len > 1 )
{
Node* end = 0;
Node* cur = head->next; // start 1 element in //
bool swap;
bool pass = false;
do
{
swap = false;
while( cur != end )
{
if( cur->data < cur->prev->data ) // swap //
{
T tmp = cur->data;
cur->data = cur->prev->data;
cur->prev->data = tmp;
swap = true;
}
cur = cur->next;
}
if( pass ) end = end->prev;
else end = tail;
pass = true;
if( !end ) break;
cur = head->next; // get ready ready for next outer (do) loop //
}
while( swap );
}
}
void print( std::ostream& os = std::cout ) const
{
Node* cur = head;
while( cur )
{
os << cur->data << ' ';
cur = cur->next;
}
}
void printReversed( std::ostream& os = std::cout ) const
{
Node* cur = tail;
while( cur )
{
os << cur->data << ' ';
cur = cur->prev;
}
}
bool isSorted() const
{
if( len > 1 )
{
Node* cur = head;
while( cur->next )
{
if( cur->next->data < cur->data ) return false;
cur = cur->next;
}
}
return true;
}
} ;
// def'n of overloaded (assignment) operator =
template< typename T >
List< T >& List< T >::operator = ( const List& other )
{
if( this != &other )
{
clear();
for( Node* cur = other.head; cur != 0; cur = cur->next )
push_back( cur->data );
}
return *this;
}
#endif
// test_DLLSorts.h.cpp // // 2017-02-13 //
#include "DLLsorts.h"
// include <iostream> // included above //
#include <string>
int main()
{
using std::string;
using std::cout;
using std::cin;
List < string > myLst;
cout << "Now testing push_front: ";
myLst.push_front( "Sam" );
myLst.push_front( "Anne" );
myLst.push_front( "Joe" );
myLst.push_front( "Zak" );
List< string > myLstCpy( myLst ); // construct a (backup) copy //
myLst.print();
cout << "\nPrinting after relink_insert_sort: ";
myLst.relink_insert_sort();
myLst.print();
cout << "\nPrinting reversed: ";
myLst.printReversed();
myLst.clear();
cout << "\n\nNow testing push_back: ";
myLst.push_back( "Sam" );
myLst.push_back( "Anne" );
myLst.push_back( "Joe" );
myLst.push_back( "Zak" );
myLst.print();
cout << "\nPrinting after insert_sort: ";
myLst.insert_sort();
myLst.print();
cout << "\nPrinting reversed: ";
myLst.printReversed();
myLst.clear();
cout << "\n\nNow testing insert_sorted: ";
myLst.insert_sorted( "Billy" );
myLst.insert_sorted( "Sam" );
myLst.insert_sorted( "Joe" );
myLst.insert_sorted( "Anne" );
myLst.insert_sorted( "Jill" );
myLst.insert_sorted( "Zak" );
myLst.print();
cout << "\nPrinting reversed: ";
myLst.printReversed();
myLst = myLstCpy; // restore from copy //
cout << "\n\nPrinting before select_sort: ";
myLst.print();
cout << "\nPrinting after select_sort: ";
myLst.select_sort();
myLst.print();
myLst = myLstCpy; // restore from copy //
cout << "\n\nPrinting before select_sort_simpler: ";
myLst.print();
cout << "\nPrinting after select_sort_simpler: ";
myLst.select_sort_simpler();
myLst.print();
myLst = myLstCpy; // restore from copy //
cout << "\n\nPrinting before bubble_sort: ";
myLst.print();
cout << "\nPrinting after bubble_sort: ";
myLst.bubble_sort();
myLst.print();
cout << "\n\nPress 'Enter' to continue/exit ...";
cin.get();
}
// timed_DLLsorts.cpp // // 2017-02-13 //
#include "DLLsorts.h"
// include <iostream> // included above //
#include <string>
#include <sstream> // re. stringstream
#include <cstdlib> // re, rand, srand
#include <ctime> // re, time clock
const int MAX_SIZE = 30000;
template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
T val = T();
while( true )
{
std::cout << msg << std::flush;
if( std::cin >> val && std::cin.get() == '\n' )
break;
else
{
std::cout << errMsg;
std::cin.clear(); // clear error flasgs
std::cin.sync(); // 'flush' cin stream ...
}
}
return val;
}
char takeInChr( const std::string& msg )
{
std::cout << msg;
std::string reply;
getline( std::cin, reply );
if( reply.size() )
return reply[0];
// else ...
return 0;
}
bool more( const std::string& text = "" )
{
char reply = takeInChr( "More " + text + "(y/n) ? " );
if( reply == 'n' || reply == 'N' )
return false;
// else ...
return true;
}
void fillUpList( List< int >& lst, int num )
{
for( int i = 0; i < num; ++ i )
lst.push_back( rand() );
}
int main()
{
using std::cout; using std::cin;
using std::string; using std::stringstream;
srand( time(0) ); // seed the random generator //
do
{
int num = 0;
for( ; ; )
{
stringstream ss;
ss << MAX_SIZE;
num = takeIn< int >( "How many numbers to sort (10000.." + ss.str() + "): " );
if( num >= 10000 && num <= MAX_SIZE ) break;
//else ///
cout << "\nTry again with a value in range 10000.." << MAX_SIZE << " ...\n\n";
}
List< int > lst;
fillUpList( lst, num );
List< int > lstCpy( lst ); // save a (backup) copy //
double t1 = clock();
lst.insert_sort();
double t2 = clock();
cout << "\nTime to insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
lst.push_front(1000000);
cout << "\nIf already was (mostly) sorted ...\n";
t1 = clock();
lst.insert_sort();
t2 = clock();
cout << "Time to insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
lst = lstCpy;
t1 = clock();
lst.relink_insert_sort();
t2 = clock();
cout << "\n\nTime to relink_insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
lst.push_front(1000000);
cout << "\nIf already was (mostly) sorted ...\n";
t1 = clock();
lst.relink_insert_sort();
t2 = clock();
cout << "Time to relink_insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
lst = lstCpy; // restore from copy //
t1 = clock();
lst.select_sort();
t2 = clock();
cout << "\n\nTime to select_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
lst.push_front(1000000);
cout << "\nIf already was (mostly) sorted ...\n";
t1 = clock();
lst.select_sort();
t2 = clock();
cout << "Time to select_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
lst = lstCpy; // restore from copy //
t1 = clock();
lst.select_sort_simpler();
t2 = clock();
cout << "\n\nTime to select_sort_simpler was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
lst.push_front(1000000);
cout << "\nIf already was (mostly) sorted ...\n";
t1 = clock();
lst.select_sort_simpler();
t2 = clock();
cout << "Time to select_sort_simpler was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
lst = lstCpy; // restore from copy //
t1 = clock();
lst.bubble_sort();
t2 = clock();
cout << "\n\nTime to bubble_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
lst.push_front(1000000);
cout << "\nIf already was (mostly) sorted ...\n";
t1 = clock();
lst.bubble_sort();
t2 = clock();
cout << "Time to bubble sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
<< ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
cout << "\n\n";
}
while( more() );
}