Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The counting sort algorithms (including Radix) are applicable only only for countable elements. Unfortunately real numbers are not countable, so you are unable to sort 'float' or 'double' values easily. Imagine that you need to sort a list of measured temperatures. </p> <p>Now regarding countable amounts (like integers), you have a basic mistake assuming that getting an element from array is O(1). This is not true. When you have array of size N the cost of setting the pointer into this array is O(log(N)). In other words to access the element Array[i] you need to define the 'i' and for defining the value of 'i' you need to set log(i) bits. As long as N is small (say 200 for sorting values of between -100..100 using counting sort) we assume than log(N) is constant and neglect it. But if you want to sort integers than your counting array will be large (size of: 2*MAX_INT) log(2*MAX_INT) might be a large number (like 32). So imagine that you have an array of size 100: A[100] of integers. Using O(N*log(N)) sort requires O(100*log(100)) comparisons. But when using counting sort You create a counting array of huge size (Say 2^64 for 64 bit integers integers) Your total time is O(N*log(2^64)) which is actually more than O(100*log(100)). Crazy as it sounds this is true. And think about the fact that you need to set the entire counting array to zero before you start counting - that is 2^64 operations which is much more than entire O(100*log(100))... And also think about a huge memory waste...</p> <p>In conclusion: Even if you have infinite amount of memory to use the running time is not really O(N). It is in fact the cost of zeroing the counting array and performing the count:</p> <pre><code>O(MAX_INT) + O(N*log(MAX_INT)) </code></pre> <p>Usually This is much more than <code>O(N*log(N))</code> for any reasonable N so counting sort is impractical. The only case when it is practical is when the range of the values is small (like -100..100) and </p> <pre><code>O(MAX_INT) + O(N*log(MAX_INT)) </code></pre> <p>becomes <code>O(200) + O(N*log(200)) ~ O(N)</code></p> <p>Radix sort enables you to save some memory and the cost of zeroing the huge counting array, but still you don't really loose the log() factor because a number of range -X..X has log(X) digits and you are still have the log(MAX_INT) which is usually larger than log(N) , Where N is the size of the array you want to sort. </p>
    singulars
    1. This table or related slice is empty.
    1. POLinear sorting algorithms
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDanielHsH
    1. USDanielHsH
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO"When you have array of size N the cost of setting the pointer into this array is O(log(N))". Could you explain further?
      singulars
      1. PO
      1. USChronoTrigger
    2. COImagine you have an array of size 2^1000. In order to access it in place 'i' you have to define the 'i' variable. 'i' variable must be of at least 1000 bits for accessing such a long array. So you have at least 1000 actions (settings bits to 0 and zeros) for every access to the array. 1000 is exactly log(2^1000)
      singulars
      1. PO
      1. USDanielHsH
    3. COOk, you are talking about very big numbers then. But for more normal numbers, i.e. < 2^32, I think it is "safe" to assume that accessing a vector v[i] is O(1), because you are adding an address and an integer, which are independent of the length of the vector (i.e. N). If we want to deal with the big O at a bit level, we cannot even assume that an assignment is O(1), but this is not very useful to study the complexity of sorting algorithms.
      singulars
      1. PO
      1. USChronoTrigger
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload