c++ - Merge sorted arrays - Efficient solution -

-

goal here merge multiple arrays sorted resultant array.

i've written following solution , wondering if there way improve solution

/*     goal merge sorted arrays */ void mergeall(const vector< vector<int> >& listofintegers,  vector<int>& result) {      int totalnumbers = listofintegers.size();     vector<int> curpos;     int currow = 0 , minelement , foundminat = 0;     curpos.reserve(totalnumbers);      // set current position travered 0 in array elements     ( int = 0; < totalnumbers; ++i)     {         curpos.push_back(0);     }      ( ; ; )     {         /*  find first minimum              first element in array hasn't been traversed         */          ( currow = 0 ; currow < totalnumbers ; ++currow)         {             if ( curpos[currow] < listofintegers[currow].size() )             {                 minelement = listofintegers[currow][curpos[currow] ];                 foundminat = currow;                 break;             }         }         /* if elements traversed in arrays, no further work needs done */         if ( !(currow < totalnumbers ) )             break;         /*              traverse each of array , find out first available minimum value         */         ( ;currow < totalnumbers; ++currow)         {             if ( listofintegers[currow][curpos[currow] ] < minelement )             {                 minelement = listofintegers[currow][curpos[currow] ];                 foundminat = currow;             }         }         /*              store minimum resultant array              , increment element traversed         */         result.push_back(minelement);         ++curpos[foundminat];     } }

the corresponding main goes this.

int main() {     vector< vector<int> > myint;     vector<int> result;      myint.push_back(vector<int>() );     myint.push_back(vector<int>() );     myint.push_back(vector<int>() );      myint[0].push_back(10);     myint[0].push_back(12);     myint[0].push_back(15);       myint[1].push_back(20);     myint[1].push_back(21);     myint[1].push_back(22);      myint[2].push_back(14);     myint[2].push_back(17);     myint[2].push_back(30);      mergeall(myint,result);      ( int = 0; < result.size() ; ++i)     {         cout << result[i] << endl;     } }

you can generalize merge sort algorithm , work multiple pointers. initially, of them pointing beginning of each array. maintain these pointers sorted (by values point to) in priority queue. in each step, remove smallest element in heap in o(log n) (n number of arrays). output element pointed extracted pointer. increment pointer in 1 position , if didn't reach end of array, reinsert in priority queue in o(log n). proceed way until heap not empty. if there total of m elements, complexity o(m log n). elements output in sorted order way.


Comments

Post a Comment

Popular posts from this blog

c++ - How do I get a multi line tooltip in MFC -

-
right now, have tool tip pops when hover on edit box. problem tool tip contains multiple error messages , in 1 long line. need have each error message on own line. error messages contained in cstring new line seperating them. my existing code below. bool ontooltiptext(uint, nmhdr* pnmhdr, lresult* presult) { assert(pnmhdr->code == ttn_needtexta || pnmhdr->code == ttn_needtextw); // need handle both ansi , unicode versions of message tooltiptexta* pttta = (tooltiptexta*)pnmhdr; tooltiptextw* ptttw = (tooltiptextw*)pnmhdr; // tchar szfulltext[256]; cstring strtiptext=_t(""); uint nid = pnmhdr->idfrom; if (pnmhdr->code == ttn_needtexta && (pttta->uflags & ttf_idishwnd) || pnmhdr->code == ttn_needtextw && (ptttw->uflags & ttf_idishwnd)) { // idfrom hwnd of tool nid = ::getdlgctrlid((hwnd)nid); } //m_errprojaccel[ch] contains 1 or more error messages each...
Read more

asp.net - In javascript how to find the height and width -

-
i having .aspx , masterpage page. in masterpage loading aspx page . in aspx page design using generating table structure using code-behind server in javascript how find height , width . regards, kumar if you're looking table height , width, should it var tbl = document.getelementbyid('tbldemo'); alert(tbl.offsetwidth + '\n' + tbl.offsetheight);
Read more

c# - DataTable to EnumerableRowCollection -

-
i have datatable according client requirement can contain invalid date "00/00/1999",null,empty string.(typed datset) when collect them enumerables wish convert of invalid forms empty string. (i.e) enumerablerowcollection<datarow> query = order in _table.asenumerable() select new { orderdate= string.isnullorempty(convert.tostring(order.field<datetime>("orderdate")) || (how check date invalid date) ? string.empty : order.field<datetime>("orderdate") } how check whether date valid date or not? datetime.tryparse...like given current code: datetime date; enumerablerowcollection<datarow> query = order in _table.asenumerable() select new { orderdate= string.isnullorempty(convert.tostring(order.field<datetime>("orderdate")) || !datetime.tryparse(convert.tostring(order.field<datetime...
Read more