flat assembler
Message board for the users of flat assembler.

 Index > Main > Sorting approach
Author
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.
12 Apr 2020, 12:38
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.
12 Apr 2020, 13:07
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8347
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.
12 Apr 2020, 13:09
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum