I've written a flexible quicksort module capable of taking a vector reference pass, cloning it, altering the clone and swapping with the original to print the list. For the most part, this works wonderfully, except for one thing.

Occasionally, it gets numbers wrong. Not all the time. If I give it five random elements (Between 1 and 100) and tell it to sort, around the sixth time I ran it it'd have a number wrong. If I gave it 5000 elements and ran it, it'd have quite a few wrong. I've stepped through the program by hand, writing down the changes on paper step by step, and can't find the error. Mind giving me a hand?

$ cat -n quicksort.cpp
     1
     2  #include <iostream>
     3  #include <vector>
     4  using namespace std;
     5  /*
     6  The quick-sort  algorithm is fairly simple. I've set up this module to be passed a vector reference, where it will act directly upon the vector rather than having to pass information back and forth to the calling class. There are two ends, L and R, which correspond to the ends of the vector and can move accordingly to shrink the line being worked on. Each time it does, a new mid-point is determined, and the process continued again. This module is designed to be flexible, and can handle any sized (Float) vector.
     7
     8  */
     9
    10  void QuickSort(vector<float>* RawData, int Begin, int End) // The overloaded version of QuickSort, designed for re-parameterization.
    11  {
    12
    13          int Low;  // The left end.
    14          int High; // The right end.
    15          int Pole; // The pivot.
    16          int Size=RawData->size(); // Get the size of the vector to be altered.
    17          vector<float> DataRestructure(Size); //A new vector is called up to receive the incoming data off of the pointer
    18          DataRestructure=*RawData; // The copy is made.
    19          Low=Begin;
    20          High=End;
    21          Pole=(High+Low)/2;
    22          // Intial Parameters are set.
    23
    24           do // Continue so long as Low and High haven't traded places and crossed each other over the pole. This is where the Cross happens, Low and High moving past each other.
    25          {
    26                  while (DataRestructure[Low] < DataRestructure[Pole]) // Move towards Pole until find a number out of place.
    27                  {
    28                          Low++;  // Bump bump.
    29                  }
    30                  while (DataRestructure[High]>DataRestructure[Pole]) // Move towards Pole until find a number out of place.
    31                  {
    32                          High--; // Dump dump.
    33                  }
    34                  if (Low<=High) // So long as they haven't crossed yet, swap the results of the above two bumps and dumps.
    35                  {
    36
    37  cout << DataRestructure[High] << " - " << DataRestructure[Low] << " to be swapped - " << endl;
    38                          swap(DataRestructure[High],DataRestructure[Low]);
    39  cout << DataRestructure[High] << " - " << DataRestructure[Low] << " has been swapped - DONE" << endl << endl;
    40                          High--;
    41                          Low++;
    42                  }
    43          } while (Low<=High);
    44          if (Begin < High) // Are there still things below High after the cross? If so, drop and keep repeating.
    45          {
    46
    47  cout << " Begin < High " << endl;
    48                  QuickSort(&DataRestructure, Begin, High);
    49          }
    50          if (Low < End) // Are there still things above Low after the cross? If so, bounce up and keep repeating.
    51          {
    52  cout << " Low < End " << endl;
    53                  QuickSort(&DataRestructure, Low, End);
    54          }
    55
    56          RawData->swap(DataRestructure); // Return the sorted vector back to the origin.
    57  }
    58
    59  void QuickSort(vector<float>* RawData) // Takes the pointer reference to the vector to be sorted, rather than passing the entire vector back and forth. This version is overloaded to accept the re-parameters.
    60  {
    61
    62          int Begin; // The left most end.
    63          int End; //  The right most end.
    64          int Low;  // The left end.
    65          int High; // The right end.
    66          int Pole; // The pivot.
    67          int Temp; // The number holder.
    68          int Size=RawData->size(); // Get the size of the vector to be altered.
    69  //--------------------------------------------------------------------------------------
    70  //      int TEST=0; // TESTER
    71  //----------------------------------------------------------------------------------------
    72          vector<float> DataRestructure(Size); //A new vector is called up to receive the incoming data off of the pointer
    73          DataRestructure=*RawData; // The copy is made.
    74          Begin=0;
    75          End=Size-1;
    76          Low=Begin;
    77          High=End;
    78          Pole=(Low+High)/2;
    79          // Intial Parameters are set.
    80           do  // Continue so long as Low and High haven't traded places and crossed each other over the pole. This is where the Cross happens, Low and High moving past each other.
    81          {
    82  //-----------------------------------------------------------------------------------------------
    83  //              TEST++;
    84  //----------------------------------------------------------------------------------------------
    85
    86                  while (DataRestructure[Low] < DataRestructure[Pole]) // Move towards Pole until find a number out of place.
    87                  {
    88                          Low++;  // Bump bump.
    89
    90                  }
    91                  while (DataRestructure[High]>DataRestructure[Pole]) // Move towards Pole until find a number out of place.
    92                  {
    93                          High--; // Dump dump.
    94
    95                  }
    96                  if (Low<=High) // So long as they haven't crossed yet, swap the results of the above two bumps and dumps.
    97                  {
    98
    99  cout << DataRestructure[High] << " - " << DataRestructure[Low] << " to be swapped - " << endl;
   100                          swap(DataRestructure[High],DataRestructure[Low]);
   101  cout << DataRestructure[High] << " - " << DataRestructure[Low] << " has been swapped - DONE" << endl << endl;
   102                          High--;
   103                          Low++;
   104                  }
   105          } while (Low<=High);
   106          if (Begin < High) // Are there still things below High after the cross? If so, drop and keep repeating.
   107          {
   108  cout << " Begin < High " << endl;
   109                  QuickSort(&DataRestructure, Begin, High);
   110          }
   111          if (Low < End) // Are there still things above Low after the cross? If so, bounce up and keep repeating.
   112          {
   113  cout << " Low < End " << endl;
   114                  QuickSort(&DataRestructure, Low, End);
   115          }
   116
   117          RawData->swap(DataRestructure); // Return the sorted vector back to the origin.
   118  }
   119
   120
   121  #if __INCLUDE_LEVEL__ < 1
   122
   123  #include <iostream>
   124  #include <vector>
   125  using namespace std;
   126  /*
   127  This entire section is devoted to testing the flexible module above.
   128  */
   129  int main()
   130  {
   131          int SizeOfThread=20; // Determines how big the test thread will be.
   132          srand((unsigned)time(0)); // Seeding random number generator.
   133          vector<float> test(SizeOfThread);
   134          for (int i=0; i<SizeOfThread; i++)
   135          {
   136                  test[i]=rand()%100+1;
   137          }
   138          cout << "Before the de-scramble: " << endl;
   139          for (int i=0;i<SizeOfThread;i++)
   140          {
   141                  cout << test[i] << endl;
   142          }
   143          QuickSort(&test);
   144
   145          cout << "After de-scrambler:"  <<  endl;
   146          for (int i=0;i<SizeOfThread;i++)
   147          {
   148          cout << test[i] <<endl;
   149          }
   150          return 0;
   151  }
   152
   153  #endif

