Professional Web Applications Themes

Bubble sort and rand() - Ruby

> I don't know if bubble sort using a random number for comparisons is > always a good idea. Bubble sort runs over the array and compares two > subsequent values and swaps them if they are out of order. > It keeps doing that until there are no more swaps during a run. No, that's an optimization to end early if there *ARE* no swaps. The sort still just runs through the list a maximum n (or n-1) times. (Or at least there's no reason NOT to.) __________________________________ Do you Yahoo!? Yahoo! SiteBuilder - Free, easy-to-use web site design ...

  1. #1

    Default Bubble sort and rand()

    > I don't know if bubble sort using a random number for comparisons
    is
    > always a good idea. Bubble sort runs over the array and compares
    two
    > subsequent values and swaps them if they are out of order.
    > It keeps doing that until there are no more swaps during a run.
    No, that's an optimization to end early if there *ARE* no swaps. The
    sort still just runs through the list a maximum n (or n-1) times. (Or
    at least there's no reason NOT to.)

    __________________________________
    Do you Yahoo!?
    Yahoo! SiteBuilder - Free, easy-to-use web site design software
    [url]http://sitebuilder.[/url]

    Michael Campbell Guest

  2. #2

    Default Re: Bubble sort and rand()

    > No, that's an optimization to end early if there *ARE* no swaps. The
    > sort still just runs through the list a maximum n (or n-1) times. (Or
    > at least there's no reason NOT to.)
    I guess that depends on how they taught you that in college. We learned
    that you do it until there are no more swaps, but you know there's a
    maximum of n-1 runs (that's how much the last element needs to move to the
    head of the array), and that's why complexity is quadratic. But you are
    right, if you do it your way, whatever I said doesn't hold.

    Peter


    Peter Guest

Similar Threads

  1. DataGridCommand does not bubble?
    By Sergio Florez M. in forum ASP.NET Building Controls
    Replies: 3
    Last Post: November 19th, 07:01 PM
  2. Bubble effect help please
    By UncleDave in forum Macromedia Flash Sitedesign
    Replies: 2
    Last Post: February 17th, 11:53 PM
  3. String Bubble Sort
    By Gram in forum ASP
    Replies: 13
    Last Post: September 19th, 11:03 PM
  4. Replies: 1
    Last Post: September 9th, 07:16 AM
  5. Pop-up text bubble
    By behockey webforumsuser@macromedia.com in forum Macromedia Dreamweaver
    Replies: 2
    Last Post: July 23rd, 12:27 AM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139