By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,855 Members | 1,934 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,855 IT Pros & Developers. It's quick & easy.

array random sort

P: n/a
gl
How do I take an array or arraylist, and sort it randomly? Like suppose the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.
Nov 17 '05 #1
Share this Question
Share on Google+
9 Replies


P: n/a

"gl" <gl@discussions.microsoft.com> wrote in message
news:7E**********************************@microsof t.com...
How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.

public static List<T> shuffledList(List<T> listToShuffle)
{
/*
* Make a new list of elements picked from listToShuffle
* in a random order.
*/

List<int> ints = new List<int>(listToShuffle.Count); //0, 1,
2, ...
for (int i = 0; i < listToShuffle.Count; i++)
ints.Add(i);

List<T> randList = new List<T>(listToShuffle.Capacity);

for (int k = 0; k < listToShuffle.Count; k++)
{
int randIndx = Common.rand.Next(ints.Count); //random
from 0, 2, .. not already picked
int randK = ints[randIndx];
randList.Add(listToShuffle[randK]);
ints.RemoveAt(randIndx);
}

return randList;
}
Nov 17 '05 #2

P: n/a

"gl" <gl@discussions.microsoft.com> wrote in message
news:7E**********************************@microsof t.com...
How do I take an array or arraylist, and sort it randomly? Like suppose the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.


Sniff....Sniff....Smells like homework.

Search google groups for shuffle algorithm
You should find what you need

Good luck
Bill
Nov 17 '05 #3

P: n/a
I forgot to mention that Common.rand is an instance of Random, and is a
static member of class Common.

You can find this, and some other useful utilities, at
http://www.frontiernet.net/~fredm/dps/Contents.htm

"Fred Mellender" <no****************@frontiernet.net> wrote in message
news:3h*****************@news02.roc.ny...

"gl" <gl@discussions.microsoft.com> wrote in message
news:7E**********************************@microsof t.com...
How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or
array
lists sort method, but i'm not exactly sure how you do it.

public static List<T> shuffledList(List<T> listToShuffle)
{
/*
* Make a new list of elements picked from listToShuffle
* in a random order.
*/

List<int> ints = new List<int>(listToShuffle.Count); //0, 1,
2, ...
for (int i = 0; i < listToShuffle.Count; i++)
ints.Add(i);

List<T> randList = new List<T>(listToShuffle.Capacity);

for (int k = 0; k < listToShuffle.Count; k++)
{
int randIndx = Common.rand.Next(ints.Count); //random
from 0, 2, .. not already picked
int randK = ints[randIndx];
randList.Add(listToShuffle[randK]);
ints.RemoveAt(randIndx);
}

return randList;
}

Nov 17 '05 #4

P: n/a
gl
I'm using c# 1.1 so no generics. :(

"Fred Mellender" wrote:

"gl" <gl@discussions.microsoft.com> wrote in message
news:7E**********************************@microsof t.com...
How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.

public static List<T> shuffledList(List<T> listToShuffle)
{
/*
* Make a new list of elements picked from listToShuffle
* in a random order.
*/

List<int> ints = new List<int>(listToShuffle.Count); //0, 1,
2, ...
for (int i = 0; i < listToShuffle.Count; i++)
ints.Add(i);

List<T> randList = new List<T>(listToShuffle.Capacity);

for (int k = 0; k < listToShuffle.Count; k++)
{
int randIndx = Common.rand.Next(ints.Count); //random
from 0, 2, .. not already picked
int randK = ints[randIndx];
randList.Add(listToShuffle[randK]);
ints.RemoveAt(randIndx);
}

return randList;
}

Nov 17 '05 #5

P: n/a
gl
it's definitely not homework. hehe..i wish it was.

