The impetus behind this sort timing test is from the Coursers “algo” course and in particular the Quicksort section. One comment was that sorting was so fast that the cost need not even be considered. It seem that on an iPad (version 3) sort times of short NSString objects in an NSArray are cheap for approximately n < 10,000.
The NSMutablearray contains unique strings of 8 digits in random order. The sort was statement was:
[ma sortUsingSelector:@selector(caseInsensitiveCompare:)];
where ma is the afore mentioned NSMutablearray.
Times were calculated in 1,2,5 step increments from 10 to 500,000 items on an iPad (version 3).
The three lines on the graph are:
Blue: the time in ms to sort the array
Green: n log(n) for a visual slope reference
Yellow: n^2 for a visual slope reference
It can be seen (and numerically verified) that the sort time is very slightly greater than n log(n). This is in agreement with sort times to be expected from the Quicksort algorithm.
The table below contain the sort times as well a n log(n and n^2 for comparison:
| items | iPad (3) ms | iPhone 3GS ms | n log(n) | n^2 |
|---|---|---|---|---|
| 10 | 0.104 | 0.488 | 1 | 100 |
| 20 | 0.081 | 0.161 | 3 | 400 |
| 50 | 0.185 | 0.699 | 8 | 2,500 |
| 100 | 0.415 | 0.814 | 20 | 10,000 |
| 200 | 0.948 | 1.827 | 46 | 40,000 |
| 500 | 0.963 | 5.373 | 135 | 250,000 |
| 1000 | 2.963 | 12.247 | 300 | 1,000,000 |
| 2000 | 6.464 | 27.365 | 660 | 4,000,000 |
| 5000 | 14.330 | 83.051 | 1,849 | 25,000,000 |
| 10000 | 41.180 | 182.578 | 4,000 | 100,000,000 |
| 20000 | 196.408 | 406.931 | 8,602 | 400,000,000 |
| 50000 | 565.032 | 1,140.463 | 23,495 | 2,500,000,000 |
| 100000 | 1,244.928 | 2,487.088 | 50,000 | 10,000,000,000 |
| 200000 | 2,703.192 | 5,396.767 | 106,021 | 40,000,000,000 |
| 500000 | 7,476.271 | 15,125.481 | 284,949 | 250,000,000,000 |
1. Sorting takes O(nlogn) time.2. Other hashing medthos are dependent upon input string size, you are expecting that input string is always going to be <= 256 characters.What about using following algorithm, which:1. platform or language independent;2. O(n) time complexity worst-case;3. O(1) space complexity no matter if your input string is a 10kb text file.Algorithm:Step 1. maintain two temporary pointers at starting char of the input string (accessed through array indexing also), first pointer at first char and second pointer at next char;Step 2. take 26 booleans or bits (in of c++), keep setting bits corresponding to the ascii value of the char minus 65 or 97Step 3. when you see a bit is already set, then move forward, else copy that char to first pointer.Step 4. Repeat until string finishes.Rajendra.
great overview! I love it. How is the coxliempty relationship interpreted, e.g., between quicksort und mergesort the coxliempty path is quadratic what does that mean? Thanks a lot for your work and sharing this with us! lnxnt
Quicksort is a space-optimized version of the binary tree sort . Instead of inserting items sequentially into an explicit tree, quicksort organizes them concurrently into a tree that is implied by the recursive calls. The algorithms make exactly the same comparisons, but in a different order. An often desirable property of a sorting algorithm is stability – that is the order of elements that compare equal is not changed, allowing controlling order of multikey tables (e.g. directory or folder listings) in a natural way. This property is hard to maintain for in situ (or in place) quicksort (that uses only constant additional space for pointers and buffers, and logN additional space for the management of explicit or implicit recursion). For variant quicksorts involving extra memory due to representations using pointers (e.g. lists or trees) or files (effectively lists), it is trivial to maintain stability. The more complex, or disk-bound, data structures tend to increase time cost, in general making increasing use of virtual memory or disk.
The 3-way partition variation of quick sort has slightly higher overhead compared to the standard 2-way partition version. Both have the same best, typical, and worst case time bounds, but this version is highly adaptive in the very common case of sorting with few unique keys.
Also, recursively paortiitning below eight elements or so causes the bookkeeping/stack frame overhead to eat up any advantage; I think most implementations use another algorithm once the recursively divided problem set gets this small.Also, quicksort is not stable in its most general form; adding comparisons to induce stability may eat up speed advantage.
Quicksort is a space-optimized version of the binary tree sort . Instead of inserting items sequentially into an explicit tree, quicksort organizes them concurrently into a tree that is implied by the recursive calls. The algorithms make exactly the same comparisons, but in a different order. An often desirable property of a sorting algorithm is stability – that is the order of elements that compare equal is not changed, allowing controlling order of multikey tables (e.g. directory or folder listings) in a natural way. This property is hard to maintain for in situ (or in place) quicksort (that uses only constant additional space for pointers and buffers, and logN additional space for the management of explicit or implicit recursion). For variant quicksorts involving extra memory due to representations using pointers (e.g. lists or trees) or files (effectively lists), it is trivial to maintain stability. The more complex, or disk-bound, data structures tend to increase time cost, in general making increasing use of virtual memory or disk.
I noticed that no one has coermpad these sorts to the PS9110 sort.The above sorts are basically O(N log N) sorts.The PS9110 sort is an O(N) sort.The second advantage is that the above sorts use a binary search.Binary searches are O(log N) searches.The PS9110 search is an O(1) search.Links have the problem of the resources needed to create and destroy the links that keep the data set in sorted order.Arrays have the problem of N/2 moves to add or delete an element from a sorted data set. {O(N) time}The PS9110 altorithms can insert and delete data from an array in O(1) time.