Jul -- Projects and Creations: It does not hurt to pose smart.

buphomet

Paragoomba
Level: 17

Posts: 69/74
EXP: 20654
For next: 4089

Since: 06-06-19

Pronouns: him/they

Since last post: 2.7 years
Last activity: 2.7 years

Posted on 07-28-19 08:53:14 AM (last edited by buphomet at 07-29-19 12:37:19 PM)

Link | Quote

You might find me posting implementations of algorithms, data structures and the like around here. Working on such is how my free time gets spent.

My ultimate aim in the future is to rip the Linux kernel apart, critique the code, it should probably be fun to also get my changes merged into the ultimate open source project there is out there.

Anyway, to start with, here is my implementation of the worst sorting algorithm there possibly is out there, bubble sort.

Any comments, critique or basically any sort of input to this thread would be much appreciated.

Here we go, cheers!




#include <iostream>


void BubbleSort(size_t length/* size of the array */, int *arr /* array itself */, bool order /* sorting order, ascending or descending */)

{

   for(size_t i = 0; i < length; i++)

       {

           for (size_t j = 0; j < length; j++) 

             {

                   /* sort according to the order */

                   if ( order )

                        {

                           if (arr[j] > arr[i])

                                {

                                   /* swap */

                                  int temp = arr[i];

                                  arr[i] = arr[j];

                                    arr[j] = temp;

                              }

                   }

                   else

                        {

                           else if (arr[j] < arr[i])

                                {

                                   int temp = arr[j];

                                  arr[j] = arr[i]

                                     arr[i] = temp;

                              }

                   }

           }

   }

   return;

}

Thanks in advance!

PS: It just occurred to me that the board does not handle code in the best way there is making it a lot more harder to read.

