quicksort

[Hector_2]

This is supposed to used quick sort using the header "arrayListType.h using quick sort and get the numbers entered smallest to largest but I'm not sure on how to do it. Can I please get some help?

#include <iostream>
#include "arrayListType.h"
#include <cstdlib>
using namespace std;
void printList(arrayListType<int>& list);

void quickSort(arrayListType<int>& list);
//
int main()
{

    arrayListType<int> intList;
    //
    int num;
    cout << "Sorting Algorithms\n\n";

    cout << "";

    cout << "Enter numbers (-999 to stop: " << endl;

    cin >> num;

    while (num != -999)
    {

        intList.insert(num);
        cin >> num;
    }
    cout << "\nThe numbers you entered are: " << endl;

    printList(intList);

    cout << "\nThe list after sorting: " << endl;

    quickSort(intList);


    cout << "\n\n\n\n";
   system("pause");
    return 0;
}
//
void printList(arrayListType<int>& list)
{

 list.print();

}
//
void quickSort(arrayListType<int>& list)
{


    list.print();
    cout << "\nSize of list is: " << list.listSize() << endl;
}

"arrayListType.h"

#ifndef H_arrayListType
#define H_arrayListType

//*************************************************************
// This class specifies the operations to implement a list as
// an array.
//*************************************************************

#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() const;
      //Function to determine whether the list is empty
      //Postcondition: Returns true if the list is empty;
      //    otherwise, returns false.
    bool isFull() const;
      //Function to determine whether the list is full.
      //Postcondition: Returns true if the list is full;
      //    otherwise, returns false.
    int listSize() const;
      //Function to determine the number of elements in the list
      //Postcondition: Returns the value of length.
    int maxListSize() const;
      //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) const;
      //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) const;
      //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) const;
      //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.

    int recursiveSeqSearch(const elemType& item) const;
       //Recursive sequential search.
       //Searches the list for a given item. If item is found,
       //returns location where in the array the item is found;
       //otherwise returns -1.


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

private:
    int recSeqSearch(const elemType& item, int first, int last) const;

};

template <class elemType>
int arrayListType<elemType>::recSeqSearch(const elemType& item,
                                          int first, int last) const
{
    if (first <= last)
    {
        if (list[first] == item)
            return first;
        else
            return recSeqSearch(item, first + 1, last);
    }
    else
        return -1;
}

template <class elemType>
int arrayListType<elemType>:: recursiveSeqSearch(const elemType& item) const
{
    return recSeqSearch(item, 0, length - 1);
}

template <class elemType>
bool arrayListType<elemType>::isEmpty() const
{
    return (length == 0);
}

template <class elemType>
bool arrayListType<elemType>::isFull() const
{
    return (length == maxSize);
}

template <class elemType>
int arrayListType<elemType>::listSize() const
{
    return length;
}

template <class elemType>
int arrayListType<elemType>::maxListSize() const
{
    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) const
{
    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 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) const
{
    if (location < 0 || location >= length)
        cerr << "The location of the item to be retrieved is "
             << "out of range" << endl;
    else
        retItem = list[location];
} // 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) const
{
    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)
        cout << "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 tem 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;
}


    //copy constructor
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];
       assert(list != NULL);

       for (int i = 0; i < length; i++)
            list[i] = otherList.list[i];
    }

    return *this;
}

#endif

[ddanbe]

Do you think more than 400 lines of code are going to impress anyone here?
Ifyou want code for quicksort, just google.

[Hector_2]

I'm not trying to impress anyone. This is for a class and I need to use the "arrayListType.h". Then some of those lines are just comments. I'm just trying to figure this out.

[rubberman]

Quicksort is implemented in C with the qsort() function. It is fast, efficient. You aren't sorting in your code. RTFM... For C++/Java code, look here: http://www.algolist.net/Algorithms/Sorting/Quicksort

FWIW, you should be able to do this in about 10-20 lines of code. A bit more if you implement all the low-level stuff yourself.

[deceptikon]

Quicksort is implemented in C with the qsort() function.

The interesting thing is the C standard doesn't in any way require that qsort be implemented as quicksort, nor does it impose any performance requirements in the same way that C++'s sort function does. The C++ standard retains this lack of guarantees for the C library functions.

You can expect it to be efficient, of course, given that implementors are not stupid. As an example, I chose heapsort as the qsort implementation for simplicity of implementation and guaranteed time complexity across the board. From stdlib.c:

/*
    @description:
        Sorts an array of n objects, the initial element of which is
        pointed to by base. The size of each element is specified by size.
*/
void qsort(void *base, size_t n, size_t size, _cmp_func_t cmp)
{
    _sort(base, n, size, cmp);
}

And from _sort.c:

