1

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.

2

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

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.

3

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

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.

4

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

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.

5

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

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.

6

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

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

7

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

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?

8

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

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.

9

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

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.

10

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

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.

11

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

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.

12

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

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!

13

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

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.

14

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

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"));}

15

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

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.

16

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

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.

17

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

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.

18

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

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.

19

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

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!

20

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

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.

21

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

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.

22

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

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.

23

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

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

24

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

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.

25

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

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.