Recursive Sorting Array

[hentaiw]

//Tests the Divide-and-Conquer Sorting pattern.
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

//This is the file sortpattern.cpp.
template <class T>
int split(T a[], int begin, int end);
//Rearranges elements [begin, end) of array a into two intervals
//[begin, splitPt) and [splitPt, end), such that the Sorting pattern works.
//Returns splitPt. 
template <class T>
void join(T a[], int begin, int splitPt, int end);
//Combines the elements in the two intervals [begin, split) and 
//[splitPt, end) in such a way that the Sorting pattern works.


void fillArray(int a[], int size, int& numberUsed);
//Precondition: size is the declared size of the array a.
//Postcondition: numberUsed is the number of values stored in a.
//a[0] through a[numberUsed - 1] have been filled with
//nonnegative integers read from the keyboard.


template <class T>
void sort(T a[], int begin, int end)
//Precondition: Interval [begin, end) of a has elements.
//Postcondition: The values in the interval [begin, end) have
//been rearranged so that a[0] <= a[1] <= ... <= a[(end - begin) - 1].
{
    if ((end - begin) > 1)
    {
        int splitPt = split(a, begin, end);
        sort(a, begin, splitPt);
        sort(a, splitPt, end);
        join(a, begin, splitPt, end);
    }//else sorting one (or fewer) elements, so do nothing.
}

template <class T>
void sort(T a[], int numberUsed)
//Precondition: numberUsed <= declared size of the array a.
//The array elements a[0] through a[numberUsed - 1] have values.
//Postcondition: The values of a[0] through a[numberUsed - 1] have
//been rearranged so that a[0] <= a[1] <= ... <= a[numberUsed - 1].
{
    sort(a, 0, numberUsed);
}

int main( )
{
cout << "This program sorts numbers from lowest to highest.\n";
    int sampleArray[10], numberUsed;
    fillArray(sampleArray, 10, numberUsed);
    sort(sampleArray, numberUsed);
    cout << "In sorted order the numbers are:\n";
    for (int index = 0; index < numberUsed; index++)
        cout << sampleArray[index] << " ";
cout << endl;
    return 0;
}


//File mergesort.cpp: the merge sort realization of the Sorting pattern.
template <class T>
int split(T a[], int begin, int end)
{ 
    return ((begin + end)/2);
}

template <class T>
void join(T a[], int begin, int splitPt, int end)
{
    T *temp;
    int intervalSize = (end - begin);
    temp = new T[intervalSize];
    int nextLeft = begin; //index for first chunk
    int nextRight = splitPt; //index for second chunk
    int i = 0; //index for temp
    //Merge till one side is exhausted:
    while ((nextLeft < splitPt) && (nextRight < end))
    {
        if (a[nextLeft] < a[nextRight])
        {
            temp[i] = a[nextLeft];
            i++; nextLeft++;
        }
        else
        {
            temp[i] = a[nextRight];
            i++; nextRight++;
        }
    }
    while (nextLeft < splitPt)//Copy rest of left chunk, if any.
    {
        temp[i] = a[nextLeft];
        i++; nextLeft++;
    }
    while (nextRight < end) //Copy rest of right chunk, if any.
    {
        temp[i] = a[nextRight];
        i++; nextRight++;
    }
    for (i = 0; i < intervalSize; i++)
        a[begin + i] = temp[i];
}


void fillArray(int a[], int size, int& numberUsed)
{
    cout << "Enter up to " << size << " nonnegative whole numbers.\n"
         << "Mark the end of the list with a negative number.\n";
    int next, index = 0;
    cin >> next;
    while ((next >= 0) && (index < size))
    {
        a[index] = next;
        index++;
        cin >> next;
    }
    numberUsed = index;
}

Plz explain this with example : 3 2 6 9 4

THanks in advance.

[Gaminic]

Grab a pen and paper and do your own homework.

[hentaiw]

Dear sir,

1.This ain't my homework,I've never taken an official programming class.
2.If you don't have a better answer then go to somewhere else and spam.
3.I only ask for help after stuck for more than half an hour.
4.The problem is I can't see where it touches the last member.

I go with 6 9 4

split point is 9,plz just show the line that can reach the last number,here is 4.

[Gaminic]

On point 1: My comment was based on your topic yesterday, on the interpretation of BigO. A typical homework question as well. Especially when you said you "solved the problem" but didn't understand a small part, which was actually the core of the problem, I got the vibe that you were asking people to do your homework.

On point 3: Staring at code might not be sufficient. Try googling merge sort. Even Wikipedia has some very good articles on various sorting methods. Very often, it's much easier to work out an example based on pseudocode instead of real code [especially when it's coded in C++].

[hentaiw]

On point 1: The difference of language and curiosity.English is not my maternal lang, learning programming fully in English is harder for me,but I'm not weak and don't blame anyone for it. That thread is for curiosity, my book said I add up,but don't say when I have O(logn) and O(n^2).

On point 3 : Thanks for the tips.

[hentaiw]

Big-O notation based on assumption of upper-bounding , I took weight too much on precision,that's why.

[Gaminic]

Judging on my experience on this forum, most of the frequent posters aren't native english speakers (including myself). Reading Wiki pages on sorting algorithms is the perfect learning opportunity!

[hentaiw]

Yes, thank you. But if I don't stare at the code,how can I continue reading my book ?

Also I determined what the problem is...for this recursive.

It uses the index more than the index of the last element,not the index of the last...puff...nice.

I can continue now.