Forum: Ruby Sorting Algorithm

The basic idea behind this is to have 3 arrays.
the first one is the original unsorted array.
the second one will be the final sorted array
and the third one will be kind of a compliment.

a comparison of the first object (in this case words/letters) will be
done with
all of the other objects and if it is the "smallest" object, it will be
pushed into the sorted array. if it is compared with an object and it is
"bigger" than that object, it is pushed into the compliment array. when
an object is pushed into the sorted array, the original unsorted array
will become empty and the compliment array will be equated to the
unsorted array and this repeats itself until all the objects have been
dealt with. I'll paste the code but I'm having issues because I get a
bizarre sorted array. Please tell me what's wrong or what I can do to
fix it. I do not want to use the bubble sort though.

---------------------------------------------------------------
>#original unsorted array
array = ['a','b','c','d']

>#final sorted array
sortedarray = []

>#compliment array
unsortedarray = []

>#placeholder for length comparison
placeholder = array

x=0
y=1

>#this while block makes sure that the length of the sorted
>#array is equal to the length of the original array

while sortedarray.length != placeholder.length
>    #this while block makes sure that every element is
>    #compared, and no object is the 'smallest' twice.

    while y != array.length
        if array[x] < array[y]
            unsortedarray.push array[y]
            y=y+1
        else
            unsortedarray.push array[x]
            x=y
            y=y+1
        end
    end

>#erase the original array and replace it with the new unsorted array
  sortedarray.push array[x]
  array = []
  array.push unsortedarray[0..unsortedarray.length]
  y=1
  x=0
end

puts sortedarray
---------------------------------------------------------------

when this program runs, I expected the same original array to be
printed, then I'll go ahead to test it with mixed arrangements... but it
didn't turn out well... what did I do wrong or what should I try?

Hi,

There are two errors in your code. First, the line

array.push unsortedarray[0..unsortedarray.length]

does not what you expect. It does not append the elements of
"unsortedarray" to "array" but rather "unsortedarray" itself. So after
the first run of the inner while loop you end up with array == [['a',
'b', 'c', 'd']]. And this will break your algorithm.

Since you want the *elements* appended, you have to unpack
"unsortedarray" first:

array.push *unsortedarray

However, this is a very complicated and inefficient solution in the
first place. Why not simply make "array" a reference to "unsortedarray"?

array = unsortedarray

Arrays are no physical objects, you don't have to actually empty and
refill them. Simply overwrite the reference.

The second error is that you forgot to reset "unsortedarray":

unsortedarray = []

I thinks that's all.

However, you should replace the placeholder with the actual length of
the original array. Imagine "array" as having many billions of entries.
It would be insane to store the whole array in memory just for its
length.

And you should replace array[x] < array[y] with array[x] <= array[y].
This will make the algorithm stable (entries with the same search key
will remain in their original order).

Your code is actually similar to Selection Sort. I assume you're doing 
this as an exercise? Because if you really want to sort arrays, you 
should always use the built-in algorithms. Those are much faster and 
much more reliable than any self designed algorithm.

Thanks for the explanations. very extensive and I appreciate and 
acknowledge your effort, I learned something new :). Indeed it is an 
exercise, I'm supposed to create a sorting program and there's a 
suggested algorithm which I don't seem to get my head around but since 
they want the array sorted, I came up with this.

Jan E. wrote in post #1051969:
> array.push unsortedarray[0..unsortedarray.length]
>
> does not what you expect. It does not append the elements of
> "unsortedarray" to "array" but rather "unsortedarray" itself. So after
> the first run of the inner while loop you end up with array == [['a',
> 'b', 'c', 'd']]. And this will break your algorithm.
>
> Since you want the *elements* appended, you have to unpack
> "unsortedarray" first:
>
> array.push *unsortedarray

Another variant to achieve this without unpacking uses Array#concat:

array.concat unsortedarray

Kind regards

robert