Ruby array five_sort algorithm

Question

I'm trying to solve a problem called five_sort that accepts an array of integers as the argument and places all the fives at the end of the array and leaves all of the other numbers unsorted. For example, [1,2,5,3,2,5,5,7] would be sorted as [1,2,3,2,7,5,5,5].The rules for the problem state that only a while loops can be used and no other methods can be called on the array except [] and []=. Here is my current code:

def five_sort(array)
    sorted = false
    while sorted == false
    idx = 0

      while idx < array.length
        if array[idx] == 5
            array[idx], array[idx + 1] = array[idx + 1], array[idx]
        end
        idx += 1
      end
    sorted = true
    end
array
end

When running it, it is just in a continuous loop but I can't find out how to fix it. I know that if I just run the second while loop without the while sorted loop, the array would only run once and the fives would only switch places once and the loop would be over. But I don't know how to run the second while loop and stop it once all the fives are at the end.

Can anyone help me figure this one out?

Answer 1

Just a simple O(n) time and O(1) space solution, using a write-index and a read-index.

  w = r = 0
  while array[w]
    r += 1 while array[r] == 5
    array[w] = array[r] || 5
    w += 1
    r += 1
  end

Answer 2

While a couple of people have posted alternative approaches, which are all good, I wanted to post something based on your own code to reassure you that you had got pretty close to a solution.

I've added comments to explain the changes I've made:

def five_sort(array)
  sorted = false
  while sorted == false
    idx = 0
    # use did_swap to keep track of if we've needed to swap any numbers
    did_swap = false

    # check if next element is nil as alternative to using Array#length
    while array[idx + 1] != nil
      # it's only really a swap if the other entry is not also a 5
      if array[idx] == 5 and array[idx + 1] != 5
        array[idx], array[idx + 1] = array[idx + 1], array[idx]
        did_swap = true
      end
      idx += 1
    end

    # if we've been through the array without needing to make any swaps
    # then the list is sorted
    if !did_swap
      sorted = true
    end
  end
  array
end