You might want to view the code as it appears in a text editor [img src="https://imgur.com/DCqfmGv"> here

Okay, whatever, BBCode seemed to fix it.

A more recent version of the code, presumably the correct code:




#include <stdio.h>

#include <stdbool.h>


void BubbleSort(int *arr /* array itself */, size_t length, bool order /* sorting order, ascending or descending */)

{

      /* do not take chances with the compiler */

 if ( order )

        {

           for(size_t i = 0; i < length; i++)

               {

                   for(size_t j = 1; j < length - 1; j++)

                   {


                               if (arr[j - 1] < arr[ j ])

                               {

                                   int temp = arr [ j ];

                                       arr[ j ] = arr[j - 1];

                                      arr[j - 1] = temp;

                          }

                   }

           }

   }

   else

        {

           for(size_t i = 0; i < length; i++)

               {

                   for(size_t j = 1; j < length; j++)

                       {


                               if (arr[j - 1] > arr[ j ])

                          {

                                   int temp = arr [ j ];

                                       arr[ j ] = arr[j - 1];

                                      arr[j - 1] = temp;

                          }

                   }

           }

   }

}



int main(int argc, char *argv)

{

       const int ArrayLength = 50;


     int arr[50] = {

                                     0x40, 0x50, 0x8, 0x31, 0x6, 0x19, 0x5, 0x40, 0x30, 0x31,

                                    0x41, 0x32, 0x41, 0x20, 0x36, 0x46, 0x31, 0x20, 0xff, 0x12,

                                 0x45, 0xe, 0xa, 0x3e, 0x22, 0x43, 0x32, 0x41, 0x45, 0x36,

                                   0xfe, 0x5a, 0xef, 0x3d, 0x23, 0x34, 0xf3, 0x22, 0x31, 0x5a,

                                 0xff, 0x3e, 0x5f, 0x88, 0x100, 0x34, 0x45, 0x21, 0xfd, 0x35

 };


      BubbleSort(arr, ArrayLength, true)

                                

      for(int i = 0; i < ArrayLength; /* i++ */)

       {

           for (int j = 0; j < 10; j++)

             {

                   fprintf(stdout, "0x%x ", arr[i + j])

                }


               i+=10;


          fprintf(stdout, "\n")

               

    }


       return 0;

}

Chalcedony

Level: 23

Posts: 90/139
EXP: 64628
For next: 3095

Since: 01-20-18

Pronouns: she/they (often dual)

Since last post: 79 days
Last activity: 4 hours

Posted on 07-28-19 01:57:38 PM

Link | Quote

^β“worst”? Ahaha. Worst of the sorta-reasonable ones, maybe. There are many more. I think I had a better reference for these, too, but I couldn't find it…

As for what you've just put up, if I might bluntly rattle off a few things:

What you have does not look like a bubble sort. (There's also syntax errors in the second branch of the if.) Bubble sorts compare adjacent elements, whereas you're comparing every element to every other, including in both directions, so I'm not sure this is even a sort at all. If your loop ranges were a little different, you would have something that looks like a selection sort that uses extra swaps instead of a temporary.
In C, it's more conventional to pass arrays with the pointer first and the element count second—but then, you have an #include <iostream> which implies you're in C++ (and is unused anyway)… ? C++-as-written-in-C-style tends to go similarly to C, but it's more conventional at the application level to use all the modern container classes and such which I haven't read about in ages.
Putting the sort order test in the inner loop feels weird; it'll be tested O(N^2) times unless the compiler hoists it for you.
return; at the end of a void function is redundant.

Getting anything actually merged into Linux is highly nontrivial. It's an interesting goal, but (a) don't get too attached, since even if you get in range of it, you'd have to have something specific to do and integrate yourself into the whole process and such, and (b) you have a long way to go… but, once you've got more of an idea of how systems code works, tinkering with kernel modules is still a neat way to learn.

Good luck with learning!

____________________

Your friendly local Chalcedony comprises primarily {[α] Illum, [β] Teneb}, their compositions, and others who don't use this account but are important parts of our system nonetheless. #plural #otherkin ^..^

buphomet

Paragoomba
Level: 17

Posts: 70/74
EXP: 20654
For next: 4089

Since: 06-06-19

Pronouns: him/they

Since last post: 2.7 years
Last activity: 2.7 years

Posted on 07-29-19 09:50:28 AM (last edited by buphomet at 07-29-19 12:38:06 PM)

Link | Quote

It -sucks- to post on this before updating the code but it looks like it might take me a bit of time to fix the code so, yeah, here we go. Posting this anyway but the code will be updated, later.

[finally posted the code, it turned out to be a lot easier than was expected, actually

]

Originally posted by Chalcedony

^β“worst”? Ahaha. Worst of the sorta-reasonable ones, maybe. There are many more. I think I had a better reference for these, too, but I couldn't find it…

Yeah, it looks like are a lot more sorts out there that are much much worse than bubble sort, yes.

Originally posted by Chalcedony

As for what you've just put up, if I might bluntly rattle off a few things:

Thanks in advance!

Originally posted by Chalcedony

What you have does not look like a bubble sort. (There's also syntax errors in the second branch of the if.) Bubble sorts compare adjacent elements, whereas you're comparing every element to every other, including in both directions, so I'm not sure this is even a sort at all.

The code, indeed does not implement a sort.

Originally posted by Chalcedony

If your loop ranges were a little different, you would have something that looks like a selection sort that uses extra swaps instead of a temporary.

Redoing this all again looks like the way to go.

Originally posted by Chalcedony

In C, it's more conventional to pass arrays with the pointer first and the element count second—but then, you have an #include <iostream> which implies you're in C++ (and is unused anyway)… ? C++-as-written-in-C-style tends to go similarly to C, but it's more conventional at the application level to use all the modern container classes and such which I haven't read about in ages.

This code is admittedly a bit messy, yes. It would have been good to try cleaning it up before posting it here.

Originally posted by Chalcedony

Putting the sort order test in the inner loop feels weird; it'll be tested O(N^2) times unless the compiler hoists it for you.

Right, thanks for pointing that out. In the updated code, the sort order test should be the first part of the algorithm.

Originally posted by Chalcedony

return; at the end of a void function is redundant.

That is right, again, it would have been a great idea to clean up the code before posting it here.

Originally posted by Chalcedony

Getting anything actually merged into Linux is highly nontrivial. It's an interesting goal, but (a) don't get too attached, since even if you get in range of it, you'd have to have something specific to do and integrate yourself into the whole process and such, and (b) you have a long way to go… but, once you've got more of an idea of how systems code works, tinkering with kernel modules is still a neat way to learn.

Well, my interest is not exactly Linux but computer science and related topics which includes but is not limited to algorithms, compilers, operating systems and related concepts.

It is not something specific about Linux that interests me but Linux and other FOSS projects(specifically R project) should be great places to learn from and if it happens that you get good enough, it might be even possible to actively contribute to this project.

Originally posted by Chalcedony

Good luck with learning!

It does not look like there is any other place to run to other than to learn.

Your HMTL post was a bit intriguing!

Thanks!

Register - Login
Views: 99393026	Main - Memberlist - Active users - Calendar - Wiki - IRC Chat - Online users Ranks - Rules/FAQ - Stats - Latest Posts - Color Chart - Smilies	04-24-22 10:18:46 AM

Query execution time:	0.088965 seconds
Script execution time:	0.012557 seconds
Total render time:	0.101522 seconds