Desperately Need Help with Defragmentation(QuickSort) Algorithm

[TheJokerV]

Basically our problem was to create a defragmentation algorithm to defragment an array of integers between 0 and 99. We were given a disk class which is basically a vector with a move function(this is our only means of moving array elements around). Each element of the array is an integer which represents a file system space. 0 means the space is empty, 1 means the its a system file and unmovable, and 2 to 99 are files(integers of the same number are all part of the same file) which are movable which the move function. A description of the move function is available in the frag.h file.

So the disk is initialized and each element is filled with random numbers and you have to defragment the disk(vector). This is basically a sorting problem where you have to sort like number elements together. In the defrag.cpp is my QuickSort algorithm. It works ...sometimes. The disk size is declared in the main function(in main.cpp) where you declare your disk object. If the disk size is 250, 3000, or 100000 the algorithm works and the disk is defragmented. If the disk size is 90, 150, 130000, I get a stack overflow error which would suggest an infinite recursion. I can't figure out what the pattern is. For some numbers it works, for some numbers I get the stack overflow error (I'm using Visual Studio 2008 BTW).

I would greatly appreciate it if someone could show me the error of my ways. Thank You in advance. I've copied the 4 files below. Thanks for helping.

P.S. The defrag algorithm is in the defrag.cpp and that is the only thing which I am allowed to change.

main.cpp

// A SAMPLE MAIN FILE

#include <iostream>
#include "frag.h"
using namespace std;

void defragment(frag &disk);

int main() {
  frag foo(100000); //How big you want the disk to be, 
  cout << "Before defrag: ";
  cout << foo.print() << ": fragIndex=" <<  foo.fragIndex() << "\n\n" << endl;
  defragment(foo);
  cout << "After defrag: ";
  cout << foo.print() << ": fragIndex=" <<  foo.fragIndex() << endl;
}

frag.h

#ifndef FRAG
#define FRAG

#include <string>
#include <vector>

using namespace std;

class frag {
  /* Maintains an array of IDs.  Array location "index" has ID "foo" (between 0 and 101)
  ** if the "foo"-th resource owns storage location "index".  For example, in the context of
  ** a hard disk, index could be a hard disk location and ID represents a particular file.
  **
  ** Note that an ID of 0 corresponds to an empty (unused) location.
  **       and an ID of 1 correspondes to an unmovable system resource
  */

 public:
  // CONSTANTS
  static const int EMPTY = 0;     // denotes an empty cell
  static const int SYSTEM = 1;    // denotes a system-owned cell that cannot be moved
  static const int NUM_IDS = 100; // total # of different IDs (including 0 and 1)

  // CONSTRUCTOR
  frag(int size=300000, int seed=0);
  /* %R:  size > 1
  ** %E:  Establishes an array of "size" cells, the first fraction of which are
  **      populated with random IDs based on the pseudorandom seed "seed", and
  **      the remaining are initially empty.
  */


  // MANIPULATIVES
  int move(int startIndex, int endIndex);
  /* %R:  0 < startIndex != endIndex < storageSize
  ** %M:  changes the storage array
  ** %E:  moves cell at index startIndex to cell at index endIndex, if possible
  **      This will not be possible if:
  **      1.  The cell at the endIndex is not empty
  **      2.  The cell at the start index is empty (ID=EMPTY) or a system resource (ID=SYSTEM)
  **      Returns true iff the move was successful
  ** %X:  assume the array containts [1 2 2 2 3 0 0]
  **      - move(0,5) would return true and result in   [0 2 2 2 3 1 0]
  **      - move(1,4) would return false because the end location is not empty
  */

  // QUERY
  const int size() { return storage->size(); }
  /* %E:  returns the size of the storage array
   */

  const int operator[](int index);
  /* %R:  0 < index < storageSize (no check is made!)
  ** %E:  returns the index-th item of the storage array
  */

  float fragIndex();
  /* %E:  Computes the fragmentation index of the storage array.
  **      This is defined to be the number of changes in index divided
  **      by the number of indices (i.e. the average # of changes / index).
  ** %X:  If the array contains [1 2 2 2 0], there are 2 changes
  **      (1->2 and 2->0) divided by 5 indices, giving an index of 0.4.
  */

  string print();             // display the fragmentations in a human-readable manner

 private:
  vector<int> *storage;       // the location with storage ids are kept
};
#endif

frag.cpp

#include "frag.h"

#include <cstdlib>
#include <cmath>

frag::frag(int size, int seed) {
  /* %E:  populates the storage item in a consistent manner.  Id 0 corresponds to an empty cell. */
  // initialization
  int fraction = (9*size)/10;
  srand(seed);
  storage = new vector<int>(size); // set up the initial vector

  int ii;
  for (ii=0; ii<fraction; ii++) {
    (*storage)[ii]=(NUM_IDS-1)*abs(sin((double) rand()))+1; // returns a biased number 1 ... NUM_IDS-1
  }
  for (ii=fraction; ii<size; ii++)
    (*storage)[ii]=0;
}

int frag::move(int startIndex, int endIndex) {
  /* %R:  0 < startIndex != endIndex < storageSize
  ** %M:  changes the storage array
  ** %E:  moves cell at index startIndex to cell at index endIndex, if possible
  **      This will not be possible if:
  **      1.  The cell at the endIndex is not empty
  **      2.  The cell at the start index is a system resource (ID=SYSTEM)
  **      Returns true iff the move was successful
  ** %X:  assume the array containts [1 2 2 2 3 0 0]
  **      - move(0,5) would return true and result in   [0 2 2 2 3 1 0]
  **      - move(0,4) would return false because the end location is not empty
  */

  if ((*storage)[endIndex]!=EMPTY ||
      (*storage)[startIndex]==SYSTEM ||
      (*storage)[startIndex]==EMPTY)
    return false; // i.e. the move failed
  else {
    // effect the move
    (*storage)[endIndex] = (*storage)[startIndex];
    (*storage)[startIndex] = EMPTY;

    return true; // i.e. the move was successful
  }
}

string frag::print() {
  // display the fragmentations in a human-readable manner
  string result = "";
  for (int ii=0; ii<storage->size(); ii++) {
    char tmp[5];
    sprintf(tmp,"%d",(*storage)[ii]);
    result+= tmp;
    result+= " ";
  }
  return result;
}

float frag::fragIndex() {
  /* %E:  Computes the fragmentation index of the storage array.
  **      This is defined to be the number of changes in index divided
  **      by the number of indices (i.e. the average # of changes / index).
  ** %X:  If the array contains [1 2 2 2 0], there are 2 changes
  **      (1->2 and 2->0) divided by 5 indices, giving an index of 0.4.
  */

  int changes=0;
  int storageSize = storage->size();

  for (int ii=1; ii<storageSize; ii++)
    changes+=((*storage)[ii]!=(*storage)[ii-1]);
  return (float) changes/storageSize;
}

const int frag::operator[](int index) {
  /* %R:  0 < index < storageSize (no check is made!)
  ** %E:  returns the index-th item of the storage array
  */

  return (*storage)[index];
}

defrag.cpp

#include "frag.h"
#include <iostream>

void QuickSort(frag &disk, int p, int r);

void defragment(frag &disk) {
	for(int i = 0; i < disk.size(); i++){
		if(disk[i] == 0){
			disk.move(0, i);
			break;
		}
	}
	QuickSort(disk, 0, disk.size()-1);
}

void QuickSort(frag &disk, int p, int r){
	bool oneFile = true;
	int ii, jj;
	int rr = r+1;
	int pivotval;

	for(int i = p+1; i < r+1; i++){
		if((disk[i] != disk[p])&&(disk[i] != 1)){
			oneFile = false;
			break;                              //Checks if only one file is in the partition
		}
	}
	if(oneFile == false){                       //If there is more than one file in the partition
			pivotval = disk[r];
			ii = p-1;
			for(jj = p; jj < r+1; jj++){
				if((disk[jj] <= pivotval)&&(disk[jj] != 1)){
					do{
						ii++;
					}while(disk[ii] == 1);
					disk.move(ii, 0);
					disk.move(jj, ii);
					disk.move(0, jj);
				}
			}

		QuickSort(disk,p,ii-1);
		QuickSort(disk, ii+1, r);
	}

	
	
/*	if(oneFile == false){                       //If there is more than one file in the partition
		do{
			rr--;
			pivotval = disk[rr];
			ii = p-1;
			for(jj = p; jj < r+1; jj++){
				if((disk[jj] <= pivotval)&&(disk[jj] != 1)){
					do{
						ii++;
					}while(disk[ii] == 1);
					disk.move(ii, 0);
					disk.move(jj, ii);
					disk.move(0, jj);
				}
			}
		}while(ii == r);

		QuickSort(disk,p,ii);
		QuickSort(disk, ii+1, r);
	}*/
}

 

[mikeblas]

Why are you using quick sort? The problem you describe would be solvable in O without sorting, using less time.

It would probably help if you provided a data set that caused your stack overflow, as the problem isn't jumping out in static analysis.

In fact, I'm a little puzzled by the code you've got. degragment() seems like it wants to find all the sectors that are marked zero, which I guess is not in use. For any that are found, you move sector #0 into the empty sector. Why is that?

For all the anal-retentive comments, there's bugs in frag.h. For example, the comments say that you can't call disk::move(a, b) with a == b. But your code at the beginning of defragment() will do just that.

Another obvious bug is that frag:rint() uses a buffer that's too small. I think you'll have numbers larger than four digits in the array you're dumping; so chra tmp[] is too small.

Your QuickSort() implementation isn't quite right. You're not checking (or even asserting) a termination condition, other than the one-file idea. This means you'd have to permute every area to make sure it was only one file -- not just that it was in-order. What happens to the one file test when QuickSort(a, b) is called with a =b ? That is, with a partition length of zero?

You can also run off the maximum of the array, I think, because of the way you set up rr and do the second call.