I'm basically pulling an array of rows from a dataset, and they have to get
put into a random order (so the same first 3 people don't get a certain value
everytime, it's randomized).

I can check google like you said though.

"Bill Butler" wrote:

"gl" <gl@discussions.microsoft.com> wrote in message
news:7E**********************************@microsof t.com...
How do I take an array or arraylist, and sort it randomly? Like suppose the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.


Sniff....Sniff....Smells like homework.

Search google groups for shuffle algorithm
You should find what you need

Good luck
Bill

Nov 17 '05 #6

P: n/a
"gl" <gl@discussions.microsoft.com> wrote in message
news:28**********************************@microsof t.com...
I'm using c# 1.1 so no generics. :(

"Fred Mellender" wrote:


So use ArrayList instead
Bill
Nov 17 '05 #7

P: n/a
Fred Mellender <no****************@frontiernet.net> wrote:

"gl" <gl@discussions.microsoft.com> wrote in message
news:7E**********************************@microsof t.com...
How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array
lists sort method, but i'm not exactly sure how you do it.


<snip>

Note that it's relatively easy to do this *without* creating two lists
(which Fred's solution does). You can shuffle within the list, by
having an imaginary dividing line between the "randomized" section and
the "unrandomized" section of the list. You start off considering
everything to be unrandomized, then pick a random element to be element
0, swapping it if necessary.

You then take a random element *other than 0*, and swap that into
position 1.

You then take a random element *other than 0 or 1* and swap that into
position 2, etc.

Here's some code which does that with an ArrayList:

public static void Shuffle (ArrayList al)
{
for (int i=0; i < al.Count; i++)
{
object x = al[i];

int index = rng.Next(al.Count-i)+i;
al[i]=al[index];
al[index]=x;
}
}

In each iteration, we're looking to set element i (which is currently
in the "unshuffled" section) to be a random element from the unshuffled
section. At that stage, it becomes part of the shuffled section.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
Nov 17 '05 #8

P: n/a
The problem with Fred's solution is that while it appears to be an O(n)
algorithm, RemoveAt itself is O(n), making the overall algorithm O(n^2). If
the input array get big, it's going to get very slow.

The trick is to avoid deleting anything. We're starting with an array
of N, and we finish with an array of N, so there's no reason to delete
anything. This version is really O(n):

// Shuffles inplace.
public static List<T> shuffleList(List<T> listToShuffle)
{
for (int k = listToShuffle.Count-1; k > 1; --k)
{
int randIndx = Common.rand.Next(k); //
T temp = listToShuffle[k];
listToShuffle[k] = listToShuffle[randIndx]; // move random num to
end of list.
listToShuffle[randIndx] = temp;
}
return listToShuffle;
}

So, say, for example, listToShuffle has 10 elements (0-9). First we pick a
random number between 0 & 8, and we swap the element at the position with
the element at position 9. Then we pick an number between 0 & 7, and swap
that element with [8]. And so on until we're pick a number between 0 & 1 and
swapping it with listToShuffle[2]
--
Truth,
James Curran
[erstwhile VC++ MVP]

Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com

"Fred Mellender" <no****************@frontiernet.net> wrote in message
news:3h*****************@news02.roc.ny...

"gl" <gl@discussions.microsoft.com> wrote in message
news:7E**********************************@microsof t.com...
How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or array lists sort method, but i'm not exactly sure how you do it.

public static List<T> shuffledList(List<T> listToShuffle)
{
/*
* Make a new list of elements picked from listToShuffle
* in a random order.
*/

List<int> ints = new List<int>(listToShuffle.Count); //0, 1,
2, ...
for (int i = 0; i < listToShuffle.Count; i++)
ints.Add(i);

List<T> randList = new List<T>(listToShuffle.Capacity);

for (int k = 0; k < listToShuffle.Count; k++)
{
int randIndx = Common.rand.Next(ints.Count); //random
from 0, 2, .. not already picked
int randK = ints[randIndx];
randList.Add(listToShuffle[randK]);
ints.RemoveAt(randIndx);
}

return randList;
}

Nov 18 '05 #9

P: n/a
If it were homework, I suspect he'd be asking about a random shuffle instead
of a random sort. :-)

Pete

"Bill Butler" <qw****@asdf.com> wrote in message
news:2i4ff.49$N44.45@trndny08...

"gl" <gl@discussions.microsoft.com> wrote in message
news:7E**********************************@microsof t.com...
How do I take an array or arraylist, and sort it randomly? Like suppose
the
items in it are (1,2,3,4,5) and I want to get it to be in a random order
(2,3,1,4,5). How do you do that? I think it's a call to the array or
array
lists sort method, but i'm not exactly sure how you do it.


Sniff....Sniff....Smells like homework.

Search google groups for shuffle algorithm
You should find what you need

Good luck
Bill

Nov 18 '05 #10

This discussion thread is closed

Replies have been disabled for this discussion.