[Tutor] Array pointers

[Alan Gauld]

> > I want to move all the 1's move to the right, 1 index at a time,
> > preserving any spacing.
> 
> So you want to insert a zero at the front and delete the first 
> zero from the back? That doesn't require iterating over all 
> the entries just enough to find the first zero...

Playing with this for a bit gives me:

def shiftOnesRight(aList):
   try:
     aList.insert(0,0)
     index = -1
     while aList[index] != 0: index -= 1
     del(aList[index])
   except IndexError: pass
   return aList

Now the challenge is to figure out how often to shift.
We need to know when all the ones are at the end.
The answer comes from counting zeros in the initial list...

count = theList.count(0)     # iterates the whole list once
for n in range(count):
   theList = shiftOnesRight(theList)  # ~1/4 the list count times?

So the total effect is only O(count*len/4 + 1), which 
is better than O(len*len).

We should speed things up even more by caching the last index we 
reached between shifts and start there next time....

def shiftOnsRight(aList,index=-1)
   try:
     aList.insert(0,0)
     while aList[index] != 0: index -= 1
     del(aList[index])
   except IndexError: pass
   return index, aList

count = theList.count(0)
index = -1
for n in range(count):
      index, theList = shiftOnesRight(theList, index)

HTH,

Alan G.