Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Merge sort not sorting at all despite copying it exact from book.

  1. #1
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Question Merge sort not sorting at all despite copying it exact from book.

    It seems one of my mergesorts isn't sorting at all, not to mention two of my three quicksorts.

            #ifndef _SORTS_H_
            #define _SORTS_H_
            #include <stdlib.h>
            #include <time.h>
            #include <vector>
            using namespace std;
     
     
            class Sorts
            {
             public:
     
              template <class T>
              static void merge_sort(T *array, int size );
     
              private:
     
                  template<class T>
                  static void merge_sort(T *array, T *tmpArray, int left, int right)
                  {
                         if (left < right)
                         {
                                int center = (left+right)/2;
                                merge_sort(array, tmpArray, left, center);
                                merge_sort(array, tmpArray, center+1, right);
                                merge(array, tmpArray, left, center+1, right);  
                                  }
                         }
     
                         template<class T>
                         static void merge(T *array, T *tmpArray, int leftPos, int rightPos, int rightEnd)
                         {
                                int leftEnd = rightPos -1;
                                int tmpPos = leftPos;
                                int numElements = rightEnd - leftPos + 1;
     
                                while(leftPos <= leftEnd && rightPos <= rightEnd)
     
                                if(array[leftPos] <= array[rightPos])
                                tmpArray[tmpPos++] = array[leftPos++];
                                else 
                                tmpArray[tmpPos++] = array[rightPos++];
     
                                while(leftPos <= leftEnd)
                                tmpArray[tmpPos++] = array[leftPos++];
     
                                while(rightPos <= rightEnd)
                                tmpArray[tmpPos++] = array[rightPos++];
     
                                for (int i =0; i < numElements; i++, rightEnd--)
                                array[rightEnd] = tmpArray[rightEnd];
     
                                }
     
     
        };
     
        template <class T>
          void Sorts::merge_sort(T *array, int size)
          {
                 T *tmpArray = new T[size];
                 merge_sort(array, tmpArray, 0, size -1);
                 }
     
        #endif

    I know the following code won't actually run without the arguments but you can simply delete that part and replace it with a cin and import that instead.

    #include "Sorts.h"
    #include <iostream>
    #include <fstream>
    using namespace std;
    #include <time.h>
     
    int main(int argc,char *argv[])
    {
      if (argc!=2)
      { 
        cout <<"Please enter file name."<<endl;
        return -1;
      }
      double *array;
      int length;
     
     
      fstream fin;
     
      fin.open(argv[1]);
      if (!fin.is_open())
      {
        cout <<"Could not open file"<<endl;
        return -1;
      }
     
      fin >>length;
      array = new double[length];
      for (int i=0;i<length;i++)
        fin >> array[i];
     
     
    double *clone1;
     
     
    clone1 = new double[length];
     
     
     
    for (int i =0; i < length; i++)
    {
    clone1[i] = array[i];
     
    }
     
     
     
      delete []array;
     
     
     double time_taken2=0;
    Sorts s2;
      clock_t tinitial2 = clock(); //the initial time
     
     // Sorts::insertion_sort(array,length);
        Sorts::merge_sort(array, length);
       // Sorts::quicksort_simple(array, 0, length - 1);
     // Sorts::quicksort_median3(array, length);
    // Sorts::quicksort_naive(array, 0, length -1);
     
      clock_t tfinal2 = clock(); //the final time
      time_taken2 = tfinal2-tinitial2; //the difference, this is still in "clock ticks"
      /*
        The resolution of the above clock is about 15 msec., which means that it cannot measure times smaller than 15 msec.
        If the thing you want to measure finishes before that time, the only resort is to do the operation several times, take the total time and take the average
      */
     
     
     
      if (time_taken2==0)  //operation was too fast for this clock, take average
      {
     
        time_taken2 = 0;
        double * tmparray = new double[length];	
        for (int i=0;i<10;i++)
        {	
          //to take true average we run the same algorithm on the same input every time
          /*
    	if you sort the original array, all subsequent sorts will be on an 
    	already sorted array, which will spoil the average. This is because 
    	we know that insertion sort times vary hugely from worst to best case
          */
          for (int j=0;j<length;j++)
    	tmparray[j] = clone1[j]; //create same temporary array again
          tinitial2 = clock(); //take initial time here so that temporary array time is not counted
          Sorts::merge_sort(tmparray,length);
          tfinal2 = clock(); //take final time
          time_taken2 += (tfinal2-tinitial2);
        }
        time_taken2 /=10; //average
        delete []tmparray;
      }
      time_taken2 = 1000.0*time_taken2/CLOCKS_PER_SEC; //conversion to milliseconds
      cout << "Time taken(merge sort): "<<time_taken2<< "msec."<<endl;
     
    for (int i = 0; i < 500; i++)
    {
    cout <<clone1[i];
    }
     
    delete[] clone1;
     
    }


    I'm wondering if it's the fact that the book used a vector and I'm using an array.

    Is it my size value that is messing it up?

    The array "array" was there because normally I'm using that array on a function and then copying that array, before it's sorted, four times and using the other four functions with those.


  2. #2
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Merge sort not sorting at all despite copying it exact from book.

    I was able to solve the problem.

    Please put thread to sleep. Ha ha!

    System.out.println("Thread can be closed now.");
    Thread.sleep(Infinity);

Similar Threads

  1. how to merge java objects with effective dates
    By java4ulok in forum What's Wrong With My Code?
    Replies: 4
    Last Post: June 10th, 2011, 01:24 PM
  2. Sliding puzzle Restart button(same exact game)
    By carterb32 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: April 21st, 2011, 04:29 AM
  3. bubble sort and selection sort on strings
    By Sir Saula in forum What's Wrong With My Code?
    Replies: 5
    Last Post: July 3rd, 2010, 09:44 AM
  4. how to merge my OO with GUI
    By zyspt in forum AWT / Java Swing
    Replies: 1
    Last Post: May 18th, 2010, 03:28 PM
  5. Merge 2 Sorted Text Files into a Third
    By Epyllion in forum What's Wrong With My Code?
    Replies: 0
    Last Post: February 10th, 2010, 08:24 PM