CODEWITHSUNDEEP
sortingalgorithm
user243592
user243592

Reputation:

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!

Upvotes: 0

Views: 272

Answers (2)

Hamish Grubijan
Hamish Grubijan

Reputation: 10820

This is actually just counting sort.

Scan the array once, count the number of As, Bs, Cs—that should give you an idea. This becomes like bucket sort—not quite but along those lines. The count of As Bs and Cs should give you an idea about where the string of As, Bs and Cs belongs.

Upvotes: 1

Roger Pate
Roger Pate

Reputation:

Sort algorithms aren't something you design fresh (i.e. first step of your development process) anymore; you should research known sort algorithms and see what meets your needs.

(It is of course possible you might really require your own new sort algorithm, but usually that has different—and highly-specific—requirements.)

If this isn't your first step (but I don't think that's the case), it would be helpful to know what you've already tried and how it failed you.

Upvotes: 1

Related Questions