#### Topic: What algorithms of sorting of an array of the big length advise?

Dear colleagues, what algorithms of sorting of an array of the big length (to 10000 elements) advise? There is an algorithm of quick sort, but it not always works correctly.

You are not logged in. Please login or register.

Programmer's Town » Programming philosophy » What algorithms of sorting of an array of the big length advise?

Dear colleagues, what algorithms of sorting of an array of the big length (to 10000 elements) advise? There is an algorithm of quick sort, but it not always works correctly.

Hello, RussianFellow, you wrote: RF> Dear colleagues, what algorithms of sorting of an array of the big length (to 10000 elements) advise? And you that should receive as a result? The data too different happens. RF> there is an algorithm of quick sort, but it not always works correctly. What means "not always works correctly"? The algorithm either sorts, or does not sort on any data so it is wrong algorithm or its wrong configuring.

Hello, RussianFellow, you wrote: RF> Dear colleagues, what algorithms of sorting of an array of the big length (to 10000 elements) advise? Any, which with support of multinuclear possibilities of the processor, in GNU STL it __ gnu_parallel:: sort, for example. That is, here not so much algorithm, how many its implementation with involvement of all possibilities of iron is important. That is, the most important iron in a software-it on which it is executed.

Hello, Kernan, you wrote: K> Hello, RussianFellow, you wrote: RF>> Dear colleagues, what algorithms of sorting of an array of the big length (to 10000 elements) advise? K> and you that it is necessary to receive as a result? The data too different happens. Sorted by increase or decrease an array from real numbers.

Hello, RussianFellow, you wrote: I and did not master independently to write algorithm of quick sort, I use simple algorithm of search: two nested loops, the first I from 1 to N-1, the second J from I+1 to N, is in the second cycle the least number and it changes with the number which is under an index I. Such algorithm not the fastest, but at me never arose tasks for which speed would be critical. If at you an array from 10 thousand numbers, sorting by this algorithm occupies time millisecond, it is possible not to worry.

Hello, RussianFellow, you wrote: RF> Dear colleagues, what algorithms of sorting of an array of the big length (to 10000 elements) advise? RF> there is an algorithm of quick sort, but it not always works correctly. It always works if is implemented correctly. For big merge-sort but 10000 it not the big is long. https://en.wikipedia.org/wiki/External_sorting

Hello, Khimik, you wrote: K> I and did not master independently to write algorithm of quick sort, I use simple algorithm of search. Than it is better than algorithm qsort with a recursion?

Hello, RussianFellow, you wrote: RF> Dear colleagues, what algorithms of sorting of an array of the big length (to 10000 elements) advise? RF> there is an algorithm of quick sort, but it not always works correctly. If there was an array of length which does not enter into storage then it was meaningful to sort in parts, then to merge. And so - use any standard for your coding environment. Fulfills so, as you will not note.

Hello, smeeld, you wrote: S> Hello, Khimik, you wrote: K>> I and did not master independently to write algorithm of quick sort, I use simple algorithm of search. S> than it is better than algorithm qsort with a recursion? Perhaps, anything, unless that it is not necessary to use the indirect code which suddenly somehow not so earns on the specific task.

Hello, Khimik, you wrote: K> Perhaps, anything, unless that it is not necessary to use the indirect code which suddenly somehow not so earns on the specific task. What ? Meant the implementation qsort in the recursive form, instead of a partition method on two cycles about what there at you it was above told.

Hello, smeeld, you wrote: S> What ? Meant the implementation qsort in the recursive form, instead of a partition method on two cycles about what there at you it was above told. I also speak - qsort I did not master the implementation. It is necessary to me, that someone clearly explained on fingers as this sorting works. And under books it is often difficult to understand something difficult.

Hello, Khimik, you wrote: K> Hello, RussianFellow, you wrote: K> I and did not master independently to write algorithm of quick sort, I use simple algorithm of search: two nested loops, the first I from 1 to N-1, the second J from I+1 to N, is in the second cycle the least number and it changes with the number which is under an index I. Such algorithm not the fastest, but at me never arose tasks for which speed would be critical. If at you an array from 10 thousand numbers, sorting by this algorithm occupies time millisecond, it is possible not to worry. Thanks, sorting work for me normally!

Hello, Khimik, you wrote: K> Perhaps, anything, unless that it is not necessary to use the indirect code which suddenly somehow not so earns on the specific task. Quite right.

