Re: How to arrange some numbers

Discussion in 'C Programming' started by BartC, Mar 15, 2013.

  1. BartC

    BartC Guest

    "paskali" <> wrote in message
    news:...
    > Hi, a simple question:
    > i want to arrange some int numbers; i want to store them
    > in an array and then print them on the screen.
    >
    > Look below:
    >
    > int numbers[10], arranged[10], i;
    > puts("Insert 10 int numbers");
    > for(i = 0; i <= 9; i ++, scanf("%d", &numbers));
    > ?
    > for(i = 0; i <= 9; i ++, printf("/n%d", arranged));
    >
    > I insert: 10 7 45 678 0 34 6 1 4 3
    > I should see on the screen: 0 1 3 4 6 7 10 34 45 678
    > Simple. Help me to replace question mark.


    I've provided some code below. Note that this uses the world's worst sort
    method, so won't get you many marks. But it's also my favourite sort.

    Also in this code:

    o For testing, I've hard-coded the test data (otherwise each you'll have to
    type in all the numbers for each run, or arrange to import them from a file)

    o I've put in code to show the numbers both before and after the sort, so
    that you'll know exactly what the input is.

    o The sorting is done in-place, so only one array is needed (you will need
    two to preserve the original data).

    #include <stdio.h>
    #include <stdlib.h>

    int main (void) {
    #define N 10
    int numbers[N]={10,7,45,678,0,34,6,1,4,3};
    int i,swapped,temp;

    printf("Numbers before sorting:\n");
    for (i=0; i<N; ++i) {
    printf("%d ",numbers);
    }
    printf("\n\n");

    /* Sort routine */
    do {
    swapped=0;
    for (i=0; i<N-1; ++i) {
    if (numbers>numbers[i+1]) {
    swapped=1;
    temp=numbers;
    numbers=numbers[i+1];
    numbers[i+1]=temp;
    }
    }
    }
    while (swapped);
    /***************/

    printf("Numbers after sorting:\n");
    for (i=0; i<N; ++i) {
    printf("%d ",numbers);
    }
    printf("\n");

    }
     
    BartC, Mar 15, 2013
    #1
    1. Advertising

  2. BartC <> wrote:

    (snip, and previously snipped discussion on bubblesort)

    > I've provided some code below. Note that this uses the world's worst sort
    > method, so won't get you many marks. But it's also my favourite sort.


    It was the first sort algorithm I knew about, as it was a sample
    program in the IBM Fortran manual that I used to learn Fortran.
    (Summer after 8th grade.) Only one I knew for some years.

    -- glen
     
    glen herrmannsfeldt, Mar 15, 2013
    #2
    1. Advertising

  3. On Saturday, March 16, 2013 10:29:27 AM UTC, David Brown wrote:
    > On 15/03/13 23:55, BartC wrote:
    >
    > Bubblesort has a lot of real-world uses.
    >

    Bubblesort is also very fast when data is almost sorted.
    An example would be a football league. Only one game can be played by each
    team each day, and teams only get three points for a win. So it's unlikely
    that any team will move more than a place or two after each game. The list
    is almost sorted, and bubblesort will only take a few passes.
     
    Malcolm McLean, Mar 16, 2013
    #3
  4. On Mar 15, 10:55 pm, "BartC" <> wrote:
    > "paskali" <> wrote in message
    >
    > news:...
    >
    > > Hi, a simple question:
    > > i want to arrange some int numbers; i want to store them
    > > in an array and then print them on the screen.

    >
    > > Look below:

    >
    > >    int numbers[10], arranged[10], i;
    > >    puts("Insert 10 int numbers");
    > >    for(i = 0; i <= 9; i ++, scanf("%d", &numbers));
    > >    ?
    > >    for(i = 0; i <= 9; i ++, printf("/n%d", arranged));

    >
    > > I insert: 10 7 45 678 0 34 6 1 4 3
    > > I should see on the screen: 0 1 3 4 6 7 10 34 45 678
    > > Simple. Help me to replace question mark.

    >
    > I've provided some code below. Note that this uses the world's worst sort
    > method, so won't get you many marks. But it's also my favourite sort.


    Boggo Sort
    1. randomly permutate the array
    2. if its ordered halt otherwise repeat step 1

    Quantum Boggo Sort
    1. randomly permutate the array
    2. if it isn't ordered destroy the universe
    3. if your universe reaches this step halt
    (this sorts in O(n))

    Worst Sort (used on letters)
    1. set n <- 0 set letter <- 'A'
    2. search for letter
    3. if found insert letter at position n and increment n
    4. move to next letter
    5. repeat step 2

    Assuming no repeated letters this sorts in only 26 passes or less.
    I've seen this implemented in a real system...

    > Also in this code:
    >
    > o For testing, I've hard-coded the test data (otherwise each you'll have to
    > type in all the numbers for each run, or arrange to import them from a file)
    >
    > o I've put in code to show the numbers both before and after the sort, so
    > that you'll know exactly what the input is.
    >
    > o The sorting is done in-place, so only one array is needed (you will need
    > two to preserve the original data).
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > int main (void) {
    > #define N 10
    > int numbers[N]={10,7,45,678,0,34,6,1,4,3};
    > int i,swapped,temp;
    >
    > printf("Numbers before sorting:\n");
    > for (i=0; i<N; ++i) {
    >  printf("%d ",numbers);}
    >
    > printf("\n\n");
    >
    > /* Sort routine */
    > do {
    >  swapped=0;
    >  for (i=0; i<N-1; ++i) {
    >   if (numbers>numbers[i+1]) {
    >    swapped=1;
    >    temp=numbers;
    >    numbers=numbers[i+1];
    >    numbers[i+1]=temp;
    >   }
    >  }}
    >
    > while (swapped);
    > /***************/
    >
    > printf("Numbers after sorting:\n");
    > for (i=0; i<N; ++i) {
    >  printf("%d ",numbers);}
    >
    > printf("\n");
    > }
     
    Nick Keighley, Mar 16, 2013
    #4
  5. On Mar 16, 10:29 am, David Brown <>
    wrote:
    > On 15/03/13 23:55, BartC wrote:
    >
    > > I've provided some code below. Note that this uses the world's worst sort
    > > method, so won't get you many marks. But it's also my favourite sort.

    >
    > Bubblesort has a lot of real-world uses.  It has a worse complexity
    > scaling than the "big" sorting algorthims (mergesort, heapsort,
    > quicksort, etc.), but run speed is not always the most important issue.
    >  /Correctness/ is far more important - and it is much easier to write a
    > correct bubblesort than a correct heapsort.  For small samples,
    > especially on more limited systems (such as embedded systems),
    > bubblesort will often be significantly faster than using a generic
    > library "qsort" function - and very much smaller in code space.
    >
    > Anyway, I thought the world's worst sort method was this:
    >
    > <http://en.wikipedia.org/wiki/Bogosort>


    but insert sort is as simple *and* better
     
    Nick Keighley, Mar 16, 2013
    #5
  6. Nick Keighley <> wrote:

    (snip)

    > Worst Sort (used on letters)
    > 1. set n <- 0 set letter <- 'A'
    > 2. search for letter
    > 3. if found insert letter at position n and increment n
    > 4. move to next letter
    > 5. repeat step 2


    > Assuming no repeated letters this sorts in only 26 passes or less.
    > I've seen this implemented in a real system...


    Radix sort with Radix 1.

    There is some discussion about Radix sort, and whether it is
    really O(N). It is for fixed word size, but O() is supposed to
    be for limit as N goes to infinity. Modify yours slightly:

    Count 'A's, count 'B's, etc.

    Write to the output file the appropriate number of 'A's, then
    the 'B's, etc.

    -- glen
     
    glen herrmannsfeldt, Mar 16, 2013
    #6
  7. BartC

    Eric Sosman Guest

    On 3/16/2013 10:40 AM, David Brown wrote:
    > [...]
    > Insert sort is not "as simple /and/ better" than bubblesort. To do an
    > efficient insertion sort (and it has to be efficient, or it is not
    > "better"), you need to use a binary search to find the insertion point
    > for each element, and you need to hold your elements in a linked list
    > rather than a static array (otherwise you need to move half your data
    > for every insertion, which is not "better").


    I guess the guy who wrote

    "It took a good deal of work to analyze the bubble sort;
    and although the techniques used in the calculations are
    instructive, the results are disappointing since they tell
    us that the bubble sort isn't really very good at all.
    Compared to straight insertion (Algorithm 5.2.1S), bubble
    sorting requires a more complicated program and takes more
    than twice as long!"
    -- D.E. Knuth, "The Art of Computer Programming"

    .... didn't know what he was talking about.

    --
    Eric Sosman
    d
     
    Eric Sosman, Mar 16, 2013
    #7
  8. On Mar 16, 3:16 pm, Eric Sosman <>
    wrote:
    > On 3/16/2013 10:40 AM, David Brown wrote:
    >
    > > [...]
    > > Insert sort is not "as simple /and/ better" than bubblesort.  To do an
    > > efficient insertion sort (and it has to be efficient, or it is not
    > > "better"), you need to use a binary search to find the insertion point
    > > for each element, and you need to hold your elements in a linked list
    > > rather than a static array (otherwise you need to move half your data
    > > for every insertion, which is not "better").

    >
    >      I guess the guy who wrote
    >
    >         "It took a good deal of work to analyze the bubble sort;
    >         and although the techniques used in the calculations are
    >         instructive, the results are disappointing since they tell
    >         us that the bubble sort isn't really very good at all.
    >         Compared to straight insertion (Algorithm 5.2.1S), bubble
    >         sorting requires a more complicated program and takes more
    >         than twice as long!"
    >         -- D.E. Knuth, "The Art of Computer Programming"
    >
    > ... didn't know what he was talking about.


    yeah. who's he anyway?




    :)
     
    Nick Keighley, Mar 16, 2013
    #8
  9. BartC

    Eric Sosman Guest

    On 3/16/2013 2:39 PM, Robert Wessel wrote:
    > On Sat, 16 Mar 2013 15:40:23 +0100, David Brown
    > <> wrote:
    >
    >> On 16/03/13 14:10, Nick Keighley wrote:
    >>> On Mar 16, 10:29 am, David Brown <>
    >>> wrote:
    >>>> On 15/03/13 23:55, BartC wrote:
    >>>>
    >>>>> I've provided some code below. Note that this uses the world's worst sort
    >>>>> method, so won't get you many marks. But it's also my favourite sort.
    >>>>
    >>>> Bubblesort has a lot of real-world uses. It has a worse complexity
    >>>> scaling than the "big" sorting algorthims (mergesort, heapsort,
    >>>> quicksort, etc.), but run speed is not always the most important issue.
    >>>> /Correctness/ is far more important - and it is much easier to write a
    >>>> correct bubblesort than a correct heapsort. For small samples,
    >>>> especially on more limited systems (such as embedded systems),
    >>>> bubblesort will often be significantly faster than using a generic
    >>>> library "qsort" function - and very much smaller in code space.
    >>>>
    >>>> Anyway, I thought the world's worst sort method was this:
    >>>>
    >>>> <http://en.wikipedia.org/wiki/Bogosort>
    >>>
    >>> but insert sort is as simple *and* better
    >>>

    >>
    >> Insert sort is not "as simple /and/ better" than bubblesort. To do an
    >> efficient insertion sort (and it has to be efficient, or it is not
    >> "better"), you need to use a binary search to find the insertion point
    >> for each element, and you need to hold your elements in a linked list
    >> rather than a static array (otherwise you need to move half your data
    >> for every insertion, which is not "better").
    >>
    >> Of course, this is for a general sort - for some kinds of applications,
    >> insertion sort is very well suited.
    >>
    >> Unless you meant that insert sort is as simple and better than bogosort...

    >
    >
    > No, ordinary insertion sort requires neither of those, and can sort an
    > array with no additional storage, just like bubble sort. The basic
    > idea is that you take each element and then move it back one spot at a
    > time in the array (by swapping with the prior element) until it's in
    > the correct spot. It's still O(n**2), but usually runs about twice as
    > fast as bubble sort, and the code is usually shorter too.
    >
    > for(i=1; i<N; i++)
    > for(j=i; j>0; j--)
    > {
    > if (a[j-1] > a[j])
    > swap(a[j-1], a[j]);
    > else
    > break;
    > }


    A simple change will speed this up significantly on most
    machines. The problem is with the swap() operation: It will
    exchange (for example) items [10] and [9], then [9] and [8],
    then [8] and [7] -- six memory writes to slide the original
    [10] element three places to the left. By holding the "moving"
    element in a temporary throughout, you can avoid almost half
    the writes:

    for (i = 1; i < N; ++i) {
    int temp = a;
    for (j = i; --j >= 0; ) {
    if (a[j] > temp)
    a[j+1] = a[j];
    else
    break;
    }
    a[j+1] = temp;
    }

    For the same rearrangement, this code loads temp from [10],
    then copies [9] to [10], [8] to [9], [7] to [8] and finally
    stores temp in [7] -- four writes instead of six. (Assuming
    that temp winds up in a register; if it doesn't, there'll
    be five writes instead of nine because swap() will need an
    additional internal write, too.)

    --
    Eric Sosman
    d
     
    Eric Sosman, Mar 16, 2013
    #9
  10. Eric Sosmanæ–¼ 2013å¹´3月17日星期日UTC+8上åˆ3時41分20秒寫é“:
    > On 3/16/2013 2:39 PM, Robert Wessel wrote:
    >
    > > On Sat, 16 Mar 2013 15:40:23 +0100, David Brown

    >
    > > <> wrote:

    >
    > >

    >
    > >> On 16/03/13 14:10, Nick Keighley wrote:

    >
    > >>> On Mar 16, 10:29 am, David Brown <>

    >
    > >>> wrote:

    >
    > >>>> On 15/03/13 23:55, BartC wrote:

    >
    > >>>>

    >
    > >>>>> I've provided some code below. Note that this uses the world's worst sort

    >
    > >>>>> method, so won't get you many marks. But it's also my favourite sort.

    >
    > >>>>

    >
    > >>>> Bubblesort has a lot of real-world uses. It has a worse complexity

    >
    > >>>> scaling than the "big" sorting algorthims (mergesort, heapsort,

    >
    > >>>> quicksort, etc.), but run speed is not always the most important issue.

    >
    > >>>> /Correctness/ is far more important - and it is much easier to write a

    >
    > >>>> correct bubblesort than a correct heapsort. For small samples,

    >
    > >>>> especially on more limited systems (such as embedded systems),

    >
    > >>>> bubblesort will often be significantly faster than using a generic

    >
    > >>>> library "qsort" function - and very much smaller in code space.

    >
    > >>>>

    >
    > >>>> Anyway, I thought the world's worst sort method was this:

    >
    > >>>>

    >
    > >>>> <http://en.wikipedia.org/wiki/Bogosort>

    >
    > >>>

    >
    > >>> but insert sort is as simple *and* better

    >
    > >>>

    >
    > >>

    >
    > >> Insert sort is not "as simple /and/ better" than bubblesort. To do an

    >
    > >> efficient insertion sort (and it has to be efficient, or it is not

    >
    > >> "better"), you need to use a binary search to find the insertion point

    >
    > >> for each element, and you need to hold your elements in a linked list

    >
    > >> rather than a static array (otherwise you need to move half your data

    >
    > >> for every insertion, which is not "better").

    >
    > >>

    >
    > >> Of course, this is for a general sort - for some kinds of applications,

    >
    > >> insertion sort is very well suited.

    >
    > >>

    >
    > >> Unless you meant that insert sort is as simple and better than bogosort...

    >
    > >

    >
    > >

    >
    > > No, ordinary insertion sort requires neither of those, and can sort an

    >
    > > array with no additional storage, just like bubble sort. The basic

    >
    > > idea is that you take each element and then move it back one spot at a

    >
    > > time in the array (by swapping with the prior element) until it's in

    >
    > > the correct spot. It's still O(n**2), but usually runs about twice as

    >
    > > fast as bubble sort, and the code is usually shorter too.

    >
    > >

    >
    > > for(i=1; i<N; i++)

    >
    > > for(j=i; j>0; j--)

    >
    > > {

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

    >
    > > swap(a[j-1], a[j]);

    >
    > > else

    >
    > > break;

    >
    > > }

    >
    >
    >
    > A simple change will speed this up significantly on most
    >
    > machines. The problem is with the swap() operation: It will
    >
    > exchange (for example) items [10] and [9], then [9] and [8],
    >
    > then [8] and [7] -- six memory writes to slide the original
    >
    > [10] element three places to the left. By holding the "moving"
    >
    > element in a temporary throughout, you can avoid almost half
    >
    > the writes:
    >
    >
    >
    > for (i = 1; i < N; ++i) {
    >
    > int temp = a;
    >
    > for (j = i; --j >= 0; ) {
    >
    > if (a[j] > temp)
    >
    > a[j+1] = a[j];
    >
    > else
    >
    > break;
    >
    > }
    >
    > a[j+1] = temp;
    >
    > }
    >
    >
    >
    > For the same rearrangement, this code loads temp from [10],
    >
    > then copies [9] to [10], [8] to [9], [7] to [8] and finally
    >
    > stores temp in [7] -- four writes instead of six. (Assuming
    >
    > that temp winds up in a register; if it doesn't, there'll
    >
    > be five writes instead of nine because swap() will need an
    >
    > additional internal write, too.)
    >
    >
    >
    > --
    >
    > Eric Sosman
    >
    > d

    I think the bubble sort is fast in sorting under 100 items.
    The quadratic behavior will dominate when the length of the list
    is large.
     
    88888 Dihedral, Mar 16, 2013
    #10
  11. BartC

    Ian Collins Guest

    David Brown wrote:
    >
    > Insert sort is not "as simple /and/ better" than bubblesort. To do an
    > efficient insertion sort (and it has to be efficient, or it is not
    > "better"), you need to use a binary search to find the insertion point
    > for each element, and you need to hold your elements in a linked list
    > rather than a static array (otherwise you need to move half your data
    > for every insertion, which is not "better").


    That perceived wisdom may not be true on modern hardware.

    The cost of searching and moving elements will probably be swamped by
    the cost of filling caches. So in practice, searching and shuffling
    data in an array will be significantly faster than doing the same with a
    "more efficient" disjoint structure like a linked list. Locality of
    reference trumps elegant theory every time!

    --
    Ian Collins
     
    Ian Collins, Mar 16, 2013
    #11
  12. BartC

    Nobody Guest

    On Sat, 16 Mar 2013 13:43:17 +0000, glen herrmannsfeldt wrote:

    > There is some discussion about Radix sort, and whether it is really O(N).
    > It is for fixed word size, but O() is supposed to be for limit as N goes
    > to infinity.


    Radix sort is O(n.log(N)), where n is the number of elements in the list
    and N is the number of elements in the set from which the list elements
    are drawn (i.e. log(N) is a measure of the size of an element).

    Whether radix sort is O(n) boils down to whether you treat N as a constant.

    E.g. you could write a function to radix sort strings, with the (worst
    case) number of passes proportional to the length of the longest string.
    Such a function would be O(m.n) where m is the length of the longest
    string, i.e. O(n.log(N)) where N = (2^m) = the cardinality of the set of
    strings of length m.
     
    Nobody, Mar 16, 2013
    #12
  13. BartC

    Öö Tiib Guest

    On Saturday, 16 March 2013 16:40:23 UTC+2, David Brown wrote:
    > Insert sort is not "as simple /and/ better" than bubblesort.


    Nonsense, insertion sort *is* bubble sort with pointless sequential
    swaps replaced with insert that is both cheaper and shorter.

    > To do an efficient insertion sort (and it has to be efficient, or it is not
    > "better"), you need to use a binary search to find the insertion point
    > for each element, and you need to hold your elements in a linked list
    > rather than a static array (otherwise you need to move half your data
    > for every insertion, which is not "better").


    You add complexity that does not win you much here. Always think and
    measure. Linked list is least efficient thing. If you go for dynamic
    structure then take red black tree.
     
    Öö Tiib, Mar 16, 2013
    #13
  14. David Brown <> wrote:

    (snip, someone wrote)
    >> but insert sort is as simple *and* better


    > Insert sort is not "as simple /and/ better" than bubblesort. To do an
    > efficient insertion sort (and it has to be efficient, or it is not
    > "better"), you need to use a binary search to find the insertion point
    > for each element, and you need to hold your elements in a linked list
    > rather than a static array (otherwise you need to move half your data
    > for every insertion, which is not "better").


    I haven't looked at the details recently, but the faster implementations
    of quicksort don't sort subarrays smaller than a given (small) size,
    then do an insertion sort on the whole array at the end. Seems to me
    that if you do linear search starting at the end that it is fast for
    an already almost sorted array.

    > Of course, this is for a general sort - for some kinds of applications,
    > insertion sort is very well suited.


    For an almost sorted array, both bubble sort and (some implementations
    of) insertion sort are fast.

    > Unless you meant that insert sort is as simple and better than bogosort...


    -- glen
     
    glen herrmannsfeldt, Mar 16, 2013
    #14
  15. Eric Sosman <> wrote:

    (snip)

    >> for(i=1; i<N; i++)
    >> for(j=i; j>0; j--)
    >> {
    >> if (a[j-1] > a[j])
    >> swap(a[j-1], a[j]);
    >> else
    >> break;
    >> }


    > A simple change will speed this up significantly on most
    > machines. The problem is with the swap() operation: It will
    > exchange (for example) items [10] and [9], then [9] and [8],
    > then [8] and [7] -- six memory writes to slide the original
    > [10] element three places to the left. By holding the "moving"
    > element in a temporary throughout, you can avoid almost half
    > the writes:


    Yes, but the cache might also figure that out. Or it might not.

    It is usual to study sort algorithms based on comparisons
    and stores, but that might not accurately indicate the time
    on real hardware. But much sort research was done before caching
    was common in processors, and even so it isn't easy to take
    into account.

    -- glen
     
    glen herrmannsfeldt, Mar 16, 2013
    #15
  16. pete <> wrote:
    > David Brown wrote:


    (snip)
    >> Insert sort is not "as simple /and/ better" than bubblesort. To do an
    >> efficient insertion sort (and it has to be efficient, or it is not
    >> "better"), you need to use a binary search to find the insertion point
    >> for each element, and you need to hold your elements in a linked list
    >> rather than a static array (otherwise you need to move half your data
    >> for every insertion, which is not "better").


    > No.
    > For insertion sort to be better than bubble sort,
    > it merely needs to be better than bubble sort in one way,
    > and not worse than bubble sort in any way.


    But you have to carefully define "way".

    > Insertion sort does less data comparisons
    > than bubble sort for the average case.
    > If insertion sort is implemented
    > with a temporary data variable,
    > then insertion sort can do less data movement than bubble sort.
    > If insertion sort is implemented as a swapping algorithm
    > then insertion sort does the same amount of data movement
    > as bubble sort.


    You are assuming that comparisons and stores are the only
    thing that count.

    Consider a highly parallel system with N (very simple)
    processors that can, on each clock cycle compare two
    elements, store one, and move one. I believe that you
    will find that the compare and swap pattern of bubblesort
    lends itself to highly parallel sorting better than
    insertion sort.

    > For data distributions when the running time
    > of insertion sort varies with (N*N),
    > the running time of binary insertion sort
    > also varies with (N*N),
    > because both algorithms
    > do about the same amount of data movement.


    But bubble sort has run time O(N) with
    O(N) processing units and neighbor to neighbor
    communication. I am not so sure about insertion
    sort.

    > There are certain data distributions
    > for which the running time of insertion sort
    > varies directly with N, where N is the number of
    > elements in the array, the running time of binary
    > insertion sort can never do better than to vary
    > directly with N*log(N).


    But again, it depends on the initial data ordering and
    also the hardware available.

    -- glen
     
    glen herrmannsfeldt, Mar 16, 2013
    #16
  17. On 16-Mar-13 14:41, Eric Sosman wrote:
    > On 3/16/2013 2:39 PM, Robert Wessel wrote:
    >> No, ordinary insertion sort requires neither of those, and can sort
    >> an array with no additional storage, just like bubble sort. The
    >> basic idea is that you take each element and then move it back one
    >> spot at a time in the array (by swapping with the prior element)
    >> until it's in the correct spot. It's still O(n**2), but usually
    >> runs about twice as fast as bubble sort, and the code is usually
    >> shorter too.

    >
    > A simple change will speed this up significantly on most machines.
    > The problem is with the swap() operation: It will exchange (for
    > example) items [10] and [9], then [9] and [8], then [8] and [7] --
    > six memory writes to slide the original [10] element three places to
    > the left. By holding the "moving" element in a temporary throughout,
    > you can avoid almost half the writes:


    Writes are effectively free, and have been for a long time. Reads are
    what kill performance, but an insertion sort (like a bubble sort)
    exhibits sufficient spatial locality to be exploited by even the dumbest
    cache predictor.

    OTOH, if the data set doesn't fit entirely in L1 cache, you're better
    off using a faster algorithm anyway for O(N^2) reasons.

    S

    --
    Stephen Sprunk "God does not play dice." --Albert Einstein
    CCIE #3723 "God is an inveterate gambler, and He throws the
    K5SSS dice at every possible opportunity." --Stephen Hawking
     
    Stephen Sprunk, Mar 16, 2013
    #17
  18. Nobody <> wrote:
    > On Sat, 16 Mar 2013 13:43:17 +0000, glen herrmannsfeldt wrote:


    >> There is some discussion about Radix sort, and whether it is really O(N).
    >> It is for fixed word size, but O() is supposed to be for limit as N goes
    >> to infinity.


    > Radix sort is O(n.log(N)), where n is the number of elements in the list
    > and N is the number of elements in the set from which the list elements
    > are drawn (i.e. log(N) is a measure of the size of an element).


    > Whether radix sort is O(n) boils down to whether you treat N as a constant.


    Yes. Some people believe that N should increase proportionally to n.
    In practical cases, that rarely happens.

    As far as I know, the most radix sorting was done on machines like:

    http://www.google.com/search?rls=en&q=ibm card sorter&

    As cards have a fixed width, there is a limit to N, while there is no
    well defined limit to n. (Possible MTBF, but even then it is easy to
    restart a sort after failure.)

    > E.g. you could write a function to radix sort strings, with the (worst
    > case) number of passes proportional to the length of the longest string.
    > Such a function would be O(m.n) where m is the length of the longest
    > string, i.e. O(n.log(N)) where N = (2^m) = the cardinality of the set of
    > strings of length m.


    -- glen
     
    glen herrmannsfeldt, Mar 16, 2013
    #18
  19. BartC

    Eric Sosman Guest

    On 3/16/2013 7:21 PM, glen herrmannsfeldt wrote:
    > Eric Sosman <> wrote:
    >
    > (snip)
    >
    >>> for(i=1; i<N; i++)
    >>> for(j=i; j>0; j--)
    >>> {
    >>> if (a[j-1] > a[j])
    >>> swap(a[j-1], a[j]);
    >>> else
    >>> break;
    >>> }

    >
    >> A simple change will speed this up significantly on most
    >> machines. The problem is with the swap() operation: It will
    >> exchange (for example) items [10] and [9], then [9] and [8],
    >> then [8] and [7] -- six memory writes to slide the original
    >> [10] element three places to the left. By holding the "moving"
    >> element in a temporary throughout, you can avoid almost half
    >> the writes:

    >
    > Yes, but the cache might also figure that out. Or it might not.
    >
    > It is usual to study sort algorithms based on comparisons
    > and stores, but that might not accurately indicate the time
    > on real hardware. But much sort research was done before caching
    > was common in processors, and even so it isn't easy to take
    > into account.


    That's why nice academic treatises on the asymptotic behavior
    of this or that algorithm are not as useful as their authors may
    wish you'd think.

    People count comparisons (or swaps) because it's easy, not
    because it's relevant. As you say, it used to be relevant, maybe
    twenty or twenty-five years ago -- but if you're using such counts
    to make performance decisions today, well, you're in the wrong
    century. "Memory is the new disk," says Cliff Click, pointing out
    that cache misses have supplanted page faults as the performance
    bugaboos of modern systems. As far as I know (which ain't all *that*
    far), modern computer scientists have not yet figured out how to
    treat the Memory Gotcha mathematically. Not satisfactorily, anyhow:
    The computational models all start with "Consider a spherical cow."

    Meanwhile, what's a practical programmer to do? You can write
    N different sort routines and measure their speed on the target
    hardware, but it'll turn out tomorrow's hardware favors a different
    implementation than today's. That's a losing game: "It takes all
    the running you can do, to keep in the same place." An approach
    with less certainty but (perhaps) greater hope is to try to put the
    least pressure on those parts of the system you imagine may be prone
    to slowness under stress. In the case at hand, we can hope that a
    cache (or caches, or write buffers, or magic) will deal with what
    looks like a lot of memory writes, or we can make fewer of them to
    begin with. Although there's no certainty, the latter approach seems
    to my mind to be less likely to come a cropper.

    --
    Eric Sosman
    d
     
    Eric Sosman, Mar 17, 2013
    #19
  20. BartC

    Eric Sosman Guest

    On 3/16/2013 7:11 PM, glen herrmannsfeldt wrote:
    > David Brown <> wrote:
    >
    > (snip, someone wrote)
    >>> but insert sort is as simple *and* better

    >
    >> Insert sort is not "as simple /and/ better" than bubblesort. To do an
    >> efficient insertion sort (and it has to be efficient, or it is not
    >> "better"), you need to use a binary search to find the insertion point
    >> for each element, and you need to hold your elements in a linked list
    >> rather than a static array (otherwise you need to move half your data
    >> for every insertion, which is not "better").

    >
    > I haven't looked at the details recently, but the faster implementations
    > of quicksort don't sort subarrays smaller than a given (small) size,
    > then do an insertion sort on the whole array at the end. [...]


    That was once true, but apparently is not true any more on many
    modern machines. Sorting the small sub-arrays as they appear instead
    of making one Grand Pass at the end exploits the fact that the arrays'
    data is likely to be in a close-to-the-CPU cache; leaving everything
    for a Final Sweep virtually guarantees that much of the data will have
    been evicted from cache before the Sweep touches it.

    --
    Eric Sosman
    d
     
    Eric Sosman, Mar 17, 2013
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mark Bluemel

    Re: How to arrange some numbers

    Mark Bluemel, Mar 15, 2013, in forum: C Programming
    Replies:
    0
    Views:
    194
    Mark Bluemel
    Mar 15, 2013
  2. Mark Bluemel

    Re: How to arrange some numbers

    Mark Bluemel, Mar 15, 2013, in forum: C Programming
    Replies:
    0
    Views:
    177
    Mark Bluemel
    Mar 15, 2013
  3. Keith Thompson

    Re: How to arrange some numbers

    Keith Thompson, Mar 15, 2013, in forum: C Programming
    Replies:
    4
    Views:
    196
    Malcolm McLean
    Mar 16, 2013
  4. Eric Sosman

    Re: How to arrange some numbers

    Eric Sosman, Mar 15, 2013, in forum: C Programming
    Replies:
    2
    Views:
    197
    osmium
    Mar 15, 2013
  5. Tim Rentsch

    Re: How to arrange some numbers

    Tim Rentsch, Mar 16, 2013, in forum: C Programming
    Replies:
    0
    Views:
    169
    Tim Rentsch
    Mar 16, 2013
Loading...

Share This Page