Question

http://ideone.com/xYXNZ

So I've coded up all the basic computer science \( O(n^2) \) comparison sort algorithms.

1. What are the differences between my_bubble_sort and the default bubble_sort (the default one is an implementation of the pseudocode on wikipedia, whereas my_bubble_sort was something I came up with).

2. Are the rand_range and shuffle algorithms alright?

3. I've got a macro to test the sorting algorithms, but above it I've also got a commented-out function that does the same thing. Should I stick with the macro or use the function?

Answer 1

I may be missing something since I'm only at the beginning of the course, but why do you post C code here ? Is it Python at the beginning and C later ?
I don't understand the forst question. Since this is your code, shouldn't you be able to tell the difference yourself ?
To test your code, since you look pretty good in C, maybe you could try to learn unit testing C code ?
http://stackoverflow.com/questions/65820/unit-testing-c-code

Answer 2

Don't worry; C isn't part of MIT 6.00. (it's part of http://cs50.tv , but that's a different course and it's also as good as MIT's 6.00)

I probably could tell the difference myself, but I could always use additional insight.

Thanks for the link; I'm just a beginner at C and I've always needed to learn how to properly write and use unit tests.

Answer 3

As a seasoned Java developer, I can tell you that unit testing is always a good idea, and a good skill to have.
Thank you for your answer ! I was afraid I had to code in C ! This language has always been a nightmare for me... But it's a powerful language indeed.

Answer 4

I can say the same to C++, and a bit of Java, I didn't have a good time coding in them, :-)
@agdgdgdgwngo I usually like coding a separate test file that I can add test cases, and some commentaries/documentation. It also allows you to check what you have covered and when you broke something that was already working. Needless to say, it's important to always back up your work before a big modification. :-)

Answer 5

To answer my own question:

1. They are both pretty similar. Here is the disassembly:

my_bubble_sort()
____________________________________________________
004018B4 push %ebp
004018B5 mov %esp,%ebp
004018B7 push %edi
004018B8 push %esi
004018B9 push %ebx
004018BA sub $0x2c,%esp
004018BD mov 0xc(%ebp),%edi
004018C0 test %edi,%edi
004018C2 je 0x401912 <my_bubble_sort+94>
004018C4 mov 0xc(%ebp),%edi
004018C7 dec %edi
004018C8 movl $0x0,-0x1c(%ebp)
004018CF nop
004018D0 test %edi,%edi
004018D2 je 0x401906 <my_bubble_sort+82>
004018D4 mov 0x8(%ebp),%eax
004018D7 xor %ebx,%ebx
004018D9 jmp 0x4018e3 <my_bubble_sort+47>
004018DB nop
004018DC inc %ebx
004018DD cmp %ebx,%edi
004018DF jbe 0x401906 <my_bubble_sort+82>
004018E1 mov %esi,%eax
004018E3 lea 0x4(%eax),%esi
004018E6 mov (%eax),%edx
004018E8 cmp 0x4(%eax),%edx
004018EB jle 0x4018dc <my_bubble_sort+40>
004018ED movl $0x4,0x8(%esp)
004018F5 mov %esi,0x4(%esp)
004018F9 mov %eax,(%esp)
004018FC call 0x401728 <swap>
00401901 inc %ebx
00401902 cmp %ebx,%edi
00401904 ja 0x4018e1 <my_bubble_sort+45>
00401906 incl -0x1c(%ebp)
00401909 dec %edi
0040190A mov -0x1c(%ebp),%eax
0040190D cmp %eax,0xc(%ebp)
00401910 ja 0x4018d0 <my_bubble_sort+28>
00401912 add $0x2c,%esp
00401915 pop %ebx
00401916 pop %esi
00401917 pop %edi
00401918 leave
00401919 ret

bubble_sort()
______________________________________________________
00401854 push %ebp
00401855 mov %esp,%ebp
00401857 push %edi
00401858 push %esi
00401859 push %ebx
0040185A sub $0x1c,%esp
0040185D mov 0xc(%ebp),%edi
00401860 cmp $0x1,%edi
00401863 jle 0x4018ab <bubble_sort+87>
00401865 mov 0x8(%ebp),%eax
00401868 xor %edx,%edx
0040186A mov $0x1,%ebx
0040186F jmp 0x40187e <bubble_sort+42>
00401871 lea 0x0(%esi),%esi
00401874 lea 0x4(%eax),%esi
00401877 inc %ebx
00401878 mov %esi,%eax
0040187A cmp %ebx,%edi
0040187C jle 0x4018a5 <bubble_sort+81>
0040187E mov (%eax),%ecx
00401880 cmp 0x4(%eax),%ecx
00401883 jle 0x401874 <bubble_sort+32>
00401885 movl $0x4,0x8(%esp)
0040188D lea 0x4(%eax),%esi
00401890 mov %esi,0x4(%esp)
00401894 mov %eax,(%esp)
00401897 call 0x401728 <swap>
0040189C mov %ebx,%edx
0040189E inc %ebx
0040189F mov %esi,%eax
004018A1 cmp %ebx,%edi
004018A3 jg 0x40187e <bubble_sort+42>
004018A5 mov %edx,%edi
004018A7 test %edx,%edx
004018A9 jne 0x401860 <bubble_sort+12>
004018AB add $0x1c,%esp
004018AE pop %ebx
004018AF pop %esi
004018B0 pop %edi
004018B1 leave
004018B2 ret

I'd argue that the second bubble_sort() is better; for one, it keeps track of much less.

2. http://stackoverflow.com/questions/2509679/how-to-generate-a-random-number-from-within-a-range-c see Ryan Reich's answer

3. I might be mistaken, but I found the macro better.