Hello, Khimik, you wrote: K> I also speak - qsort I did not master the implementation. It is necessary to me, that someone clearly explained on fingers as this sorting works. And under books it is often difficult to understand something difficult. And, clearly, but there everything is simple, more low the most simple variant, works hardly more slowly than std:: sort (in last not absolutely qsort, a HeapSort, in which on small intervals if the size of the partial segment less than some limit, quick sort is replaced on heap_sort), but faster than qsort them glibc. #include <iostream> #include <algorithm> #include <vector> #include <iterator> #define likely (X) __ builtin_expect (!! (X), 1) template <typename Pos, typename Cmp> void srt (Pos pt, Pos pm, Cmp cmp) {Pos tmp=pt, md=pt, sp; do {if (likely (md == pm)) return; sp=pm; while (sp! =tmp) {if (cmp (*tmp, *md)) {++ tmp; continue;} ; while (- sp! =tmp) {if (cmp (*md, *sp)) continue; std:: swap (*tmp, *sp); ++ tmp; break;}} ++ md;} while (tmp == pt); srt (pt, tmp, cmp); srt (tmp, pm, cmp);} template <typename Pos> void srt (Pos pt, Pos pm) {Pos tmp=pt, md=pt, sp; do {if (likely (md == pm)) return; sp=pm; while (sp! =tmp) {if (cmp (*tmp, *md)) {++ tmp; continue;}; while (- sp! =tmp) {if (cmp (*md, *sp)) continue; std:: swap (*tmp, *sp); ++ tmp; break;}} ++ md;} while (tmp == pt); srt (pt, tmp); srt (tmp, pm);} int main (int a, char ** s) {std:: vector <int> v; v.reserve (std:: stoi (s [1])); std:: generate_n (std:: back_inserter <std:: vector <int>> (v), std:: stoi (s [1 ); std:: copy (v.begin (), v.begin () +std:: stoi (s [2]), std:: ostream_iterator <int> (std:: cout, "\n"));}

Hello, Khimik, you wrote: K> I and did not master independently to write algorithm of quick sort, Yes is fine? K> I use simple algorithm of search: two nested loops, the first I from 1 to N-1, the second J from I+1 to N, is in the second cycle the least number and it changes with the number which is under an index I. Whether the bubble sort method? Somehow you strange described it.

Hello, RussianFellow, you wrote: RF> Dear colleagues, what algorithms of sorting of an array of the big length (to 10000 elements) advise? RF> there is an algorithm of quick sort, but it not always works correctly. You , did not prepare for interviews when? To go nuts.

Hello, Khimik, you wrote: K> Perhaps, anything, unless that it is not necessary to use the indirect code which suddenly somehow not so earns on the specific task. I while met exactly one specific task: to sort surnames in alphabetic order in the Ukrainian language. Some letters of the Ukrainian language took wrong places in the table. And that, it was for a long time.

Hello, smeeld, you wrote: S> Hello, Khimik, you wrote: K>> I also speak - qsort I did not master the implementation. It is necessary to me, that someone clearly explained on fingers as this sorting works. And under books it is often difficult to understand something difficult. S> and, clearly, but everything there is simple, more low the most simple variant, works hardly more slowly than std:: sort (in last not absolutely qsort, a HeapSort, in which on small intervals if the size of the partial segment less than some limit, quick sort is replaced on heap_sort), but faster than qsort them glibc. I, as well as the HARDWARE, not the pro, know only Delphi, but I would like to understand a principle qsort. From Vicks I like understood the following: sorting Procedure has on a boundary input in which the array (initially from 1 to N is processed). We find median number M in an array (one cycle is for this purpose launched), further we divide an array on two parts - smaller and big (or equal) M. If I correctly understand, for this purpose it is convenient to hold temporary array Z of the same length, as well as sorted, and to run two cycles - at first to place in Z numbers, smaller M, and then numbers, big or equal M. Further it is necessary to launch the fourth cycle - to replace an initial array on Z. To remember boundaries of two subarrays: from 1 to V from V+1 to N. And further twice to cause recursively the same procedure, the first with boundaries from 1 to V, the second with boundaries from V+1 to N. If the recursive function sees that to it suggest to sort only one number - at once to quit.

Hello, RussianFellow, you wrote: RF> Hello, Khimik, you wrote: K>> Perhaps, anything, unless that it is not necessary to use the indirect code which suddenly somehow not so earns on the specific task. RF> quite right. It is absolutely incorrect!

Hello, RussianFellow, you wrote: RF> Sorted by increase or decrease an array from real numbers. Then simply take quick sort and use it. 10.000 elements it about what, but on this array problems are already shown. Complexities therefore bubble sort which were offered by the Chemist will be not optimal, though if your data is badly mixed or laid partially down in an array upside-down qsort will be not so is effective. Anyway, qsort it is better than bubble sort.

