I asked this question some time ago. Now I ended up with just a sorter method that will sort the items based on their bulkiness/nSlotsRequired. Here's what I'm doing:
- I store all the items I have in a one-dimensional array.
- Empty the bag.
- Sort the array.
- And start putting them back into the bag again.
Now, this is clearly not the best way to sort something, I mean, if I have an array I wouldn't just store its values somewhere else, empty it, sort the other array and then copy them back. Even if I had a 2D array, I would sort it by considering it a 1D array. 1st element's index is 0, 2nd is 1, 3rd is 2, 4th is 3, 5th is 4, etc.
General formula to convert from a 1D index to a 2D:
- row_index = _1D_index % nRows;
- col_index = _1D_index % nCols;
For example the 5th element has the 1D index of 4, to get the row: 4 % 3 = 1, to get the col, 4 % 4 = 0, so your element is at 1,0. What's the point of all this? Now you can just make a function
int GetAt(int index)
{
return array[index % nRows][index % nCols];
}
and something along the lines of:
void Swap(int index1, int index2)
{
int r1 = index1 % nRows;
int c1 = index1 % nCols;
int r2 = index2 % nRows;
int c2 = index2 % nCols;
int temp = array[r1][c1];
array[r1][c1] = array[r2][c2];
array[r2][c2] = temp;
}
But the problem is: 1- items take more than one slot. 2- Even if I were to just swap them in a way that they're sorted, they still have to get to their positions, I mean, the biggest one would go to the top left, beside it is the smaller, etc.
Taking notice that:
- I already have an array of the items' indices/places in the bag, so I don't have to look for them.
- I have an array of the available slots in the bag, that way I don't have to go through all of them to find where items fit. I just start from the next available slot placing the items (I update those arrays everytime I add/remove an item)
is there a more efficient way of doing this? Can I just, sort the items right away without having to empty the bag, store them somewhere else, etc? - It would make more sense. I couldn't think of a way :/ Maybe sort only the items that needs sorting? Thanks for any help.
EDIT: Here's what I have so far (sorting feature @~9:00)