0
$\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$
6
  • 2
    $\begingroup$ Please use $f \in O(n)$ and $f \in o(n)$ as appropriate. $\endgroup$
    – greybeard
    Commented 20 hours ago
  • 1
    $\begingroup$ "because the map is alphabetical", who says? $\endgroup$
    – Rinkesh P
    Commented 13 hours ago
  • $\begingroup$ For example, the built in functions in Java do this $\endgroup$
    – user1503883
    Commented 13 hours ago
  • 1
    $\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 13 hours ago
  • 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 13 hours ago

3 Answers 3

Reset to default
3
$\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$
3
  • $\begingroup$ Similar story for a radix map (e.g. a trie) vs radix sort. $\endgroup$
    – Pseudonym ♦
    Commented 9 hours ago
  • $\begingroup$ Isn't that the exact complexity of quick sort $\endgroup$
    – user1503883
    Commented 3 hours ago
  • $\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 2 hours ago
3
$\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 3 hours ago
  • $\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 2 hours ago
0
$\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$

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.