Hello, Kernan, you wrote: K> Hello, RussianFellow, you wrote: RF>> Sorted by increase or decrease an array from real numbers. K> then simply take quick sort and use it. 10.000 elements it about what, but on this array problems are already shown. Complexities therefore bubble sort which were offered by the Chemist will be not optimal, though if your data is badly mixed or laid partially down in an array upside-down qsort will be not so is effective. Anyway, qsort it is better than bubble sort. At me not bubble sort. I do not know, how my algorithm (though it, apparently, even hardly more slowly, than bubble sort) is called. I always use it, as it occupies all somewhere 10 code lines, and I interpose it into any code mixed up with other tasks. As I already told, sorting of 10 thousand numbers by this algorithm occupies somewhere a millisecond if the HARDWARE writes not games that such speed will be for it quite sufficient.

Hello, RussianFellow, you wrote: RF> Dear colleagues, what algorithms of sorting of an array of the big length (to 10000 elements) advise? M-yes. Both length big, and philosophy deep.

Hello, Khimik, you wrote: K> Hello, smeeld, you wrote: S>> Hello, Khimik, you wrote: K>>> I also speak - qsort I did not master the implementation. It is necessary to me, that someone clearly explained on fingers as this sorting works. And under books it is often difficult to understand something difficult. S>> and, clearly, but everything there is simple, more low the most simple variant, works hardly more slowly than std:: sort (in last not absolutely qsort, a HeapSort, in which on small intervals if the size of the partial segment less than some limit, quick sort is replaced on heap_sort), but faster than qsort them glibc. K> I, as well as the HARDWARE, not the pro, know only Delphi, but I would like to understand a principle qsort. From Vicks I like understood the following: K> sorting Procedure has on a boundary input in which the array (initially from 1 to N is processed). We find median number M in an array (one cycle is for this purpose launched), further we divide an array on two parts - smaller and big (or equal) M. If I correctly understand, for this purpose it is convenient to hold temporary array Z of the same length, as well as sorted, and to run two cycles - at first to place in Z numbers, smaller M, and then numbers, big or equal M. Further it is necessary to launch the fourth cycle - to replace an initial array on Z. To remember boundaries of two subarrays: from 1 to V from V+1 to N. And further twice to cause recursively the same procedure, the first with boundaries from 1 to V, the second with boundaries from V+1 to N. If the recursive function sees that to it suggest to sort only one number - at once to quit. Quick sort: a small group of elements. Arbitrarily we select any. For remaining elements we shift in the left heap if an element less selected or in right otherwise. Then for the left and right small group we do too most. In the end we obtain the arranged data. PROFIT on delphi looks somehow so type TQSort=class function cmp (i, j:integer):integer; virtual; abstract; procedure swap (i, j:integer); virtual; abstract; procedure sort (N:integer); virtual; end; procedure TQSort.sort (N:integer); const threshold=7; stacksize=16*sizeof (integer)-6; var stack:array [0. stacksize] of integer; sp, i, j, L, R:integer; begin sp: = 0; L: = 0; R: = N-1; repeat while (R-L)> =threshold do begin swap ((L+R) shr 1, L); i: = L+1; j: = R; if cmp (i, j)> 0 then swap (i, j); if cmp (L, j)> 0 then swap (L, j); if cmp (i, L)> 0 then swap (i, L); repeat repeat inc (i); until (cmp (i, L)> =0); repeat dec (j); until (cmp (j, L) <=0); if i> j then break else swap (i, j); until false; swap (L, j); if (j-L)> (R-i) then begin stack [sp inc (sp, 2); end; i: = L+1; while i <=R do begin j: = i; while (j> L) and (cmp (j-1, j)> 0) do begin swap (j-1, j); dec (j); end; inc (i); end; if (sp> 0) then begin dec (sp, 2); L: = stack [sp]; R: = stack [sp+1]; end else break; until false; end; it is necessary to define only operation of comparing and an exchange of elements

Hello, Khimik, you wrote: K> I, as well as the HARDWARE, not the pro, know only Delphi, but I would like to understand a principle qsort. From Vicks I like understood the following: K> sorting Procedure has on a boundary input in which the array (initially from 1 to N is processed). We find median number M in an array (one cycle is for this purpose launched), further we divide an array on two parts - smaller and big (or equal) M. Truly. K> if I correctly understand, for this purpose it is convenient to hold a temporary array Was not present, it is possible to make directly on a place. In Wikipedia is , showing process.

Hello, Khimik, you wrote: K> As I already told, sorting of 10 thousand numbers by this algorithm occupies somewhere a millisecond if the HARDWARE writes not games that such speed will be for it quite sufficient. Here the test for and qsort (though if I am fair I do not know what in stl a sort) http://ideone.com/7YG12V. It is obvious that gives 170ms on 10.000 and if to raise an amount of elements to 50.000 already it is more 4.

**Random topics**