Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Sorting, Part I

Name: Anonymous 2009-03-29 11:17

//Bubble sort

//Bubble sort [TOP]
Array length:  10000 | Type: integer | Time:   319 ms |
Array length:  20000 | Type: integer | Time:  1281 ms |
Array length:  30000 | Type: integer | Time:  2868 ms |
Array length:  40000 | Type: integer | Time:  5086 ms |
Array length:  50000 | Type: integer | Time:  7965 ms |
Array length:  60000 | Type: integer | Time: 11462 ms |
Array length:  70000 | Type: integer | Time: 15708 ms |
Array length:  80000 | Type: integer | Time: 20418 ms |
Array length:  90000 | Type: integer | Time: 26028 ms |
Array length: 100000 | Type: integer | Time: 32243 ms |

//Bubble sort [BOTTOM]
Array length:  10000 | Type: integer | Time:   331 ms |
Array length:  20000 | Type: integer | Time:  1294 ms |
Array length:  30000 | Type: integer | Time:  2696 ms |
Array length:  40000 | Type: integer | Time:  4772 ms |
Array length:  50000 | Type: integer | Time:  7423 ms |
Array length:  60000 | Type: integer | Time: 10789 ms |
Array length:  70000 | Type: integer | Time: 14758 ms |
Array length:  80000 | Type: integer | Time: 19236 ms |
Array length:  90000 | Type: integer | Time: 24246 ms |
Array length: 100000 | Type: integer | Time: 29840 ms |

//Code
    /*Bubble sort [TOP]*/
    public static int[] BubbleT(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            for(int j = arr.length - 1; i < j; j--) {
                if(arr[j] < arr[j-1]) {
                    int temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
   
    /*Bubble sort [BOTTOM]*/
    public static int[] BubbleB(int[] arr) {
        for(int i = arr.length - 1; 0 <= i; i--) {
            for(int j = 0; j < i; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

//Shaker sort
Array length:  10000 | Type: integer | Time:   584 ms |
Array length:  20000 | Type: integer | Time:  2287 ms |
Array length:  30000 | Type: integer | Time:  5080 ms |
Array length:  40000 | Type: integer | Time:  9031 ms |
Array length:  50000 | Type: integer | Time: 14130 ms |
Array length:  60000 | Type: integer | Time: 20351 ms |
Array length:  70000 | Type: integer | Time: 27678 ms |
Array length:  80000 | Type: integer | Time: 36138 ms |
Array length:  90000 | Type: integer | Time: 45868 ms |
Array length: 100000 | Type: integer | Time: 57483 ms |

//Code
    public static int[] Shaker(int[] arr) {
        for(int i = 0, dir = -1; i < arr.length; i++) {
            for(int j = (dir == -1? 1 : arr.length - 1), pos = 0; 0 < j && j < arr.length; pos = dir == -1? j++ : j--) {
                if(arr[j] < arr[j-1]) {
                    int temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
            dir = -dir;
        }
        return arr;
    }

Obviously, I'm doing something wrong. But what?

Name: Anonymous 2009-03-29 11:23

lrn2radix sort
O(n) time > slow shit

Name: Anonymous 2009-03-29 11:27

You're using Java and not putting spaces after your // .

Name: Anonymous 2009-03-29 11:47

>>3
That's not really the point. I just want to know why the shaker sort is slower compared to bubble sort. I know that there is something wrong with my implementation. I can't figure out why.

Name: Anonymous 2009-03-29 11:54

>>4
It really is.

Name: Anonymous 2009-03-29 12:16

Just put it in your database then write SQL programs.

Name: Anonymous 2009-03-29 12:18

I gotta copypasta this:

Currently learning sorts; this will be more hillarious than my off by one errors with recursive mergesorting.

btw, I really don't think you need a space after //, unless it's fudging up the other comments

Name: Anonymous 2009-03-29 12:21

You're right. The actual problem is that you're asking /prog/ to do your homework for you.

Name: Anonymous 2009-03-29 12:41

>>8
Nope, you are wrong. I have implemented as you have seen bubble sort, selection sort and insertion sort. Also I use Java only for testing the algorithm correctness. Of course, I could use induction to prove correctness. To the Java haters, I will rewrite the algorithms in C, when I'm done reading the K&R.

Now, please give me a hint, so I can fix my shaker sort and gtfo.

Name: Anonymous 2009-03-29 12:47

Here's a hint: You suck at programming.

Name: Anonymous 2009-03-29 12:48

void sort(int a[]) throws Exception { int i = 0; int k = a.length - 1; while (i < k) { int min = i; int max = i; int j; for (j = i + 1; j <= k; j++) { if (stopRequested) { return; } if (a[j] < a[min]) { min = j; } if (a[j] > a[max]) { max = j; } pause(i,j); } int T = a[min]; a[min] = a[i]; a[i] = T; pause(i,k); if (max == i) { T = a[min]; a[min] = a[k]; a[k] = T; } else { T = a[max]; a[max] = a[k]; a[k] = T; } pause(i,k); i++; k--; } }

Name: Anonymous 2009-03-29 12:53

>>10
Better than you.

Name: Anonymous 2009-03-29 13:09

>>12
Obviously not.

Name: Anonymous 2009-03-29 13:16

>>13
Obviously, he is talking shit, without posting some code.

Name: Anonymous 2009-03-29 13:23

READ SICP, and stop writing halfassed, poorly performing, distasteful sorting algorithms in halfassed, poorly performing, distasteful languages.

Name: Anonymous 2009-03-29 23:51

if you're sorting integers, use radix sort. unless it's for homework. if it's for homework, use fork() and sleep().

Name: Anonymous 2009-03-30 0:01

void sort(int length, int *array, int *output)
 {
  for(int i = 0; i < length; ++i)
   {
    if(!fork())
     {
      sleep(array[i]);
      *output++ =  array[i];
     }
   }
 }

Name: Anonymous 2009-03-30 0:56

>>17
I think I caught AIDS from your indentation style

Name: Anonymous 2009-03-30 2:34

>>18
thank gnu for inspiring it.

Name: Anonymous 2009-03-30 2:43

>>16
I want to implement basic sorting algorithms first, before implementing heap sort, quick sort, radix sort, etc. Again, this is not homework. I'm doing it because sorting is relevant for my interest.

Name: Anonymous 2009-03-30 3:00

>>20
OH GEE LETS REINVENT THE WHEEL AND WRITE THE MOST WRITTEN PEICE OF CODE IN THE HISTORY OF MAN AGAIN, BECAUSE WE ARE LEARNING TO BE PRO ALGORITHMS DESIGNERS THIS WAY IM SUCH A GOOD LEARNER BECAUSE I UNDERSTAND THIS

Name: Anonymous 2009-03-30 10:32

>>21
dont be hatin

Name: Anonymous 2009-03-30 10:33

>>22
Don't be a fucktard.

Name: Anonymous 2009-03-30 11:03

>>23
Don't be fucktardin[1]

[1] Merriam-Webster Dictionary, 2009 - http://www.merriam-webster.com/dictionary/fucktardin

Name: Anonymous 2009-03-30 11:32

>>24
Cool story.

Name: Anonymous 2009-03-30 13:36

>>21
Cry me a river.

Name: Anonymous 2009-03-30 13:40

>>26
Don't be a fucktard, again.

Name: Anonymous 2013-01-19 23:43

/prog/ will be spammed continuously until further notice. we apologize for any inconvenience this may cause.
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -