Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #143374 > unrolled thread

qsort() standard functions

Back to article view | Back to comp.lang.c

Contents

  qsort() standard functions rick.c.hodgin@gmail.com - 2019-04-24 09:08 -0700
    Re: qsort() standard functions gazelle@shell.xmission.com (Kenny McCormack) - 2019-04-24 16:12 +0000
      Re: qsort() standard functions rick.c.hodgin@gmail.com - 2019-04-24 09:18 -0700
        Re: qsort() standard functions Chad <cdalten@gmail.com> - 2019-05-02 12:02 -0700
      Re: qsort() standard functions Real Troll <real.troll@trolls.com> - 2019-04-24 22:30 -0400
        Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 19:32 -0700
          Re: qsort() standard functions Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-04-25 10:19 +0000
            Re: qsort() standard functions rick.c.hodgin@gmail.com - 2019-04-25 04:09 -0700
              Re: qsort() standard functions Richard Damon <Richard@Damon-Family.org> - 2019-04-25 08:13 -0400
                Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-25 06:39 -0700
                Re: qsort() standard functions already5chosen@yahoo.com - 2019-04-25 07:23 -0700
        Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-25 00:39 -0700
          Re: qsort() standard functions Real Troll <Real.Troll@Trolls.com> - 2019-04-25 23:27 +0100
    Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 09:34 -0700
      Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 09:47 -0700
      Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 09:47 -0700
        Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 12:54 -0400
          Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 11:33 -0700
            Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 14:41 -0400
              Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 11:52 -0700
                Re: qsort() standard functions gazelle@shell.xmission.com (Kenny McCormack) - 2019-04-24 19:12 +0000
                Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 16:05 -0400
                  Re: qsort() standard functions queequeg@trust.no1 (Queequeg) - 2019-04-24 20:39 +0000
              Re: qsort() standard functions James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-04-24 16:33 -0700
        Re: qsort() standard functions gazelle@shell.xmission.com (Kenny McCormack) - 2019-04-24 19:18 +0000
          Re: qsort() standard functions Bart <bc@freeuk.com> - 2019-04-24 20:28 +0100
            Re: qsort() standard functions gazelle@shell.xmission.com (Kenny McCormack) - 2019-04-24 21:27 +0000
          Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 12:31 -0700
          Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 13:02 -0700
            Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 13:41 -0700
              Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 14:00 -0700
                Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-25 00:22 +0300
                  Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 15:04 -0700
                    Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 15:20 -0700
                      Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 15:40 -0700
                        Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 15:57 -0700
                          Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 16:06 -0700
                            Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-25 23:49 +0300
                              Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-25 22:45 +0100
                                Re: qsort() standard functions Bart <bc@freeuk.com> - 2019-04-25 23:00 +0100
                                  Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-25 23:24 +0100
                                Re: qsort() standard functions Real Troll <Real.Troll@Trolls.com> - 2019-04-25 23:20 +0100
                                Re: qsort() standard functions Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-04-26 13:06 +0300
                                  Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-26 13:38 +0100
                                    Re: qsort() standard functions Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-04-26 16:43 +0300
                                      Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-26 17:46 +0100
                                        Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-27 14:55 +0300
                                          Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-27 14:59 +0100
                                            Re: qsort() standard functions Robert Wessel <robertwessel2@yahoo.com> - 2019-04-27 11:41 -0500
                                              Re: qsort() standard functions Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-05-02 09:46 -0700
                                                Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-02 20:35 +0300
                                                  Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-05-02 15:35 -0700
                                                    Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-05-05 04:39 -0700
                                                  Re: qsort() standard functions Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-05-04 07:35 -0700
                                                    Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-05 00:01 +0300
                                            Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-02 15:11 +0300
                                              Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-05-02 16:36 +0100
                                Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-27 14:47 +0300
                                  Re: qsort() standard functions Robert Wessel <robertwessel2@yahoo.com> - 2019-04-27 08:30 -0500
                                    Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-02 14:52 +0300
                                      Re: qsort() standard functions Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-05-04 07:13 -0700
                                        Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-05 22:57 +0300
                                          Re: qsort() standard functions David Brown <david.brown@hesbynett.no> - 2019-05-06 10:09 +0200
                                          Re: qsort() standard functions Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-06-01 05:22 -0700
                              Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-25 17:09 -0700
                                Re: qsort() standard functions Bart <bc@freeuk.com> - 2019-04-26 10:58 +0100
                                  Re: qsort() standard functions mark.bluemel@gmail.com - 2019-04-26 03:59 -0700
                                  Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 06:34 -0700
                                    Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 07:16 -0700
                                      Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 07:45 -0700
                                        Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 08:29 -0700
                                Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 12:06 -0700
                                  Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 13:09 -0700
                                    Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 13:37 -0700
                                      Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 14:05 -0700
                      Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-27 14:59 +0300
                        Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-27 06:19 -0700
                          Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-27 06:32 -0700
    Re: qsort() standard functions Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-04-24 10:54 -0600
      Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 10:10 -0700
      Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-25 00:06 +0300
    Re: qsort() standard functions scott@slp53.sl.home (Scott Lurndal) - 2019-04-24 17:37 +0000
      Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 10:56 -0700
        Re: qsort() standard functions Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-04-24 12:12 -0600
          Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 14:27 -0400
            Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 11:44 -0700
              Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 11:57 -0700
                Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 12:04 -0700
              Re: qsort() standard functions nobody@example.org (Scott) - 2019-04-25 01:16 +0000
                Re: qsort() standard functions James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-04-24 21:38 -0400
    Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 14:42 -0400
      Re: qsort() standard functions David Brown <david.brown@hesbynett.no> - 2019-04-24 22:13 +0200
      Re: qsort() standard functions queequeg@trust.no1 (Queequeg) - 2019-04-24 20:46 +0000
    Re: qsort() standard functions jadill33@gmail.com - 2019-04-24 14:01 -0700
    Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 15:41 -0700
    Re: qsort() standard functions "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-04-26 22:24 +0800
      Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-02 15:05 +0300
        Re: qsort() standard functions "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-05-03 17:02 +0800
          Re: qsort() standard functions Chad <cdalten@gmail.com> - 2019-05-03 10:10 -0700
            Re: qsort() standard functions "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-05-04 01:22 +0800
              Re: qsort() standard functions Chad <cdalten@gmail.com> - 2019-05-03 15:14 -0700
                [OT]Eternal.... programmer? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-05-04 06:20 +0800
                  Re: [OT]Eternal.... programmer? Chad <cdalten@gmail.com> - 2019-05-04 05:53 -0700

Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6  Next page →

#143591

Anton Shepelev <anton.txt@gmail.com> writes:

> Robert Wessel:
[...]
>> You've already dealt with the stack issue (although I
>> personally prefer the semi-recursive form, it's not a big
>> difference).
>
> You mean reliance of tail-call optimisation?  I dislike it
> for readability.  Recursive code is compiled into iterative
> machine code.  This is misleading.

I find this reaction rather quaint.  It reminds me of times when
oldtimers advised new programmers to use shifts and ands rather
than dividing or remaindering by a power of two.  Optimizing tail
calls, especially in cases like this one where the function is
calling itself, is one of the easiest transformations to make,
and any decent compiler will do so.  When will people get past
the idea that programming in C is like programming in assembly
language?  (Although, come to think of it, people understood
and used tail-call optimization quite routinely even back when
I was programming in assembly language nearly half a century
ago.)

Incidentally, I think Robert Wessel was not talking about
tail-call optimization but about recursing down the first
(shorter) side of the recurrence, and only the first side,
then looping for the longer side when the shorter call
returns.

[toc] | [prev] | [next] | [standalone]

#143619

Tim Rentsch to Anton Shepelev:

> > You mean reliance of tail-call optimisation?  I dislike
> > it for readability.  Recursive code is compiled into
> > iterative machine code.  This is misleading.
>
> I find this reaction rather quaint.  It reminds me of
> times when oldtimers advised new programmers to use shifts
> and ands rather than dividing or remaindering by a power
> of two.

Well, this is not the same.  If my purpose is to multiply an
integer by two and the operation is not part of a
performace-critical section of code, I will write:

                        a2 = a * 2;

`a2 = a >> 1' would only thwart readability because it would
express not the intent but a hardware-specific detail.  If,
however, my purpose is to shift a bit battern, I will write:

                      a_shf = a >> 1;

Code is written for the human reader and must reflect the
vision and intent of the programmer to facilitate
understanding.

If modern compilers automatically detect divisions and
multiplications by a power of two and replace them with
shifts it is actually very good because helps to keep code
human-oriented rather than machine-oriented.

> Optimizing tail calls, especially in cases like this one
> where the function is calling itself, is one of the
> easiest transformations to make, and any decent compiler
> will do so.

Similarly, I do not object if compilers perform tail-call
optimisation, for it lets the programmer not to rewrite
conceptually recursive code into a interative form,
sacrifing readability for performance.  But I find my
iterative implementation of QuickSort clearer than than the
"one-legged" version mixing recusion and iteration.  The
simplest form with two recursive calls is the most readable
but its stack usage is unfortunately not limited to log(n).

> When will people get past the idea that programming in C
> is like programming in assembly language?  (Although, come
> to think of it, people understood and used tail-call
> optimization quite routinely even back when I was
> programming in assembly language nearly half a century
> ago.)

C indeed is a lower-level language than Pascal and Modula,
because it mixes low-level and high-level features so
carelessly.  Even its `switch' operator has the architecture
of a jump table rather than of the structural control-flow
operator that it has in Pascal.  In general, C has high-
level control flow but low-level types, not even a complete
string or array type.

> Incidentally, I think Robert Wessel was not talking about
> tail-call optimization but about recursing down the first
> (shorter) side of the recurrence, and only the first side,
> then looping for the longer side when the shorter call
> returns.

OK.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#143631

On 05/05/2019 21:57, Anton Shepelev wrote:
> Tim Rentsch to Anton Shepelev:
> 
>>> You mean reliance of tail-call optimisation?  I dislike
>>> it for readability.  Recursive code is compiled into
>>> iterative machine code.  This is misleading.
>>
>> I find this reaction rather quaint.  It reminds me of
>> times when oldtimers advised new programmers to use shifts
>> and ands rather than dividing or remaindering by a power
>> of two.
> 
> Well, this is not the same.  If my purpose is to multiply an
> integer by two and the operation is not part of a
> performace-critical section of code, I will write:
> 
>                         a2 = a * 2;
> 
> `a2 = a >> 1' would only thwart readability because it would
> express not the intent but a hardware-specific detail.  If,
> however, my purpose is to shift a bit battern, I will write:
> 
>                       a_shf = a >> 1;
> 

(You have muddled the direction of the shift.  That is presumably not a
mistake you'd make in real code, but it does show how easy it is to make
mistakes when writing "hand optimized" code instead of aiming for the
clearest code for human readers.)

> Code is written for the human reader and must reflect the
> vision and intent of the programmer to facilitate
> understanding.

Exactly.  Let the compiler figure out the small details for generating
efficient code, so that the human can put effort into correctness and
high-level (algorithmic) efficiency.

> 
> If modern compilers automatically detect divisions and
> multiplications by a power of two and replace them with
> shifts it is actually very good because helps to keep code
> human-oriented rather than machine-oriented.

They do that, yes.  Division of signed integers by powers of two is not
quite as simple as a shift, but compilers handle the details (C division
is "truncate towards zero", while shift-division is "round towards minus
infinity".  And right-shift of negative numbers may vary for different
cpus).  Multiplication is just shift, on any cpu I have seen.  But
sometimes the cpu has more efficient ways to calculate this than shift
instructions (such as the x86's "lea" instruction).

Generally, it is best to write the operations in the "natural" human
form - multiplication or division - because it lets the compiler handle
the optimisation details suitable for the cpu you are using.  Compilers
can sometimes do a better job with more human-style code, because it can
give them more information.  (For example, if array accesses are "hand
optimised" to pointer arithmetic, the compiler may lose track of useful
information about the array and its dimensions.)

> 
>> Optimizing tail calls, especially in cases like this one
>> where the function is calling itself, is one of the
>> easiest transformations to make, and any decent compiler
>> will do so.
> 
> Similarly, I do not object if compilers perform tail-call
> optimisation, for it lets the programmer not to rewrite
> conceptually recursive code into a interative form,
> sacrifing readability for performance.  But I find my
> iterative implementation of QuickSort clearer than than the
> "one-legged" version mixing recusion and iteration.  The
> simplest form with two recursive calls is the most readable
> but its stack usage is unfortunately not limited to log(n).
> 

Aim first for readability and correctness - then you can refine it for
efficiency.  (And /test/ for efficiency, using realistic data - cache
effects can make it rather hard to predict run times.)  But I agree that
doing worse-case analysis can be harder when optimisations such as tail
recursion can make such a difference.

>> When will people get past the idea that programming in C
>> is like programming in assembly language?  (Although, come
>> to think of it, people understood and used tail-call
>> optimization quite routinely even back when I was
>> programming in assembly language nearly half a century
>> ago.)
> 
> C indeed is a lower-level language than Pascal and Modula,
> because it mixes low-level and high-level features so
> carelessly.  Even its `switch' operator has the architecture
> of a jump table rather than of the structural control-flow
> operator that it has in Pascal.  In general, C has high-
> level control flow but low-level types, not even a complete
> string or array type.

I view C as a high level language, because it is defined in terms of
specifications over an abstract machine, rather than in terms of the
underlying hardware.  But it is perhaps the lowest level mainstream high
level language (Forth is, I think, the possible alternative).  There is
always the "as if" rule - even though "switch" (and many other C
features) were designed to have simple implementations, they don't have
to be implemented that way.

Personally, I rely heavily on optimisations in the compiler in order to
write code in a "higher level" style - such as using multiplication and
division instead of shifts.  It is not uncommon for my programs to fail
to meet timing or code space requirements if compiled with optimisations
disabled.

> 
>> Incidentally, I think Robert Wessel was not talking about
>> tail-call optimization but about recursing down the first
>> (shorter) side of the recurrence, and only the first side,
>> then looping for the longer side when the shorter call
>> returns.
> 
> OK.
> 

[toc] | [prev] | [next] | [standalone]

#144264

Anton Shepelev <anton.txt@gmail.com> writes:

> Tim Rentsch to Anton Shepelev:
>
>>> You mean reliance of tail-call optimisation?  I dislike
>>> it for readability.  Recursive code is compiled into
>>> iterative machine code.  This is misleading.
>>
>> I find this reaction rather quaint.  It reminds me of
>> times when oldtimers advised new programmers to use shifts
>> and ands rather than dividing or remaindering by a power
>> of two.
>
> Well, this is not the same.  If my purpose is to multiply an
> integer by two and the operation is not part of a
> performace-critical section of code, I will write:
>
>                         a2 = a * 2;
>
> `a2 = a >> 1' would only thwart readability because it would
> express not the intent but a hardware-specific detail.  If,
> however, my purpose is to shift a bit battern, I will write:
>
>                       a_shf = a >> 1;
>
> Code is written for the human reader and must reflect the
> vision and intent of the programmer to facilitate
> understanding.

This statement is at odds with your idea of how to
write a quicksort function.

>> Optimizing tail calls, especially in cases like this one
>> where the function is calling itself, is one of the
>> easiest transformations to make, and any decent compiler
>> will do so.
>
> Similarly, I do not object if compilers perform tail-call
> optimisation, for it lets the programmer not to rewrite
> conceptually recursive code into a interative form,
> sacrifing readability for performance.  But I find my
> iterative implementation of QuickSort clearer than than the
> "one-legged" version mixing recusion and iteration.  The
> simplest form with two recursive calls is the most readable
> but its stack usage is unfortunately not limited to log(n).

It will be, with a simple test for which branch to do
first, in the presence of tail-call optimization.  Any
decent compiler will effect the tail-call optimization
in an easy case like this one.

[toc] | [prev] | [next] | [standalone]

#143446

W dniu czwartek, 25 kwietnia 2019 22:50:05 UTC+2 użytkownik Anton Shepelev napisał:
> fir:
> 
> > i see maybe your code do this same 9but with no elanation)
> > (introductions and explanations are important as nobody
> > likes guessing - i dont like it)
> >
> > now im to sleepy, but eventually mau check it tomorow
> > (yawn)
> 
> #include <stdio.h>
> #include <stdlib.h>
> #include <time.h>
> #include "sort.h"
> 
> void print( int * a, int n )
> {  int i;
>    for( i = 0; i < n; i++ )
>       printf("%i ", a[i] );
>    printf("\n");
> }
> 
> /* comparison function: */
> int comp( void * data, int i, int j )
> {  return ( (int*)data )[i] -
>           ( (int*)data )[j];
> }
> 
> /* comparison function for standard qsort: */
> compar(const void * a, void * b)
> {  return *((int*)a) - *((int*)b);
> }
> 
> /* swap function: */
> void swap( void * data, int i, int j )
> {  int buf;
>    buf = ( (int[])data )[i];
>    ( (int*)data )[i] = ( (int*)data )[j];
>    ( (int*)data )[j] = buf;
> }
> 
> #define testlen 2500
> void test()
> {  int a[testlen], c[testlen];
>    int i, j;
>    clock_t st, tot;
>    tot = 0;
>    for( i = 0; i < 1000; i++ )
>    {  for( j = 0; j < testlen; j++ )
>       {  a[j] = rand() % 5;
>          c[j] = a[j];
>       }
>       st = clock();
>       //qsort( a, testlen, sizeof(int), &compar );
>       sort( a, testlen, &comp, &swap, NULL );
>       tot = tot + clock() - st;  
>       for( j = 0; j < testlen-1; j++ )
>       {  if( a[j] > a[j+1] )
>          {  print( c, testlen );
>             print( a, testlen );
>             return;
>          }
>       }
>    }
>    printf("Time: %f\n", (float)tot / CLOCKS_PER_SEC );
> }
> 
> #define len 2
> int main( int argc, char** argv )
> {  /*int ta[5] = {7,8,9,10,2};*/
>    /*int ta[5] = {9,8,8,9,7};*/
> 
>    test();
>    return 0;
> 
>    int ta[len] = {2,1};
>    int pr;
>    print( ta, len );
>    sort( ta, len, &comp, &swap, NULL );
>    print( ta, len );
> }

i was being making some experiments in writing quicksort in a simple looking way 
that i would like and encountered soem problem

int SwipePartition (int* table, int lo, int hi)
{
    int i = lo;
    int j = hi;

    int pivot =  table[(lo+hi)/2];

    while (1)
    {

           while ( table[i] < pivot ) i++;
           while ( table[j] > pivot ) j--;


            if (i < j)
            {
                int t  = table[i]; table[i] = table[j]; table[j] = t;
            }
            else
            {
                return i;
            }
    }



}



void QuickSort(int* table, int lo, int hi)
{
    if (lo < hi)
    {
         int pivot = SwipePartition(table, lo, hi);

          QuickSort(table, lo, pivot-1);
          QuickSort(table, pivot+1, hi);
    }
}


this above looks simple like i would like
it eventually look like, but it only works if values to sort do noyt repeat , othervise it hangs (comes in infinite loop)

the question is how to simply add something to make it work in general?


when values do not reapat this partition works obviously like that

say pivot value is 100

(less then 100 here) 100 (bigger than 100 here)


if values repeat it will get that state

(less then 100 here) 100 (various) 100 (bigger than 100 here)

what simple i should add to go thry such situation?

[toc] | [prev] | [next] | [standalone]

#143447

On 26/04/2019 01:09, fir wrote:

> i was being making some experiments in writing quicksort in a simple looking way
> that i would like and encountered soem problem

> void QuickSort(int* table, int lo, int hi)
> {
>      if (lo < hi)
>      {
>           int pivot = SwipePartition(table, lo, hi);
> 
>            QuickSort(table, lo, pivot-1);
>            QuickSort(table, pivot+1, hi);
>      }
> }


What happened to not using recursion and not using a stack?

[toc] | [prev] | [next] | [standalone]

#143450

On Friday, 26 April 2019 10:58:59 UTC+1, Bart  wrote:
> On 26/04/2019 01:09, fir wrote:
> 
> > i was being making some experiments in writing quicksort in a simple looking way
> > that i would like and encountered soem problem
> 
> > void QuickSort(int* table, int lo, int hi)
> > {
> >      if (lo < hi)
> >      {
> >           int pivot = SwipePartition(table, lo, hi);
> > 
> >            QuickSort(table, lo, pivot-1);
> >            QuickSort(table, pivot+1, hi);
> >      }
> > }
> 
> 
> What happened to not using recursion and not using a stack?

That was in the past, Professor fir cannot be expected to stick to outdated,
bourgeois concepts of consistency (or even comprehensibility).

[toc] | [prev] | [next] | [standalone]

#143457

W dniu piątek, 26 kwietnia 2019 11:58:59 UTC+2 użytkownik Bart napisał:
> On 26/04/2019 01:09, fir wrote:
> 
> > i was being making some experiments in writing quicksort in a simple looking way
> > that i would like and encountered soem problem
> 
> > void QuickSort(int* table, int lo, int hi)
> > {
> >      if (lo < hi)
> >      {
> >           int pivot = SwipePartition(table, lo, hi);
> > 
> >            QuickSort(table, lo, pivot-1);
> >            QuickSort(table, pivot+1, hi);
> >      }
> > }
> 
> 
> What happened to not using recursion and not using a stack?

lol, tell me what could happen? nothing

recursive version id first step, non recursive is advance 

(at least it should be but need some tests, too)

(as i dont want to repaste it from the net strictly, i want to cook out more personal form... hiovever as i said i need it to work when 'piviot' (honestly i dodnt know what that word mean i not checked it even in dictionary yet) repeats, 

it coul seen that when i just turn one < into <= and one i into j it could work but it not, i must have some bug in it then.. but i cannot checkit until sunset
(dont like to code when to much sun sunlits the screen)

[toc] | [prev] | [next] | [standalone]

#143459

W dniu piątek, 26 kwietnia 2019 15:34:47 UTC+2 użytkownik fir napisał:
> W dniu piątek, 26 kwietnia 2019 11:58:59 UTC+2 użytkownik Bart napisał:
> > On 26/04/2019 01:09, fir wrote:
> > 
> > > i was being making some experiments in writing quicksort in a simple looking way
> > > that i would like and encountered soem problem
> > 
> > > void QuickSort(int* table, int lo, int hi)
> > > {
> > >      if (lo < hi)
> > >      {
> > >           int pivot = SwipePartition(table, lo, hi);
> > > 
> > >            QuickSort(table, lo, pivot-1);
> > >            QuickSort(table, pivot+1, hi);
> > >      }
> > > }
> > 
> > 
> > What happened to not using recursion and not using a stack?
> 
> lol, tell me what could happen? nothing
> 
> recursive version id first step, non recursive is advance 
> 
> (at least it should be but need some tests, too)
> 
> (as i dont want to repaste it from the net strictly, i want to cook out more personal form... hiovever as i said i need it to work when 'piviot' (honestly i dodnt know what that word mean i not checked it even in dictionary yet) repeats, 
> 
> it coul seen that when i just turn one < into <= and one i into j it could work but it not, i must have some bug in it then.. but i cannot checkit until sunset
> (dont like to code when to much sun sunlits the screen)

btw the console loging of values of this code above when no values repeat




 pivot = 15 
 partition:  10 20 5 4 3 88 99 15 2 101 300 16 410 11 12
 partition swiped:  10 12 5 4 3 11 2 15 99 101 300 16 410 88 20
 whole table: 10 12 5 4 3 11 2 15 99 101 300 16 410 88 20

 pivot = 4 
 partition:  10 12 5 4 3 11 2
 partition swiped:  2 3 4 5 12 11 10
 whole table: 2 3 4 5 12 11 10 15 99 101 300 16 410 88 20

 pivot = 2 
 partition:  2 3
 partition swiped:  2 3
 whole table: 2 3 4 5 12 11 10 15 99 101 300 16 410 88 20

 pivot = 12 
 partition:  5 12 11 10
 partition swiped:  5 10 11 12
 whole table: 2 3 4 5 10 11 12 15 99 101 300 16 410 88 20

 pivot = 10 
 partition:  5 10 11
 partition swiped:  5 10 11
 whole table: 2 3 4 5 10 11 12 15 99 101 300 16 410 88 20

 pivot = 16 
 partition:  99 101 300 16 410 88 20
 partition swiped:  16 101 300 99 410 88 20
 whole table: 2 3 4 5 10 11 12 15 16 101 300 99 410 88 20

 pivot = 99 
 partition:  101 300 99 410 88 20
 partition swiped:  20 88 99 410 300 101
 whole table: 2 3 4 5 10 11 12 15 16 20 88 99 410 300 101

 pivot = 20 
 partition:  20 88
 partition swiped:  20 88
 whole table: 2 3 4 5 10 11 12 15 16 20 88 99 410 300 101

 pivot = 300 
 partition:  410 300 101
 partition swiped:  101 300 410
 whole table: 2 3 4 5 10 11 12 15 16 20 88 99 101 300 410


i not checked it how it llook like when repeat

[toc] | [prev] | [next] | [standalone]

#143461

W dniu piątek, 26 kwietnia 2019 16:17:18 UTC+2 użytkownik fir napisał:
> W dniu piątek, 26 kwietnia 2019 15:34:47 UTC+2 użytkownik fir napisał:
> > W dniu piątek, 26 kwietnia 2019 11:58:59 UTC+2 użytkownik Bart napisał:
> > > On 26/04/2019 01:09, fir wrote:
> > > 
> > > > i was being making some experiments in writing quicksort in a simple looking way
> > > > that i would like and encountered soem problem
> > > 
> > > > void QuickSort(int* table, int lo, int hi)
> > > > {
> > > >      if (lo < hi)
> > > >      {
> > > >           int pivot = SwipePartition(table, lo, hi);
> > > > 
> > > >            QuickSort(table, lo, pivot-1);
> > > >            QuickSort(table, pivot+1, hi);
> > > >      }
> > > > }
> > > 
> > > 
> > > What happened to not using recursion and not using a stack?
> > 
> > lol, tell me what could happen? nothing
> > 
> > recursive version id first step, non recursive is advance 
> > 
> > (at least it should be but need some tests, too)
> > 
> > (as i dont want to repaste it from the net strictly, i want to cook out more personal form... hiovever as i said i need it to work when 'piviot' (honestly i dodnt know what that word mean i not checked it even in dictionary yet) repeats, 
> > 
> > it coul seen that when i just turn one < into <= and one i into j it could work but it not, i must have some bug in it then.. but i cannot checkit until sunset
> > (dont like to code when to much sun sunlits the screen)
> 
> btw the console loging of values of this code above when no values repeat
> 
> 
> 
> 
>  pivot = 15 
>  partition:  10 20 5 4 3 88 99 15 2 101 300 16 410 11 12
>  partition swiped:  10 12 5 4 3 11 2 15 99 101 300 16 410 88 20
>  whole table: 10 12 5 4 3 11 2 15 99 101 300 16 410 88 20
> 
>  pivot = 4 
>  partition:  10 12 5 4 3 11 2
>  partition swiped:  2 3 4 5 12 11 10
>  whole table: 2 3 4 5 12 11 10 15 99 101 300 16 410 88 20
> 
>  pivot = 2 
>  partition:  2 3
>  partition swiped:  2 3
>  whole table: 2 3 4 5 12 11 10 15 99 101 300 16 410 88 20
> 
>  pivot = 12 
>  partition:  5 12 11 10
>  partition swiped:  5 10 11 12
>  whole table: 2 3 4 5 10 11 12 15 99 101 300 16 410 88 20
> 
>  pivot = 10 
>  partition:  5 10 11
>  partition swiped:  5 10 11
>  whole table: 2 3 4 5 10 11 12 15 99 101 300 16 410 88 20
> 
>  pivot = 16 
>  partition:  99 101 300 16 410 88 20
>  partition swiped:  16 101 300 99 410 88 20
>  whole table: 2 3 4 5 10 11 12 15 16 101 300 99 410 88 20
> 
>  pivot = 99 
>  partition:  101 300 99 410 88 20
>  partition swiped:  20 88 99 410 300 101
>  whole table: 2 3 4 5 10 11 12 15 16 20 88 99 410 300 101
> 
>  pivot = 20 
>  partition:  20 88
>  partition swiped:  20 88
>  whole table: 2 3 4 5 10 11 12 15 16 20 88 99 410 300 101
> 
>  pivot = 300 
>  partition:  410 300 101
>  partition swiped:  101 300 410
>  whole table: 2 3 4 5 10 11 12 15 16 20 88 99 101 300 410
> 
> 
> i not checked it how it llook like when repeat

seems i found the reason of it not working in case of <=

it is becouse, if you will say partition like that

5 12 11 10

and pivit is 12 then in case of <= swipe will do totaly nothing

at the moment i dont know yet what to do with it

[toc] | [prev] | [next] | [standalone]

#143464

W dniu piątek, 26 kwietnia 2019 16:45:53 UTC+2 użytkownik fir napisał:
> W dniu piątek, 26 kwietnia 2019 16:17:18 UTC+2 użytkownik fir napisał:
> > W dniu piątek, 26 kwietnia 2019 15:34:47 UTC+2 użytkownik fir napisał:
> > > W dniu piątek, 26 kwietnia 2019 11:58:59 UTC+2 użytkownik Bart napisał:
> > > > On 26/04/2019 01:09, fir wrote:
> > > > 
> > > > > i was being making some experiments in writing quicksort in a simple looking way
> > > > > that i would like and encountered soem problem
> > > > 
> > > > > void QuickSort(int* table, int lo, int hi)
> > > > > {
> > > > >      if (lo < hi)
> > > > >      {
> > > > >           int pivot = SwipePartition(table, lo, hi);
> > > > > 
> > > > >            QuickSort(table, lo, pivot-1);
> > > > >            QuickSort(table, pivot+1, hi);
> > > > >      }
> > > > > }
> > > > 
> > > > 
> > > > What happened to not using recursion and not using a stack?
> > > 
> > > lol, tell me what could happen? nothing
> > > 
> > > recursive version id first step, non recursive is advance 
> > > 
> > > (at least it should be but need some tests, too)
> > > 
> > > (as i dont want to repaste it from the net strictly, i want to cook out more personal form... hiovever as i said i need it to work when 'piviot' (honestly i dodnt know what that word mean i not checked it even in dictionary yet) repeats, 
> > > 
> > > it coul seen that when i just turn one < into <= and one i into j it could work but it not, i must have some bug in it then.. but i cannot checkit until sunset
> > > (dont like to code when to much sun sunlits the screen)
> > 
> > btw the console loging of values of this code above when no values repeat
> > 
> > 
> > 
> > 
> >  pivot = 15 
> >  partition:  10 20 5 4 3 88 99 15 2 101 300 16 410 11 12
> >  partition swiped:  10 12 5 4 3 11 2 15 99 101 300 16 410 88 20
> >  whole table: 10 12 5 4 3 11 2 15 99 101 300 16 410 88 20
> > 
> >  pivot = 4 
> >  partition:  10 12 5 4 3 11 2
> >  partition swiped:  2 3 4 5 12 11 10
> >  whole table: 2 3 4 5 12 11 10 15 99 101 300 16 410 88 20
> > 
> >  pivot = 2 
> >  partition:  2 3
> >  partition swiped:  2 3
> >  whole table: 2 3 4 5 12 11 10 15 99 101 300 16 410 88 20
> > 
> >  pivot = 12 
> >  partition:  5 12 11 10
> >  partition swiped:  5 10 11 12
> >  whole table: 2 3 4 5 10 11 12 15 99 101 300 16 410 88 20
> > 
> >  pivot = 10 
> >  partition:  5 10 11
> >  partition swiped:  5 10 11
> >  whole table: 2 3 4 5 10 11 12 15 99 101 300 16 410 88 20
> > 
> >  pivot = 16 
> >  partition:  99 101 300 16 410 88 20
> >  partition swiped:  16 101 300 99 410 88 20
> >  whole table: 2 3 4 5 10 11 12 15 16 101 300 99 410 88 20
> > 
> >  pivot = 99 
> >  partition:  101 300 99 410 88 20
> >  partition swiped:  20 88 99 410 300 101
> >  whole table: 2 3 4 5 10 11 12 15 16 20 88 99 410 300 101
> > 
> >  pivot = 20 
> >  partition:  20 88
> >  partition swiped:  20 88
> >  whole table: 2 3 4 5 10 11 12 15 16 20 88 99 410 300 101
> > 
> >  pivot = 300 
> >  partition:  410 300 101
> >  partition swiped:  101 300 410
> >  whole table: 2 3 4 5 10 11 12 15 16 20 88 99 101 300 410
> > 
> > 
> > i not checked it how it llook like when repeat
> 
> seems i found the reason of it not working in case of <=
> 
> it is becouse, if you will say partition like that
> 
> 5 12 11 10
> 
> and pivit is 12 then in case of <= swipe will do totaly nothing
> 
> at the moment i dont know yet what to do with it

seems possibly different approch should be taken, this swipe partition works like swap-swap-swap-swap-swap-swap till both cursors hit

as i said it stops when it mets two pivot values - as swaping this dont do nothing, also ignoring them seem to be bad.. (???) in fact im not sure maybe ignoring them would be ok? must check it yet

[toc] | [prev] | [next] | [standalone]

#143471

W dniu piątek, 26 kwietnia 2019 02:09:53 UTC+2 użytkownik fir napisał:
> W dniu czwartek, 25 kwietnia 2019 22:50:05 UTC+2 użytkownik Anton Shepelev napisał:
> > fir:
> > 
> > > i see maybe your code do this same 9but with no elanation)
> > > (introductions and explanations are important as nobody
> > > likes guessing - i dont like it)
> > >
> > > now im to sleepy, but eventually mau check it tomorow
> > > (yawn)
> > 
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <time.h>
> > #include "sort.h"
> > 
> > void print( int * a, int n )
> > {  int i;
> >    for( i = 0; i < n; i++ )
> >       printf("%i ", a[i] );
> >    printf("\n");
> > }
> > 
> > /* comparison function: */
> > int comp( void * data, int i, int j )
> > {  return ( (int*)data )[i] -
> >           ( (int*)data )[j];
> > }
> > 
> > /* comparison function for standard qsort: */
> > compar(const void * a, void * b)
> > {  return *((int*)a) - *((int*)b);
> > }
> > 
> > /* swap function: */
> > void swap( void * data, int i, int j )
> > {  int buf;
> >    buf = ( (int[])data )[i];
> >    ( (int*)data )[i] = ( (int*)data )[j];
> >    ( (int*)data )[j] = buf;
> > }
> > 
> > #define testlen 2500
> > void test()
> > {  int a[testlen], c[testlen];
> >    int i, j;
> >    clock_t st, tot;
> >    tot = 0;
> >    for( i = 0; i < 1000; i++ )
> >    {  for( j = 0; j < testlen; j++ )
> >       {  a[j] = rand() % 5;
> >          c[j] = a[j];
> >       }
> >       st = clock();
> >       //qsort( a, testlen, sizeof(int), &compar );
> >       sort( a, testlen, &comp, &swap, NULL );
> >       tot = tot + clock() - st;  
> >       for( j = 0; j < testlen-1; j++ )
> >       {  if( a[j] > a[j+1] )
> >          {  print( c, testlen );
> >             print( a, testlen );
> >             return;
> >          }
> >       }
> >    }
> >    printf("Time: %f\n", (float)tot / CLOCKS_PER_SEC );
> > }
> > 
> > #define len 2
> > int main( int argc, char** argv )
> > {  /*int ta[5] = {7,8,9,10,2};*/
> >    /*int ta[5] = {9,8,8,9,7};*/
> > 
> >    test();
> >    return 0;
> > 
> >    int ta[len] = {2,1};
> >    int pr;
> >    print( ta, len );
> >    sort( ta, len, &comp, &swap, NULL );
> >    print( ta, len );
> > }
> 
> i was being making some experiments in writing quicksort in a simple looking way 
> that i would like and encountered soem problem
> 
> int SwipePartition (int* table, int lo, int hi)
> {
>     int i = lo;
>     int j = hi;
> 
>     int pivot =  table[(lo+hi)/2];
> 
>     while (1)
>     {
> 
>            while ( table[i] < pivot ) i++;
>            while ( table[j] > pivot ) j--;
> 
> 
>             if (i < j)
>             {
>                 int t  = table[i]; table[i] = table[j]; table[j] = t;
>             }
>             else
>             {
>                 return i;
>             }
>     }
> 
> 
> 
> }
> 
> 
> 
> void QuickSort(int* table, int lo, int hi)
> {
>     if (lo < hi)
>     {
>          int pivot = SwipePartition(table, lo, hi);
> 
>           QuickSort(table, lo, pivot-1);
>           QuickSort(table, pivot+1, hi);
>     }
> }
> 
> 
> this above looks simple like i would like
> it eventually look like, but it only works if values to sort do noyt repeat , othervise it hangs (comes in infinite loop)
> 
> the question is how to simply add something to make it work in general?
> 
> 
> when values do not reapat this partition works obviously like that
> 
> say pivot value is 100
> 
> (less then 100 here) 100 (bigger than 100 here)
> 
> 
> if values repeat it will get that state
> 
> (less then 100 here) 100 (various) 100 (bigger than 100 here)
> 
> what simple i should add to go thry such situation?

i also noted i may write alternative version to this above as


int SwipePartition (int* table, int lo, int hi)
{
    int i = lo;
    int j = hi;

    int pivot =  table[(lo+hi)/2];

    while (i<j)
    {
     if(table[i] < pivot) { i++; continue; }
     if(table[j] > pivot) { j--; continue; }

     swap(&table[i], &table[j]);
     }

     return j;
}

this is alos that that only work if values do not repeat

finding how to mend it to work with all seem to take me longer than i though

those are weird pieces of code, i mean such pieces that are short but hard to reason (?) about

[toc] | [prev] | [next] | [standalone]

#143473

W dniu piątek, 26 kwietnia 2019 21:07:18 UTC+2 użytkownik fir napisał:
> W dniu piątek, 26 kwietnia 2019 02:09:53 UTC+2 użytkownik fir napisał:
> > W dniu czwartek, 25 kwietnia 2019 22:50:05 UTC+2 użytkownik Anton Shepelev napisał:
> > > fir:
> > > 
> > > > i see maybe your code do this same 9but with no elanation)
> > > > (introductions and explanations are important as nobody
> > > > likes guessing - i dont like it)
> > > >
> > > > now im to sleepy, but eventually mau check it tomorow
> > > > (yawn)
> > > 
> > > #include <stdio.h>
> > > #include <stdlib.h>
> > > #include <time.h>
> > > #include "sort.h"
> > > 
> > > void print( int * a, int n )
> > > {  int i;
> > >    for( i = 0; i < n; i++ )
> > >       printf("%i ", a[i] );
> > >    printf("\n");
> > > }
> > > 
> > > /* comparison function: */
> > > int comp( void * data, int i, int j )
> > > {  return ( (int*)data )[i] -
> > >           ( (int*)data )[j];
> > > }
> > > 
> > > /* comparison function for standard qsort: */
> > > compar(const void * a, void * b)
> > > {  return *((int*)a) - *((int*)b);
> > > }
> > > 
> > > /* swap function: */
> > > void swap( void * data, int i, int j )
> > > {  int buf;
> > >    buf = ( (int[])data )[i];
> > >    ( (int*)data )[i] = ( (int*)data )[j];
> > >    ( (int*)data )[j] = buf;
> > > }
> > > 
> > > #define testlen 2500
> > > void test()
> > > {  int a[testlen], c[testlen];
> > >    int i, j;
> > >    clock_t st, tot;
> > >    tot = 0;
> > >    for( i = 0; i < 1000; i++ )
> > >    {  for( j = 0; j < testlen; j++ )
> > >       {  a[j] = rand() % 5;
> > >          c[j] = a[j];
> > >       }
> > >       st = clock();
> > >       //qsort( a, testlen, sizeof(int), &compar );
> > >       sort( a, testlen, &comp, &swap, NULL );
> > >       tot = tot + clock() - st;  
> > >       for( j = 0; j < testlen-1; j++ )
> > >       {  if( a[j] > a[j+1] )
> > >          {  print( c, testlen );
> > >             print( a, testlen );
> > >             return;
> > >          }
> > >       }
> > >    }
> > >    printf("Time: %f\n", (float)tot / CLOCKS_PER_SEC );
> > > }
> > > 
> > > #define len 2
> > > int main( int argc, char** argv )
> > > {  /*int ta[5] = {7,8,9,10,2};*/
> > >    /*int ta[5] = {9,8,8,9,7};*/
> > > 
> > >    test();
> > >    return 0;
> > > 
> > >    int ta[len] = {2,1};
> > >    int pr;
> > >    print( ta, len );
> > >    sort( ta, len, &comp, &swap, NULL );
> > >    print( ta, len );
> > > }
> > 
> > i was being making some experiments in writing quicksort in a simple looking way 
> > that i would like and encountered soem problem
> > 
> > int SwipePartition (int* table, int lo, int hi)
> > {
> >     int i = lo;
> >     int j = hi;
> > 
> >     int pivot =  table[(lo+hi)/2];
> > 
> >     while (1)
> >     {
> > 
> >            while ( table[i] < pivot ) i++;
> >            while ( table[j] > pivot ) j--;
> > 
> > 
> >             if (i < j)
> >             {
> >                 int t  = table[i]; table[i] = table[j]; table[j] = t;
> >             }
> >             else
> >             {
> >                 return i;
> >             }
> >     }
> > 
> > 
> > 
> > }
> > 
> > 
> > 
> > void QuickSort(int* table, int lo, int hi)
> > {
> >     if (lo < hi)
> >     {
> >          int pivot = SwipePartition(table, lo, hi);
> > 
> >           QuickSort(table, lo, pivot-1);
> >           QuickSort(table, pivot+1, hi);
> >     }
> > }
> > 
> > 
> > this above looks simple like i would like
> > it eventually look like, but it only works if values to sort do noyt repeat , othervise it hangs (comes in infinite loop)
> > 
> > the question is how to simply add something to make it work in general?
> > 
> > 
> > when values do not reapat this partition works obviously like that
> > 
> > say pivot value is 100
> > 
> > (less then 100 here) 100 (bigger than 100 here)
> > 
> > 
> > if values repeat it will get that state
> > 
> > (less then 100 here) 100 (various) 100 (bigger than 100 here)
> > 
> > what simple i should add to go thry such situation?
> 
> i also noted i may write alternative version to this above as
> 
> 
> int SwipePartition (int* table, int lo, int hi)
> {
>     int i = lo;
>     int j = hi;
> 
>     int pivot =  table[(lo+hi)/2];
> 
>     while (i<j)
>     {
>      if(table[i] < pivot) { i++; continue; }
>      if(table[j] > pivot) { j--; continue; }
> 
>      swap(&table[i], &table[j]);
>      }
> 
>      return j;
> }
> 
> this is alos that that only work if values do not repeat
> 
> finding how to mend it to work with all seem to take me longer than i though
> 
> those are weird pieces of code, i mean such pieces that are short but hard to reason (?) about

ok it seems that this work


int SwipePartition (int* table, int lo, int hi)
{

    int i = lo;
    int j = hi;

    int pivot =  table[(lo+hi)/2];

    while (i<j)
    {

     if(table[j] > pivot) { j--; continue; }
     if(table[i] < pivot) { i++; continue; }

      if( table[j]==pivot && table[i]>pivot
       || table[i]==pivot && table[j]<pivot)
      {
        swap(&table[i], &table[j]); continue;
      }


     if(table[i]==pivot && table[j]==pivot)
     {
         if(j-i==1) break;
         swap(&table[i], &table[--j]);
         continue;
     }

     swap(&table[i], &table[j]);

     }

     return j;

}
which in turn selfreduces to

int SwipePartition (int* table, int lo, int hi)
{
    int i = lo;
    int j = hi;

    int pivot =  table[(lo+hi)/2];

    while (i<j)
    {

     if(table[j] > pivot) { j--; continue; }
     if(table[i] < pivot) { i++; continue; }


     if(table[i]==pivot && table[j]==pivot)
     {
         if(j-i==1) break;
         swap(&table[i], &table[j-1]);
         j--;
         continue;
     }

     swap(&table[i], &table[j]);

     }

     return j;
}

i didnt check it much but it seem to work

thi is the question iof this is simplest form,probably no, but this is a bit tiresome to optimise such things

doesnt look terribly but its probably not optimal

[toc] | [prev] | [next] | [standalone]

#143474

damn i dont know if i do some stupid mistake becouse of tirednes or just that simply works ?

inline void swap(int* a, int* b)
{
   int t = *a; *a=*b; *b=t;
}

inline int SwipePartition (int* table, int lo, int hi)
{

    int i = lo;
    int j = hi;

    int pivot =  table[(lo+hi)/2];

    while (i<j)
    {
     if(table[j] >= pivot) { j--; continue; }
     if(table[i] < pivot) { i++; continue; }

     swap(&table[i], &table[j]);
     }

     return j;
}


void QuickSort(int* table, int lo, int hi)
{
    if (lo < hi)
    {
         int pivot = SwipePartition(table, lo, hi);

          QuickSort(table, lo, pivot-1);
          QuickSort(table, pivot+1, hi);
    }
}

[toc] | [prev] | [next] | [standalone]

#143476

in compact form it is

void QuickSortInts(int* tab, int lo, int hi)
{
    if(lo<hi)
    {
     int i=lo, j=hi, p=tab[(lo+hi)/2];

     while (i<j)
     {
      if(tab[j]>=p) {j--; continue;}
      if(tab[i]< p) {i++; continue;}
      int t=tab[i]; tab[i]=tab[j]; tab[j]=t;
     }

      QuickSortInts(tab, lo, j-1);
      QuickSortInts(tab, j+1, hi);
    }
}

still im not sure if i didnt do some mistake becouse of tiredenes, as it previously like not worked


well i see in net they go to soemething like taht too, (though some i see are a bit worse than that) so this probably is ok

[toc] | [prev] | [next] | [standalone]

#143486

fir:

> besides wat is the idea - roughly looking i doubt if it
> will work 9hovever id ont readed into it longer than few
> minutes and odnt know what some ariables mean, like q

The only variable with a totally non-intuitive name.
Renamed to `d' for stack depth.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#143489

W dniu sobota, 27 kwietnia 2019 13:59:17 UTC+2 użytkownik Anton Shepelev napisał:
> fir:
> 
> > besides wat is the idea - roughly looking i doubt if it
> > will work 9hovever id ont readed into it longer than few
> > minutes and odnt know what some ariables mean, like q
> 
> The only variable with a totally non-intuitive name.
> Renamed to `d' for stack depth.
> 

your code didnt seem to much readable to me, though i dont say also its bad..its a mater of style

if you do time measurigh test you could comepare your versions wiyth those of my

recurence version:


void QuickSortInts(int* tab, int lo, int hi)
{
    if(lo<hi)
    {
     int i=lo, j=hi, p=tab[(lo+hi)/2];

     while (i<j)
     {
      if(tab[j]>=p) {j--; continue;}
      if(tab[i]< p) {i++; continue;}
      int t=tab[i]; tab[i]=tab[j]; tab[j]=t;
     }

      QuickSortInts(tab, lo, j-1);
      QuickSortInts(tab, j+1, hi);
    }
}


draft of non stack verion (only checked to work but not revritten to more effecive & better lookin)


   struct Partition {int lo, hi; };

     Partition partitions[1000*1000] = {0};
     int partitions_top = 0;

inline void AddPartition(int lo, int hi)
{
     partitions[partitions_top].lo=lo;
     partitions[partitions_top].hi=hi;
     partitions_top++;
}


inline int SwipePartition_(int* tab, int lo, int hi)
{

    int i=lo, j=hi, p=tab[(lo+hi)/2];

     while (i<j)
     {
      if(tab[j]>=p) {j--; continue;}
      if(tab[i]< p) {i++; continue;}
      int t=tab[i]; tab[i]=tab[j]; tab[j]=t;
     }

     return j;


}


void QuickSortInts_(int* tab, int lo, int hi)
{

    AddPartition(lo, hi);

    for(int i=0; i<partitions_top; i++)
    {
      int lo = partitions[i].lo;
      int hi = partitions[i].hi;
      int j = SwipePartition_(tab, lo, hi);
      if(lo<j-1)  AddPartition(lo, j-1);
      if(j+1<hi)  AddPartition(j+1, hi);

    }

}


i could measure the times but later (now im exhausted as i often am)

[toc] | [prev] | [next] | [standalone]

#143491

W dniu sobota, 27 kwietnia 2019 15:19:54 UTC+2 użytkownik fir napisał:
> W dniu sobota, 27 kwietnia 2019 13:59:17 UTC+2 użytkownik Anton Shepelev napisał:
> > fir:
> > 
> > > besides wat is the idea - roughly looking i doubt if it
> > > will work 9hovever id ont readed into it longer than few
> > > minutes and odnt know what some ariables mean, like q
> > 
> > The only variable with a totally non-intuitive name.
> > Renamed to `d' for stack depth.
> > 
> 
> your code didnt seem to much readable to me, though i dont say also its bad..its a mater of style
> 
> if you do time measurigh test you could comepare your versions wiyth those of my
> 
> recurence version:
> 
> 
> void QuickSortInts(int* tab, int lo, int hi)
> {
>     if(lo<hi)
>     {
>      int i=lo, j=hi, p=tab[(lo+hi)/2];
> 
>      while (i<j)
>      {
>       if(tab[j]>=p) {j--; continue;}
>       if(tab[i]< p) {i++; continue;}
>       int t=tab[i]; tab[i]=tab[j]; tab[j]=t;
>      }
> 
>       QuickSortInts(tab, lo, j-1);
>       QuickSortInts(tab, j+1, hi);
>     }
> }
> 
> 
> draft of non stack verion (only checked to work but not revritten to more effecive & better lookin)
> 
> 
>    struct Partition {int lo, hi; };
> 
>      Partition partitions[1000*1000] = {0};
>      int partitions_top = 0;
> 
> inline void AddPartition(int lo, int hi)
> {
>      partitions[partitions_top].lo=lo;
>      partitions[partitions_top].hi=hi;
>      partitions_top++;
> }
> 
> 
> inline int SwipePartition_(int* tab, int lo, int hi)
> {
> 
>     int i=lo, j=hi, p=tab[(lo+hi)/2];
> 
>      while (i<j)
>      {
>       if(tab[j]>=p) {j--; continue;}
>       if(tab[i]< p) {i++; continue;}
>       int t=tab[i]; tab[i]=tab[j]; tab[j]=t;
>      }
> 
>      return j;
> 
> 
> }
> 
> 
> void QuickSortInts_(int* tab, int lo, int hi)
> {
> 
>     AddPartition(lo, hi);
> 
>     for(int i=0; i<partitions_top; i++)
>     {
>       int lo = partitions[i].lo;
>       int hi = partitions[i].hi;
>       int j = SwipePartition_(tab, lo, hi);
>       if(lo<j-1)  AddPartition(lo, j-1);
>       if(j+1<hi)  AddPartition(j+1, hi);
> 
>     }
> 
> }
> 
> 
> i could measure the times but later (now im exhausted as i often am)

ps i know that this array version coudl be probably optimised as each swipe step in that algorithm produces two next partition - ypu most probably dont need to store both as immediately you take one back and use it - only to store that
one additional one

(thsi maybe will grant that searched improvement over recurance version along with fact you dont need to push retadres values )
- i just did not have mood to rewrite it htat way yet as im a bit exhausted

[toc] | [prev] | [next] | [standalone]

#143381

rick.c.hodgin@gmail.com writes:

> Does qsort() provide any standard function support?  Like if
> I'm sorting a list of integers, is there a qsort_int() func
> I can use without creating my own?  And what about strings?
> Or other things which are standard forms to C?

There's really no reason to have that -- sorting an array of integers is
something that comes up very seldom in any context other than freshman
programming classes.  If you're sorting something it's almost surely
going to be some sort of struct with a key field, so the general tool
provided by qsort() is the right thing to have in the library.

Also, of course, if you really want to sort integers the comparison
function you need to provide is a one-liner anyway.

[toc] | [prev] | [next] | [standalone]

#143382

On Wednesday, April 24, 2019 at 12:54:46 PM UTC-4, Joe Pfeiffer wrote:
> rick.c.hodgin@gmail.com writes:
> 
> > Does qsort() provide any standard function support?  Like if
> > I'm sorting a list of integers, is there a qsort_int() func
> > I can use without creating my own?  And what about strings?
> > Or other things which are standard forms to C?
> 
> There's really no reason to have that -- sorting an array of integers is
> something that comes up very seldom in any context other than freshman
> programming classes.

Depends on what you're doing.  I needed to sort output from the
Windows function EnumProcesses() today, which returns a list of
running processes all of which are identified by their process id.
That list needed to be sorted to generate a list of processes in
a standard order to run through a diff processor to see what
changes before and after various things launch.

Sorting databases on key fields (32-bit integers) requires parsing
through the database and generating lists of keys (for each field
being indexed in that way), sorting the keys, and generating the
indexes.  This requires an 8-byte structure (key field + record
number), but it's sorted based only on the first 4 bytes, so using
a standard function would work.

> If you're sorting something it's almost surely
> going to be some sort of struct with a key field, so the general tool
> provided by qsort() is the right thing to have in the library.

I often use qsort() for that as well.

> Also, of course, if you really want to sort integers the comparison
> function you need to provide is a one-liner anyway.

That's why I was thinking the C Standard Library may provide that
kind of support built-in.  They are fairly trivial to create, but
by not having in the C Standard Library, every developer needing
them must create them.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6  Next page →

Back to top | Article view | comp.lang.c

csiph-web