Grouping items in an array?

views:

answers:

+1 Q:

Grouping items in an array?

Hey guys, if I have an array that looks like [A,B,C,A,B,C,A,C,B] (random order), and I wish to arrange it into [A,A,A,B,B,B,C,C,C] (each group is together), and the only operations allowed are: 1)query the i-th item of the array 2)swap two items in the array.

How to design an algorithm that does the job in O(n)?

Thanks!

+1 A:

Roger Pate 2010-01-05 01:18:10

This is related to sorting, but not a sorting problem. He wants an O(n) algorithm to group items together in the array - the order of the groups doesn't matter.

BlueRaja - Danny Pflughoeft 2010-01-05 01:43:18

+1 A:

Hamish Grubijan 2010-01-05 01:36:21

Thanks so much!

WayToProgram 2010-01-05 01:43:07

Did you know you can use `[text](URL)`? It's curious for someone that commented encouraging tagging as homework to just give away the answer. (That last has nothing to do with you, even though I have been critical of your blatant rep-whoring lately, just my recent notice of the homework tag and how it's applied.)

Roger Pate 2010-01-05 01:46:59

No P. However, beware that you are asked to work this thing in-place. So, it is a bit different I think.

Hamish Grubijan 2010-01-05 01:47:58

Roger, I wrote in this forum that I am not going to get laid by my gf until I get 1000 rep. You aren't that gullible, are you. Also, about hw: I know plenty of people who took algorithms to never see that stuff again and code awesome php web pages. Trust me when I say that these guys will not need to implement their own sort ... ever.

Hamish Grubijan 2010-01-05 01:50:56

And by the way, I did take an OS class but I do not remember 80% of what I studied there. I did mostly my own work. I will admit that my undergrad program was not the best.

Hamish Grubijan 2010-01-05 01:52:12

I honestly don't care *why* you said you need 1k rep (and I never saw that specific comment, only http://stackoverflow.com/questions/1995815/), but I've seen you abusing the system (unfortunately the deleted question was the best example) and that behavior should be discouraged.

Roger Pate 2010-01-05 01:57:32

I was honestly trying to help you format better answers (and thus get the rep you desperately need *without* abusing the system). I find the `[text](URL)` format easiest to type instead of using the UI buttons (and rarely use the other link formats). Edited to show example.

Roger Pate 2010-01-05 02:00:32

Ah, now I understand your OS class comment. I was just talking publicly about homework tagging/commenting, as I've been paying closer attention (instead of just ignoring the debate as I did previously). See http://meta.stackoverflow.com/questions/34503/ and http://meta.stackoverflow.com/questions/34511/ for reference.

Roger Pate 2010-01-05 02:36:50

ansaurus

tags:

views:

answers:

Grouping items in an array?

related questions