Whenever I try to sort an array using a pivot one of the values gets replaced by a large negative number

Question

This is the header file, the sort functions are at the 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 the assignment operator
    bool isEmpty();
    //Function to determine whether the list is empty
    //Postcondition: Returns true if the list is empty; 
    //    otherwise, returns false.
    bool isFull();
    //Function to determine whether the list is full.
    //Postcondition: Returns true if the list is full; 
    //    otherwise, returns false.
    int listSize();
    //Function to determine the number of elements in the list
    //Postcondition: Returns the value of length.
    int maxListSize();
    //Function to determine the size of the list.
    //Postcondition: Returns the value of maxSize.
    void print() const;
    //Function to output the elements of the list
    //Postcondition: Elements of the list are output on the 
    //   standard output device.
    bool isItemAtEqual(int location, const elemType& item);
    //Function to determine whether the item is the same 
    //as the item in the list at the position specified by
    //Postcondition: Returns true if the list[location] 
    //    is the same as the item; otherwise, 
    //               returns false.
    void insertAt(int location, const elemType& insertItem);
    //Function to insert an item in the list at the 
    //position specified by location. The item to be inserted 
    //is passed as a parameter to the function.
    //Postcondition: Starting at location, the elements of the
    //    list are shifted down, list[location] = insertItem;,
    //    and length++;. If the list is full or location is
    //    out of range, an appropriate message is displayed.
    void insertEnd(const elemType& insertItem);
    //Function to insert an item at the end of the list. 
    //The parameter insertItem specifies the item to be inserted.
    //Postcondition: list[length] = insertItem; and length++;
    //    If the list is full, an appropriate message is 
    //    displayed.
    void removeAt(int location);
    //Function to remove the item from the list at the 
    //position specified by location 
    //Postcondition: The list element at list[location] is removed
    //    and length is decremented by 1. If location is out of 
    //    range,an appropriate message is displayed.
    void retrieveAt(int location, elemType& retItem);
    //Function to retrieve the element from the list at the  
    //position specified by location. 
    //Postcondition: retItem = list[location] 
    //    If location is out of range, an appropriate message is
    //    displayed.
    void replaceAt(int location, const elemType& repItem);
    //Function to replace the elements in the list at the 
    //position specified by location. The item to be replaced 
    //is specified by the parameter repItem.
    //Postcondition: list[location] = repItem 
    //    If location is out of range, an appropriate message is
    //    displayed.
    void clearList();
    //Function to remove all the elements from the list. 
    //After this operation, the size of the list is zero.
    //Postcondition: length = 0;
    int seqSearch(const elemType& item);
    //Function to search the list for a given item. 
    //Postcondition: If the item is found, returns the location 
    //    in the array where the item is found; otherwise,
    //    returns -1.
    void insert(const elemType& insertItem);
    //Function to insert the item specified by the parameter 
    //insertItem at the end of the list. However, first the
    //list is searched to see whether the item to be inserted 
    //is already in the list. 
    //Postcondition: list[length] = insertItem and length++
    //     If the item is already in the list or the list
    //     is full, an appropriate message is displayed.
    void remove(const elemType& removeItem);
    //Function to remove an item from the list. The parameter 
    //removeItem specifies the item to be removed.
    //Postcondition: If removeItem is found in the list,
    //      it is removed from the list and length is 
    //      decremented by one.

    arrayListType(int size = 100);
    //constructor
    //Creates an array of the size specified by the 
    //parameter size. The default array size is 100.
    //Postcondition: The list points to the array, length = 0, 
    //    and maxSize = size

    arrayListType(const arrayListType<elemType>& otherList);
    //copy constructor

    ~arrayListType();
    //destructor
    //Deallocates the memory occupied by the 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 to hold the list elements
    int length;      //to store the length of the list
    int maxSize;     //to store the maximum size of the 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
{
    for (int i = 0; i < 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 the item to be inserted "
        << "is out of range" << endl;
    else
    if (length >= maxSize)  //list is full
        cerr << "Cannot insert in a full list" << endl;
    else
    {
        for (int i = length; i > location; i--)
            list[i] = list[i - 1];   //move the elements down

        list[location] = insertItem;  //insert the item at the 
        //specified position

        length++;     //increment the length
    }
} //end insertAt

template <class elemType>
void arrayListType<elemType>::insertEnd(const elemType& insertItem)
{

    if (length >= maxSize)  //the list is full
        cerr << "Cannot insert in a full list" << endl;
    else
    {
        list[length] = insertItem;   //insert the item at the end
        length++;   //increment the length
    }
} //end insertEnd

template <class elemType>
void arrayListType<elemType>::removeAt(int location)
{
    if (location < 0 || location >= length)
        cerr << "The location of the item to be removed "
        << "is out of range" << endl;
    else
    {
        for (int i = location; i < 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 the item to be retrieved is "
        << "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 the item to be replaced is "
        << "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;

    for (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 is empty
        list[length++] = insertItem;    //insert the item and 
    //increment the length
    else if (length == maxSize)
        cerr << "Cannot insert in a full list." << endl;
    else
    {
        loc = seqSearch(insertItem);

        if (loc == -1)    //the item to be inserted 
            //does not exist in the list
            list[length++] = insertItem;
        else
            cerr << "the item to be inserted is already in "
            << "the list. No duplicates are allowed." << endl;
    }
} //end insert

template<class elemType>
void arrayListType<elemType>::remove(const elemType& removeItem)
{
    int loc;

    if (length == 0)
        cerr << "Cannot delete from an empty list." << endl;
    else
    {
        loc = seqSearch(removeItem);

        if (loc != -1)
            removeAt(loc);
        else
            cout << "The item to be deleted is not in the list."
            << endl;
    }
} //end remove

template <class elemType>
arrayListType<elemType>::arrayListType(int size)
{
    if (size < 0)
    {
        cerr << "The array size must be 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 the array
    assert(list != NULL);         //terminate if unable to allocate
    //memory space

    for (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 the array
        assert(list != NULL);   //if unable to allocate memory 
        //space, terminate the program 
        for (int i = 0; i < length; i++)
            list[i] = otherList.list[i];
    }

    return *this;
}

template <class elemType>
void arrayListType<elemType>::insertionSort()
{
    int firstOutOfOrder, location;
    elemType temp;

    for (firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++)
    {
        if (list[firstOutOfOrder] < list[firstOutOfOrder - 1])
        {
            temp = list[firstOutOfOrder];
            location = firstOutOfOrder;

            do
            {
                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++;
        }

    }

}*/

// The 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;
}

// The 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 that the error is occurring inside of the partition.

This is the driver.

//**************************************************************
// Author: D.S. Malik
//
// This program illustrates how to use selection sort in a 
// 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 with -999"
        //<< endl;                                        //Line 8

    //cin >> num;                                          //Line 9

    srand(time(NULL));
    //list.maxListSize()
    for (int i =0; i <= 20; i++)                                  //Line 10
    {                                                    //Line 11
        list.insert(rand() % 10000 + 1);                                //Line 12
        //cin >> num;                                      //Line 13
    }                                                    //Line 14

    testlist = list;

    cout << "Line 15: The 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: The 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 at this for way to long. I know it is a pretty obvious fix but I just can't seem to find it!

Answer 1

In arrayListType<elemType>::partition(int p, int r) you access list[r]. When partition gets called the first time, r equals listSize(), which is one past the last element.