c++ - Quicksort correct implemetation but with some extra comparisons -


i'm trying pull maximum out of quicksort implementation. functionally correct , has canonical form, i've counted superfluous comparisons. use first element pivot:

#include <vector>  using namespace std; using uint = unsigned int;  uint partitionsub(vector<uint>& inp, uint l, uint r, uint& numofcmp);  void quicksort(vector<uint>& inp, uint l, uint r, uint& numofcmp) {     if (r - l < 2)         return;      uint newpivotidx = partitionsub(inp, l, r, numofcmp);      quicksort(inp, l, newpivotidx, numofcmp);     quicksort(inp, newpivotidx + 1, r, numofcmp); }  uint partitionsub(vector<uint>& inp, uint l, uint r, uint& numofcmp) {     auto swap = [&inp](uint a, uint b)     {         uint buf = inp[a];         inp[a] = inp[b];         inp[b] = buf;     };      //numofcmp += r - l; // can use this, ++numofcmp before                               // comparison more clear     uint = l + 1;     uint j = l + 1;      uint p = inp[l];      (; j <= r; j++)     {         ++numofcmp;         if (inp[j] < p)         {             if (i != j)                 swap(i, j);             i++;         }     }      uint newpivotidx = - 1;     swap(l, newpivotidx);     return newpivotidx; }

given input: 3,9,8,4,6,10,2,5,7,1 25 comparisons required, 27. i've been debugging 3 days , have no clues. if guys see places should optimized in sense of making fewer comparisons, please give me directions? understand, it's due redundant recursion pass, since partition subroutine , counting in implemented correctly.

i may have spotted problem:

quicksort(inp, l, newpivotidx, numofcmp); quicksort(inp, newpivotidx + 1, r, numofcmp);

you don't need include pivot element in recursion; know it's in correct position. change first line

quicksort(inp, l, newpivotidx-1, numofcmp);

you haven't displayed debugging output, such trace of printing arguments on function entry, , i'm afraid don't have time myself right now. hope happens problem.


Comments

Post a Comment

Popular posts from this blog

jOOQ update returning clause with Oracle -

according http://www.jooq.org/doc/3.8/manual/sql-building/sql-statements/update-statement/ jooq doesn't support returning clause in update statements databases except firebird , postgres. does know, still correct oracle jooq? according oracle's documentation, oracle db supports returning clase delete, insert, or update statements. incorrect manual you're right - manual wrong , should fixed: https://github.com/jooq/jooq/issues/5470 single row update returning jooq 3.8 added support single row update .. returning statements. internally, uses callablestatement , pl/sql block of form: begin update "my_table" set "my_table"."column" = 'xyz' "my_table"."id" = 1 returning "my_table"."id", "my_table"."column" ?, ?; ? := sql%rowcount; end; the relevant issue is: https://github.com/jooq/jooq/issues/5190 multi row update returning a...
Read more

java - Warning equals/hashCode on @Data annotation lombok with inheritance -

i have entity inherits other. on other hand, i'm using lombok project reduce boilerplate code, put @data annotation. annotation @data inheritance produces next warning: generating equals/hashcode implementation without call superclass, though class not extend java.lang.object. if intentional, add '@equalsandhashcode(callsuper=false)' type. is advisable add annotation @equalsandhashcode (callsuper = true) or @equalsandhashcode (callsuper = false) ? if not added, 1 callsuper=false or callsuper=true ? the default value false . 1 if don't specify , ignore warning. yes, recommended add @equalsandhashcode annotation on @data annotated classes extend else object. cannot tell if need true or false , depends on class hierarchy, , need examined on case-by-case basis. however, project or package, can configure in lombok.config call super methods if not direct subclass of object. lombok.equalsandhashcode.callsuper = call for configuration system ...
Read more

java - BasicPathUsageException: Cannot join to attribute of basic type -

i using java 8 jpa (hibernate 5.2.1). have clause works perfectly, until introduce clause make use foreign key table values too. i getting following error: basicpathusageexception: cannot join attribute of basic type i think problem related fact have join table, , not sure how create join using join table. employee - employee_category - category model (employee.java): @manytomany(cascade = cascadetype.all, fetch=fetchtype.eager) @jointable ( name="employee_category", joincolumns={ @joincolumn(name="emp_id", referencedcolumnname="id") }, inversejoincolumns={ @joincolumn(name="cat_id", referencedcolumnname="id") } ) private set<category> categories; model (category.java): @id private string id; jpa when introduce following code, fails error above (i think problem new piece of code): join<t, category> category = from.join("id"); predicates.add(criteriabuilder.like(category....
Read more