#include "_sort.h"
#include "_system.h"
#include "stdint.h"
#include "stdlib.h"
#include "string.h"

static void do_heap(void *temp, uint8_t *base, size_t i, size_t n, size_t size, _cmp_func_t cmp);

/*
    @description:
        qsort-friendly implementation of heapsort for guaranteed time complexity.
*/
void _sort(void *base, size_t n, size_t size, _cmp_func_t cmp)
{
    void *temp = _sys_alloc(size); // The size of items is unknown, so we must allocate
    uint8_t *p = (uint8_t*)base;   // Pun the base into a byte array
    size_t i = n / 2;

    // Heapify the array
    while (i-- > 0)
    {
        do_heap(temp, p, i, n, size, cmp);
    }

    // Extract the heap max and place it in sorted position
    while (--n < (size_t)-1)
    {
        // Swap the heap max with base[n]
        memcpy(temp, p, size);
        memcpy(p, &p[n * size], size);
        memcpy(&p[n * size], temp, size);

        // Re-heapify after removing the heap max
        do_heap(temp, p, 0, n, size, cmp);
    }

    _sys_free(temp);
}

/*
    @description:
        Heapify helper for _sort.
*/
void do_heap(void *temp, uint8_t *base, size_t i, size_t n, size_t size, _cmp_func_t cmp)
{
    // Save the node that's being overwritten below
    memcpy(temp, &base[i * size], size);

    // Move all subsequent child nodes into place to maintain the heap property
    for (size_t k = i * 2 + 1; k < n; k = i * 2 + 1)
    {
        // Find the next child node
        if (k + 1 < n && cmp(&base[k * size], &base[(k + 1) * size]) < 0)
        {
            ++k;
        }

        // Are we at the saved node's sorted position?
        if (cmp(temp, &base[k * size]) >= 0)
        {
            break;
        }

        // Overwrite the parent with one of its children
        memcpy(&base[i * size], &base[k * size], size);
        i = k;
    }

    // Copy the saved node into its final resting place
    memcpy(&base[i * size], temp, size);
}

But I might update it in the future with introsort.

I'm told that this doesn't sufficiently explain the inner workings of the algorithms for a beginner to sorting, so I'm interested in critiques so I can improve the tutorial, but it includes full working code for a number of common algorithms and may help.

[rubberman]

I wrote a widely used C++ sorted collection that used a modified qsort algorithm to implement an insertion sort, with head-tail optimization to deal with already sorted incoming data efficiently. The collections would remain sorted without additional work, and it was very fast for very large collections (100,000+ elements). Below is an example of some of the code I wrote for an options trading framework some years ago (2006). The original code was written some years before this, but was similar in most respects. I can't post that code here since it is owned by Applied Materials. This is my code, with no encumbrances. Use if if you wish - I can release it under an LGPL license if needed.

       virtual void insert( CT* pItem ) throw (NoMemoryError, InvalidArgumentError, DuplicateObjectError)
        {
            size_t locn;
            size_t where = findItem(pItem, locn);
            if (where != SIZE_MAX)
            {
                // Item has been found. Insert after other member.
                locn = where + 1;
            }
            Collection<CT>::insertAt(pItem, locn);
        }

        size_t findItem( const CT* pItem, size_t& locn ) const throw (InvalidArgumentError, MissingObjectError)
        {
            if (!pItem)
            {
                InvalidArgumentError err;
                err.setMessage(0, "pItem", "is nil");
                throw err;
            }
            size_t cnt = entries();
            size_t curr = 0;
            size_t found = SIZE_MAX;
            if (cnt > 0)
            {
                // Note: this will have to be adjusted to accomodate sparse arrays.
                const CT* pMember = 0;

                bool done = false;
                for (size_t left = 0, right = cnt - 1; !done; )
                {
                    size_t mid = (left + right)/2;

                    pMember = getPtrAt(mid);
                    if (pMember == 0)
                    {
                        MissingObjectError err;
                        throw err;
                    }

                    int diff = compare(pItem, pMember);
                    if (diff > 0 && mid < right)
                    {
                        curr = left = mid + 1;
                    }
                    else if (diff < 0 && mid > left)
                    {
                        curr = right = mid - 1;
                    }
                    else
                    {
                        done = true;
                        if (diff < 0)
                        {
                            curr = mid;
                        }
                        else if (diff > 0)
                        {
                            curr = mid + 1;
                        }
                        else
                        {
                            found = mid;
                            while (diff == 0 && mid < cnt)
                            {
                                curr = ++mid;
                                if (mid < cnt)
                                {
                                    pMember = getPtrAt(mid);
                                    diff = compare(pItem, pMember);
                                    if (diff == 0)
                                    {
                                        found = mid;
                                    }
                                }
                            }
                        }
                    }
                }

            }
            locn = curr;
            return found;
        }