c++ - Whenever I try to sort an array using a pivot one of the values gets replaced by a large negative number -
this header file, sort functions @ end.
#ifndef h_arraylisttype #define h_arraylisttype #include <iostream> #include <cassert> using namespace std; template <class elemtype> class arraylisttype { public: const arraylisttype<elemtype>& operator= (const arraylisttype<elemtype>&); //overloads assignment operator bool isempty(); //function determine whether list empty //postcondition: returns true if list empty; // otherwise, returns false. bool isfull(); //function determine whether list full. //postcondition: returns true if list full; // otherwise, returns false. int listsize(); //function determine number of elements in list //postcondition: returns value of length. int maxlistsize(); //function determine size of list. //postcondition: returns value of maxsize. void print() const; //function output elements of list //postcondition: elements of list output on // standard output device. bool isitematequal(int location, const elemtype& item); //function determine whether item same //as item in list @ position specified //postcondition: returns true if list[location] // same item; otherwise, // returns false. void insertat(int location, const elemtype& insertitem); //function insert item in list @ //position specified location. item inserted //is passed parameter function. //postcondition: starting @ location, elements of // list shifted down, list[location] = insertitem;, // , length++;. if list full or location // out of range, appropriate message displayed. void insertend(const elemtype& insertitem); //function insert item @ end of list. //the parameter insertitem specifies item inserted. //postcondition: list[length] = insertitem; , length++; // if list full, appropriate message // displayed. void removeat(int location); //function remove item list @ //position specified location //postcondition: list element @ list[location] removed // , length decremented 1. if location out of // range,an appropriate message displayed. void retrieveat(int location, elemtype& retitem); //function retrieve element list @ //position specified location. //postcondition: retitem = list[location] // if location out of range, appropriate message // displayed. void replaceat(int location, const elemtype& repitem); //function replace elements in list @ //position specified location. item replaced //is specified parameter repitem. //postcondition: list[location] = repitem // if location out of range, appropriate message // displayed. void clearlist(); //function remove elements list. //after operation, size of list zero. //postcondition: length = 0; int seqsearch(const elemtype& item); //function search list given item. //postcondition: if item found, returns location // in array item found; otherwise, // returns -1. void insert(const elemtype& insertitem); //function insert item specified parameter //insertitem @ end of list. however, first //list searched see whether item inserted //is in list. //postcondition: list[length] = insertitem , length++ // if item in list or list // full, appropriate message displayed. void remove(const elemtype& removeitem); //function remove item list. parameter //removeitem specifies item removed. //postcondition: if removeitem found in list, // removed list , length // decremented one. arraylisttype(int size = 100); //constructor //creates array of size specified //parameter size. default array size 100. //postcondition: list points array, length = 0, // , maxsize = size arraylisttype(const arraylisttype<elemtype>& otherlist); //copy constructor ~arraylisttype(); //destructor //deallocates memory occupied array. void insertionsort(); //middlepivot(const arraylisttype<elemtype>& otherlist, elemtype& length); int partition(int p, int r); void quicksort(int p, int r); protected: elemtype *list; //array hold list elements int length; //to store length of list int maxsize; //to store maximum size of list void swap(int first, int second); int minlocation(int first, int last); }; template <class elemtype> bool arraylisttype<elemtype>::isempty() { return (length == 0); } template <class elemtype> bool arraylisttype<elemtype>::isfull() { return (length == maxsize); } template <class elemtype> int arraylisttype<elemtype>::listsize() { return length; } template <class elemtype> int arraylisttype<elemtype>::maxlistsize() { return maxsize; } template <class elemtype> void arraylisttype<elemtype>::print() const { (int = 0; < length; i++) cout << list[i] << " "; cout << endl; } template <class elemtype> bool arraylisttype<elemtype>::isitematequal (int location, const elemtype& item) { return(list[location] == item); } template <class elemtype> void arraylisttype<elemtype>::insertat (int location, const elemtype& insertitem) { if (location < 0 || location >= maxsize) cerr << "the position of item inserted " << "is out of range" << endl; else if (length >= maxsize) //list full cerr << "cannot insert in full list" << endl; else { (int = length; > location; i--) list[i] = list[i - 1]; //move elements down list[location] = insertitem; //insert item @ //specified position length++; //increment length } } //end insertat template <class elemtype> void arraylisttype<elemtype>::insertend(const elemtype& insertitem) { if (length >= maxsize) //the list full cerr << "cannot insert in full list" << endl; else { list[length] = insertitem; //insert item @ end length++; //increment length } } //end insertend template <class elemtype> void arraylisttype<elemtype>::removeat(int location) { if (location < 0 || location >= length) cerr << "the location of item removed " << "is out of range" << endl; else { (int = location; < length - 1; i++) list[i] = list[i + 1]; length--; } } //end removeat template <class elemtype> void arraylisttype<elemtype>::retrieveat (int location, elemtype& retitem) { if (location < 0 || location >= length) cerr << "the location of item retrieved " << "out of range." << endl; else retitem = list[location]; } //end retrieveat template <class elemtype> void arraylisttype<elemtype>::replaceat (int location, const elemtype& repitem) { if (location < 0 || location >= length) cerr << "the location of item replaced " << "out of range." << endl; else list[location] = repitem; } //end replaceat template <class elemtype> void arraylisttype<elemtype>::clearlist() { length = 0; } //end clearlist template <class elemtype> int arraylisttype<elemtype>::seqsearch(const elemtype& item) { int loc; bool found = false; (loc = 0; loc < length; loc++) if (list[loc] == item) { found = true; break; } if (found) return loc; else return -1; } //end seqsearch template <class elemtype> void arraylisttype<elemtype>::insert(const elemtype& insertitem) { int loc; if (length == 0) //list empty list[length++] = insertitem; //insert item , //increment length else if (length == maxsize) cerr << "cannot insert in full list." << endl; else { loc = seqsearch(insertitem); if (loc == -1) //the item inserted //does not exist in list list[length++] = insertitem; else cerr << "the item inserted in " << "the list. no duplicates allowed." << endl; } } //end insert template<class elemtype> void arraylisttype<elemtype>::remove(const elemtype& removeitem) { int loc; if (length == 0) cerr << "cannot delete empty list." << endl; else { loc = seqsearch(removeitem); if (loc != -1) removeat(loc); else cout << "the item deleted not in list." << endl; } } //end remove template <class elemtype> arraylisttype<elemtype>::arraylisttype(int size) { if (size < 0) { cerr << "the array size must positive. creating " << "an array of size 100. " << endl; maxsize = 100; } else maxsize = size; length = 0; list = new elemtype[maxsize]; assert(list != null); } template <class elemtype> arraylisttype<elemtype>::~arraylisttype() { delete[] list; } template <class elemtype> arraylisttype<elemtype>::arraylisttype (const arraylisttype<elemtype>& otherlist) { maxsize = otherlist.maxsize; length = otherlist.length; list = new elemtype[maxsize]; //create array assert(list != null); //terminate if unable allocate //memory space (int j = 0; j < length; j++) //copy otherlist list[j] = otherlist.list[j]; } //end copy constructor template <class elemtype> const arraylisttype<elemtype>& arraylisttype<elemtype>::operator= (const arraylisttype<elemtype>& otherlist) { if (this != &otherlist) //avoid self-assignment { delete[] list; maxsize = otherlist.maxsize; length = otherlist.length; list = new elemtype[maxsize]; //create array assert(list != null); //if unable allocate memory //space, terminate program (int = 0; < length; i++) list[i] = otherlist.list[i]; } return *this; } template <class elemtype> void arraylisttype<elemtype>::insertionsort() { int firstoutoforder, location; elemtype temp; (firstoutoforder = 1; firstoutoforder < length; firstoutoforder++) { if (list[firstoutoforder] < list[firstoutoforder - 1]) { temp = list[firstoutoforder]; location = firstoutoforder; { list[location] = list[location - 1]; location--; } while (location > 0 && list[location - 1] > temp); list[location] = temp; } } } // end insertionsort /*template <class elemtype> arraylisttype<elemtype>::middlepivot(elemtype& length){ int left=0; int right=0; int pivotcnt=0; int first=0; int last=length; int pivot=last/2; int left[pivot]; int right[pivot]; for(int i=0; i<=last; i++){ if(list[i] < list[pivot]){ left[left] = list[i]; left++; }if(list[i] > list[pivot]){ right[right] = list[i]; right++; }else{ pivotcnt++; } } }*/ // partition function template <class elemtype> int arraylisttype<elemtype>::partition(int p, int r) { int pivot = list[(r+p)/2]; while ( p < r ) { while ( list[p] < pivot ) p++; while ( list[r] > pivot ) r--; if ( list[p] == list[r] ) p++; else if ( p < r ) { int tmp = list[p]; list[p] = list[r]; list[r] = tmp; } } return r; } // quicksort recursive function template <class elemtype> void arraylisttype<elemtype>::quicksort(int p, int r) { if ( p < r ) { int j = partition(p, r); quicksort(p, j-1); quicksort(j+1, r); } } #endif i believe error occurring inside of partition.
this driver.
//************************************************************** // author: d.s. malik // // program illustrates how use selection sort in // program. //************************************************************** #include <iostream> //line 1 #include <ctime> #include "arraylisttype.h" //line 2 using namespace std; //line 3 int main() //line 4 { //line 5 arraylisttype<int> list(20); arraylisttype<int> testlist(20); //arraylisttype<int> list; //line 6 int num; //line 7 //cout << "line 8: enter numbers ending -999" //<< endl; //line 8 //cin >> num; //line 9 srand(time(null)); //list.maxlistsize() (int =0; <= 20; i++) //line 10 { //line 11 list.insert(rand() % 10000 + 1); //line 12 //cin >> num; //line 13 } //line 14 testlist = list; cout << "line 15: list before sorting:" << endl; //line 15 testlist.print(); //line 16 cout << endl; //line 17 //middle sort testlist.quicksort(0, testlist.listsize()); //line 18 cout << "line 19: list after sorting:" << endl; //line 19 testlist.print(); //line 20 cout << endl; //line 21 system("pause>nul"); //line 22 return 0; //line 23 } //line 23 i have been staring @ way long. know pretty obvious fix can't seem find it!
in arraylisttype<elemtype>::partition(int p, int r) access list[r]. when partition gets called first time, r equals listsize(), 1 past last element.
Comments
Post a Comment