|
|
back to boardO(n*log(n)) solution in 0.328 seconds and new type of sorting! Posted by Pasha 30 Jun 2004 21:07 Yes, this solution is very slow, but during solving this problem new type of sorting was invented, which sorts any massive in O(n*log(n)) time and doesn't require additional memory! Are you kidding? :) New type of sorting? :) (+) I think you should first read "The art of computer programming" by Donald E. Knuth (especially, Volume 3 "Sorting and Searching") and "Introduction to Algorithms", the MIT Press... If you are not kidding,can you send your soure to yym2008@hotmail.com? Re: O(n*log(n)) solution in 0.328 seconds and new type of sorting! Posted by Sandro 10 Aug 2004 10:43 Why is your solution so slow? My program works O(N*log(N)) too (using Qsort) but in 0.046 sec. Re: O(n*log(n)) solution in 0.328 seconds and new type of sorting! Posted by BYF 4 Sep 2004 20:28 There are lots of sorts of sorting methods can do this(nlogn at any time) and faster than you. Re: O(n*log(n)) solution in 0.328 seconds and new type of sorting! Please, send me your code - dkorduban[at]ukr.net No subject Edited by author 25.03.2005 19:49 Re: O(n*log(n)) solution in 0.328 seconds and new type of sorting! Posted by Pasha 25 Mar 2005 19:18 I am giving my apologizing because I accidentally mislead everybody. I used silly Binary Search method to solve this problem. I've written the first lines because I contrived this method myself during solving this problem, so I was very pleased and wrote the strings at the beginning in the heat of the solvation of the problems. To <Dmitry 'Diman_YES' Kovalioff>: I've did't expect that books of so kind even exists at that time, not mentioned that I read one of them. You've opened my eyes. Thank You very much for this. To everyone who wants see my code (Pascal): {In reading we trying to place the last read element into the massive of the last M read elements in the proper place following the value of it. So the last element in this massive will be the greatest - we write this element to the ouput.} const lenmax=100000; upbone=100000; var elkol: array [0..upbone] of word; elems, elist: array [1..lenmax] of longint; curno, curelem, m, els, elpos: longint; already_in_list: boolean; function BinSearch(bsx: longint): longint; var bsp, bsq, bsi: longint; begin bsp:=1; { Left border of the search } bsq:=els; { Right border of the search } while bsp <= bsq do begin bsi:=(bsp + bsq) div 2; if elist[bsi] = bsx then begin BinSearch := bsi; already_in_list:=true; exit end; if bsx < elist[bsi] then bsq := bsi - 1 else bsp := bsi + 1 end; if bsx>elist[bsq] then BinSearch:=bsp else BinSearch:=bsq; already_in_list:=false end; procedure ins_new_item; begin if curelem<elist[1] then begin move(elist[1], elist[2], els*4); elist[1]:=curelem; inc(els) end else if curelem>elist[els] then begin inc(els); elist[els]:=curelem; end else begin elpos:=binsearch(curelem); if not already_in_list then begin move(elist[elpos], elist[elpos+1], (els-elpos+1)*4); elist[elpos]:=curelem; inc(els) end end end; begin fillchar(elkol, sizeof(elkol), 0); readln(m); readln(curelem); if curelem=-1 then exit; elist[1]:=curelem; els:=1; curno:=0; while (curno<m) and (curelem<>-1) do begin inc(curno); elems[curno]:=curelem; inc(elkol[curelem]); if curno>1 then ins_new_item; readln(curelem) end; {First M or less elements are being read} writeln(elist[els]); if curelem=-1 then exit; {If not end of sequence, reading until curelem=-1 (condition of the end of the sequence)} while curelem<>-1 do begin inc(curno); elems[curno]:=curelem; inc(elkol[curelem]); ins_new_item; dec(elkol[elems[curno-m]]); if elkol[elems[curno-m]]=0 then begin elpos:=binsearch(elems[curno-m]); move(elist[elpos+1], elist[elpos], (els-elpos)*4); dec(els) end; writeln(elist[els]); readln(curelem) end end. |
|
|