flat assembler
Message board for the users of flat assembler.

Index > Main > Sorting approach

Author
Thread Post new topic Reply to topic
Abruzzi



Joined: 30 Sep 2019
Posts: 17
Abruzzi 12 Apr 2020, 12:38
What is the good approach to sort a buffer that contains bitmap pixels by one of the color channels?

Let's suppose I have 4 pixels in format BBGGRRAA:
A01020FF C0C0C0FF 406080FF 7AE321FF

and arranged by green channel should be
A01020FF 406080FF C0C0C0FF 7AE321FF

When I say a good approach I am thinking about an easy implementation also not just fast execution and memory used. I think I am looking for a balanced solution between.
Post 12 Apr 2020, 12:38
View user's profile Send private message Reply with quote
DimonSoft



Joined: 03 Mar 2010
Posts: 1228
Location: Belarus
DimonSoft 12 Apr 2020, 13:07
Choose sorting algorithm you like most and instead of directly comparing the values compare the same values but bitwise-anded with appropriate mask.
Post 12 Apr 2020, 13:07
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8263
Location: Kraków, Poland
Tomasz Grysztar 12 Apr 2020, 13:09
I would myself use a bitwise algorithm, where you first arrange the list so that items having the topmost bit 0 are before the items having the highest bit 1, and then for each of these two sub-lists you repeat the process, but looking at the bit below, and so on.To arrange the list this way, you can scan from the beginning of the list until you reach an element with the highest bit set, and from the top of the list until you reach an element with highest bit zeroed, and if the former is before the latter in the list, you swap them and continue scanning.

In your case you'd be looking at the highest bit of the green channel, and continue (perhaps recursively) to cover all 8 bits. So at first you'd be testing bit 800000h, during the next step you would be testing 400000h, and so on, ending on the 010000h bit.

For assembly programming I have always been finding this algorithm very natural and easy, in fact in my early days of programming I had been using it without even realizing that it is simply a special case of Radix sort that one may learn during formal education.

Note, however, that this algorithm is not stable, so if you also need stability, you might need to consider another one.
Post 12 Apr 2020, 13:09
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2023, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.