So. Where is my reiteration ending too quickly? I did a 'quicksort' search through the forum menu, but didn't really find anything like what I was seeing.

So eh... when you're calling your deal here

QuickSort(&test);

with your 20 element (size)

and then you're doing this

int Low;  // The left end.
int High; // The right end.
int Pole; // The pivot.
...

int Size=RawData->size(); // Get the size of the vector to be altered.

vector<float> DataRestructure(Size); //A new vector is called up to receive the incoming data off of the pointer
Begin=0;
End=Size-1;
Low=Begin;
High=End;
Pole=(Low+High)/2;

You're setting High to End, which is Size-1, which is 20 - 1

Then you're calling Pole = ( 0 + 19 ) / 2 ... thats 9.5

Then you're checking for DataRestructure[Pole] ... which in this case is DataRestructure[9.5] and theres no such animal

I don't know if thats your problem but thats something that I've noticed

I actually checked that earlier. The type is int for Pole, it just drops the decimal point. 9.5 becomes 9. I thought the same thing, but a couple of echoes written in proved it.

Found the error, it's working like a charm now. I removed the overload, and instead started passing the reference in the constructor, along with the number 0 and the thread size - 1. Then let it loop on itself. I also changed Pole to be float, and made it represent the actual number inside of DataRestructure[(Low+High)/2] rather than being a position in and of itself. That, and I put a semi-colon at the end of While, and removed the do loop.

And it seems to work fine after that little clean-up? Up to twenty thousand integers so far, ran them through a seperate shell-sort that I've already proven, and a seperate bubble-sort that I've already proven, and no swaps made. Ran through by hand via page-down on the output page, and didn't spot anything out of order. Still wish I knew how that made a difference.

This article has been dead for over six months. Start a new discussion instead.