comparing strings 'mathematically' - is this 'future-save'?
- It's not mathematically ("10" > "9"), it ASCII ordering ("10" < "9") because 1 comes before 9 in the table. Safe until strings go multi byte or you want language depending ordering.
- Never use bubble sort. An insertion sort is twice as efficient (your link said that) and simpler to code than yours. https://www.mql5.com/en/forum/138127
- It's not mathematically ("10" > "9"), it ASCII ordering ("10" < "9") because 1 comes before 9 in the table. Safe until strings go multi byte or you want language depending ordering.
- Never use bubble sort. An insertion sort is twice as efficient (your link said that) and simpler to code than yours. https://www.mql5.com/en/forum/138127
ok, Thanks,
the ASCII ordering ("10"<"9") doesn't matter in my case, it's usable for a binary search.
"twice as efficien" If you look here: https://en.wikipedia.org/wiki/Sorting_algorithm the timing should be the same for both, bubble sort and insertion sort (n..n²), both need 1 single temp var.
But in bubble sort I can easily check (=without an extra comparison) whether the array is already sorted (ret stays false, nothing more to do) or s.th. has changed place, whereafter I have to re-write all the other arrays.
Thanks, gooly
| https://en.wikipedia.org/wiki/Bubble_sort | Bubble sort has worst-case and average complexity both О(n2), |
| https://en.wikipedia.org/wiki/Insertion_sort | worst case input is an array sorted in reverse order. ... (i.e., O(n2)). best case input is an array that is already sorted. ..., Θ(n). insertion sort will usually perform about half as many comparisons as selection sort.(bubble sort) .. insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort; |
No, you look here:
| https://en.wikipedia.org/wiki/Bubble_sort | Bubble sort has worst-case and average complexity both О(n2), |
| https://en.wikipedia.org/wiki/Insertion_sort | worst case input is an array sorted in reverse order. ... (i.e., O(n2)). best case input is an array that is already sorted. ..., Θ(n). insertion sort will usually perform about half as many comparisons as selection sort.(bubble sort) .. insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort; |
As most of the time you are too extreme. If bubble sort do the job for gooly, why could he not use it ? I don't think he can get a performance issue by sorting the list of symbols.
It's good for educational purpose also.
I didn't say he couldn't use it. I said he shouldn't use it and why (simpler to code and more efficient.)
Then what does he do, posts a "If you look here" and completely missed what it actually says, and said a complete falsehood "timing should be the same for both"
So I corrected him, so anyone reading this in the future will know the truth. You think that is extreme?
I didn't say he couldn't use it. I said he shouldn't use it and why (simpler to code and more efficient.)
Then what does he do, posts a "If you look here" and completely missed what it actually says, and said a complete falsehood "timing should be the same for both"
So I corrected him, so anyone reading this in the future will know the truth. You think that is extreme?
WRoeder,
for bubble and insertion sort the timing should be the same - no?
For both I read the same.
bubble sort:
| Worst case performance O(n²) | |
|---|---|
| Best case performance O(n) | |
| Average case performance O(n²) | |
| Worst case space complexity O(1) | auxiliary |
for insertion sort:
| Worst case performance | О(n2) comparisons, swaps |
|---|---|
| Best case performance | O(n) comparisons, O(1) swaps |
| Average case performance | О(n2) comparisons, swaps |
| Worst case space complexity | О(n) total, O(1) auxiliary |
To me this is the same. But more than that the sort-timing is not sooo important for my need.
I want to detect if the array has to be changed (sorted, swapped) because this means I have to re-write all the other arrays and this takes more time.
Bubble sort allows me to place one additional order which is performed only in case of a swap so if the array is already sorted this extra line is never touched.
bubbleSort3(Array A) isChanged = false; //my add n = ArraySize(A); while(n>1) { newn = 1; for (i=0; i<n-1; i++){ if (A[i] > A[i+1]){ A.swap(i, i+1); isChanged = true; // my add newn = i+1; } // ende if } // ende for n = newn; }
In case of insertion sort where should I place what kind of 'change detector'?
INSERTIONSORT(A) 1 for i = 1 to Length(A)-1 do 2 tempVal = A[i] 3 j = i 4 while j > 1 and A[j-1] > tempVal do 5 A[j] = A[j - 1] 6 j = j − 1 7 A[j] = tempVal
How would you detect whether this array has been changed or not? I think the advantage of insertion sort disappears in this case.
gooly
gooly: for bubble and insertion sort the timing should be the same - no?
How would you detect whether this array has been changed or not? I think the advantage of insertion sort disappears in this case.
- No!!!!!!!!! Worst and AVERAGE and BEST case of bubble is n^2 Your newn=i+1 only modifies the best case. For insertion ONLY the worst is n^2 and BEST is O(n).
- Stop assuming and measure it.
- Detecting whether the array has been changed is irrelevant. That can be done in either method.
INSERTIONSORT(A) 1 for i = 1 to Length(A)-1 do 2 tempVal = A[i] 3 j = i 4 while j > 1 and A[j-1] > tempVal do 5 A[j] = A[j - 1] ; MODIFIED=TRUE; 6 j = j − 1 7 A[j] = tempVal
well - if so: "No!!!!!!!!! Worst and AVERAGE and BEST case of bubble is n^2 Your newn=i+1 only modifies the best case. For insertion ONLY the worst is n^2 and BEST is O(n)."
wiki is wrong, but convinced and change the code :)
Thanks,
gooly
- Free trading apps
- Over 8,000 signals for copying
- Economic news for exploring financial markets
You agree to website policy and terms of use
Hi,
in order to perform a quick (binary) search within a string array to get the index I compare strings like that
It works as this amended script shows (try yourself):
But this is a kind of using an undocumented feature - is it save to use it even in future version of mt4?
Maybe s.o. can tell me more.
Thanks in advance,
gooly