0

I have an abstract base class (Comparable) with Date and Time virtually inheriting from it and a DateTime class v-inheriting from Date and Time.

My problem is this: I was tasked with dynamically allocating an array of Comparables.

Comparable ** compArray;
compArray = new Comparable *[n]; // where n is user specified number of elements

I then populate the array with DateTimes in alternating order. I need to sort this array using a quicksort and bubblesort combination. Bubble if length < 8. Comparable** from and Comparable ** to are the only parameters I'm allowed to use.

But I'm completely stuck. At this point it isn't worth pasting in the code I have due to it's frantic haphazardness.

Any help would be greatly appreciated. I've spent the past few hours trying to finish this up, only have sorting left in my project. Which is due tomorrow late morning.

Thanks in advance, Joel

EDIT:

  void Sort(Comparable** a);
  void quicksort(Comparable** from, Comparable** to);   
  Comparable** partition(Comparable** from, Comparable** to);
  void Swap(Comparable** from, Comparable** to);    
  void safeRead(istream& sin, Comparable* d, const char* prompt);
  void printArray(ostream & sout, Comparable **a, int size);

I was given the above to use as my arraySort.h

I'm using: int aSize = _msize(a) / sizeof(Comparable) - 1; as my length variable... which I have to calculate instead of passing it, which is kind of annoying.

I'm mainly just having headaches over dereferencing the ** and calling it's lessThan or equals method in quicksort. Once I understand how to do a quicksort with it'll 'click' and I'll be able to easily to bubble sort.

EDIT: I currently have the following as my bubble sort, it doesn't sort the array at all.

  void Swap(Comparable** from, Comparable** to)
  {
    Comparable** tmp;

    tmp = from;
    **from = **to;
    to = tmp;

  }

  void bubbleSort(Comparable** a, int size)
  {

    int i, j;

      for (i=0; i<size-1; i++)
      {
        for (j= size - 1; j > i; j--)
          if(a[j]->lessThan(*a[j-1]))
            Swap(&a[j], &a[j-1]);

      }
  }
4

4 に答える 4

2

DateTime オブジェクトを作成する必要がないように、日付と時刻を交互に使用する必要がありますね。

インプレース配列をソートしていることを思い出してください。From と to は、STL コンテナーの begin() と end() の部分に似ています。

void QuickSort(Comparable** from, Comparable** to)
{
    int n = to - from;
    if (n < 8) BubbleSort(from, to);
    else {
        // the trick in here is remembering you have to sort in pairs
    }
}

Comparable** array = new Comparable*[n];
for (int i = 0; i < n; i += 2) {
    array[i] = new Date();
    array[i+1] = new Time();
}

// sort it
QuickSort(array, array+n);
于 2009-10-16T01:02:06.517 に答える
1

Comparable**fromとComparable**toは、私が使用できる唯一のパラメーターです。

サイズパラメータを持つ方が優れたAPIになるため、これは少しばかげています。

とにかく、1つの回避策（許可されているかどうかはわかりません）は、Cが文字列に対して行うことを実行することです。つまり、配列を割り当てるときに必要な要素よりも1つ大きくし、最後の要素をゼロ（null）にして、配列の終わりをマークします（これにより、呼び出し先はnullポインターを探して、配列の終わりを見つけることができます）。

于 2009-10-16T00:35:21.270 に答える
1

クラスの演算子「<」をオーバーロードして、2 つのクラスを比較してソートできるようにする必要があります。その後、バブルソートとクイックソートを実装するだけです。これは非常に簡単なことです (Google で多くの説明とサンプル コードを見つけることができます)。多分私はあなたの問題が何であるかを正確に理解していなかったので、これが役に立たない場合はもっと明確にしてください:)

于 2009-10-16T00:48:36.790 に答える
1

次の行に注意してください。

Comparable ** compArray = new Comparable *[n];

... ポインターの配列を割り当てています。実際のオブジェクトを割り当てていません。したがって、上記の配列を割り当てた後に次に行うことは、compArray 内の各ポインターを有効なオブジェクトを指すように設定することです。(それぞれに対して new を呼び出してそれらを設定するか、別の場所にある既存のオブジェクトを指すようにポインターを設定するかは、もちろんあなた次第です)

これが完了したと仮定すると、おそらく次のことは、2 つのポインターが指すものに基づいてそれらを比較する IsLessThan() 関数を作成することです。

bool IsLessThan(const Comparable * a, const Comparable * b) {return (*a) < (*b);}

上記は、ポインター自体の比較とは大きく異なることに注意してください。

その後の次のステップは、配列をソートする BubbleSort 関数を作成することです。次のようになります。

 void BubbleSort(Comparable ** ptrArray, int arrayLen)
 {
    [... bubble sort routine would go here ...]
 }

...そして、配列内のポインターを繰り返し反復することができ、間違った順序の隣接するポインターのペアが見つかるたびに (つまり、IsLessThan(ptrArray[i], ptrArray[i+1]) == false )、ポインターを交換します。ポインターをまったく交換することなく配列のパス全体を通過すると、完了したことがわかり、関数を返すことができます。

これが正しく機能するようになったら (もちろん非効率ですが、問題ありません)、最後のステップは QuickSort ルーチンを作成することです。

 void QuickSort(Comparable ** ptrArray, int arrayLen)
 {
    if (arrayLen < 8) BubbleSort(ptrArray, arrayLen);
    else
    {
        [... quick sort routine would go here ...]
    }
 }

QuickSort については、ここで説明できるほどよく覚えていませんが、上記の方法で、少なくともほとんどの課題を解決できることを願っています。

于 2009-10-16T00:50:18.333 に答える