-1
$\begingroup$

Instead of doing a quicksort, you can store everything in a map. Because the map is alphabetical it's already sorted.

It seems like instead of doing a quicksort you could instantly put everything in a map and get it back as a o1 operation.

Why is quicksort done when you can just put everything in a map? The disadvantage is running out of memory but then you're implying the memory is somewhat of a fraud because you have more discrete values than the memory can store anyway.

Even so you can just layer the map to get the same result, if values crowd into one key then you can create a map under that key and it barely changes the complexity. There's no notation to express this but it would be o(1)(n/m) where n is the number of possible entries divided by the firmware limits of the memory to virtualize addresses.

The example function would be treemap.

Improve this question
New contributor
user1503883 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
7
  • 3
    $\begingroup$ Please use $f \in O(n)$ and $f \in o(n)$ as appropriate. $\endgroup$
    – greybeard
    Commented 2 days ago
  • 2
    $\begingroup$ "because the map is alphabetical", who says? $\endgroup$
    – Rinkesh P
    Commented yesterday
  • $\begingroup$ For example, the built in functions in Java do this $\endgroup$
    – user1503883
    Commented yesterday
  • 2
    $\begingroup$ please mention the example functions clearly in your question, and please clarify more on "firmware limits of the memory to virtualize address" $\endgroup$
    – Rinkesh P
    Commented yesterday
  • 1
    $\begingroup$ also clarify on what "layer the map" does, and how would it be done w.r.t the examples you provide $\endgroup$
    – Rinkesh P
    Commented yesterday

3 Answers 3

Reset to default
5
$\begingroup$

Inserting $n$ items into a sorted map takes a total of $O(n \log n)$ time, so the running time is not faster than sorting the $n$ items.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Similar story for a radix map (e.g. a trie) vs radix sort. $\endgroup$
    – Pseudonym ♦
    Commented yesterday
  • $\begingroup$ Isn't that the exact complexity of quick sort $\endgroup$
    – user1503883
    Commented yesterday
  • $\begingroup$ @user1503883 It sure is! (At least on suitably random lists.) And lots of other sort algorithms besides. In fact, it's pretty easy to prove that O(n log(n)) is optimal for sorts that only use greater than/less than comparisons on the objects being sorted. $\endgroup$
    – Daniel Wagner
    Commented yesterday
  • 1
    $\begingroup$ @user1503883 Two algorithms with the same BigO complexity do not necessarily have the same real performance, they just scale in the worst case at the same rate. There's also memory use to consider. $\endgroup$
    – Schwern
    Commented yesterday
4
$\begingroup$

Apples vs Oranges

Quicksort is a sorting algorithm, whereas a map/dictionary/hashtable/hashmap is a container data structure. Use cases of both are widely apart.

As far as your argument is concerned, yes one can sort items that way, but depending on the input and map implementation, a map would need to perform much more operations like insertion, collision handling and resizing, all of which are not needed in sorting.

As far as TreeMap is concerned, it uses Red-Black trees underneath. So effectively and as rightly pointed out by @D.W.'s answer, the running time, or the time complexity, is not better.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How does quick sort not require insertion, and the memory also requires virtualization $\endgroup$
    – user1503883
    Commented yesterday
  • $\begingroup$ @user1503883 You are again comparing Apples and Oranges by introducing virtual memory into this. Quicksort is much much more easy to implement and understand than RB tree or a balanced tree. The fact that YOU don't have to implement a sorted map doesn't mean it's free from cost. Just implement one and see for your self which is faster. It's pretty easy to see that a map implemented with a balanced tree still requires O(nlogn) to sort an array. $\endgroup$
    – Margaret Bloom
    Commented yesterday
2
$\begingroup$

Instantly put everything in a map and get it back as a $O(1)$ operation.

HashMap operations do run in $O(1)$, but it cannot be used for sorting.

TreeMap can be used for sorting, but its operations run in $O(\log n)$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ The operations would be somewhat better than log n if mapped correctly. Because many of the operations are o(1). $\endgroup$
    – user1503883
    Commented yesterday
  • $\begingroup$ @user1503883 Do you map with TreeMap, or something else? $\endgroup$
    – Kenneth Kho
    Commented yesterday
  • $\begingroup$ Treemap or a c function using the memory. Because the memory location is read anyway the size of the map there can be anything and still be one read $\endgroup$
    – user1503883
    Commented yesterday
  • 2
    $\begingroup$ @user1503883 Both c++ map and java TreeMap use Red-Black Tree, whose search, insertion, deletion runs in $O(\log n)$. $\endgroup$
    – Kenneth Kho
    Commented yesterday
  • $\begingroup$ It's actually somewhat faster than log n because the leaf breadth can be arbitrary $\endgroup$
    – user1503883
    Commented yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.