Sorting Algorithm to Rearrange Zeros at End - Help Needed

[p1ayaone1]

I just wrote a big long post on this algorithm I'm working on to solve the determinant of an nxn matrix, but I got booted before I could post so it's all gone! I'm brand new to this forum.

As I was writing, I solved most of the problem, but I'm still stuck with a sorting algorithm that I can't work out.

0 3 2 0 8 4 7 0 9 0

should be sorted so that all the zeros come at the end. I would like to (but don't absolutely *need* to) preserve the order of the nonzero numbers:

3 2 8 4 7 9 0 0 0 0

The rub is that the first element (and last) is allowed to be zero. Is there some way I could avoid writing two algorithms?

if( first element is zero )
do a swap
else
so the sorting

And at that, how do you sort something like this? It doesn't look like there is a nice efficient way to do this, I have to pass over the list up to n^2 times:

loop over list or until all nonzero elements have been found
{
loop over list
{
find nonzero element that hasn't previously been found
find zero element
swap them if the nonzero element comes before the zero element
}
}

anyone got a better way to do this?

if someone wants to know more abt the determinant problem, let me know and I'll share in another thread

thanks

 

[davee123]

Seems like you can do this in O(n) time, since you're not really interested in sorting any of the non-zero numbers, and there's only one dealybob that you're effectively stripping off and putting at the end. Iterate through the list only once. Keep one index of where you are in the list, and one separate index of where you put the last non-zero item. Go from left-to-right and each time you come across a non-zero item at index1, copy it to the spot at index2, and then change index1's spot to a zero, increasing index2 when finished. Then, when index1 gets to the end of the list, just fill the remaining spots (everything from index2 to the end of the list) with 0's, and you should be all set.

DaveE

 

[p1ayaone1]

Thanks DaveE,

You're right that it's done on O(n) and about the two indices that I need to keep track of. If index1 is keeping track of the listwise iteration, then index2 will be that index with which I will swap. I do need to make sure that the element at index2 is nonzero, however, which requires a nested search of O(n-index1).

I can't give a copy of my code because it just won't make any sense (the "list" is acutally the ith column of an nxn matrix) but the stripped-down version is something like

for( int index1=0; index1<N;, index1++)
{
  int index2 = index1;
  if( list[index1] == 0 )
  {
    while( list[index2] == 0 )
    {
      index2++;
      if( index2 == N-1 )
        return;
    }
  list.swap(index1, index2);
  index2--;
}