-1

My given sequence looks like this

<product, quantity>

<milk, 2>, <bread, 3>, <eggs, 3>, <sugar, 2>, <apples, 4>, <berries, 4>
Here I have my n value as 6 and k as 3 (3 distinct values - 2, 3, 4).

My sorted sequence should be like this. Sorted in increasing order of key-values

<milk, 2>, <sugar, 2>,  <bread, 3>, <eggs, 3>, <apples, 4>, <berries, 4>

What algorithms can I use to sort this in two running times? 1. O(n) 2. O(nlogk)

Gokkul
  • 74
  • 1
  • 1
  • 7
  • 1
    This sounds like homework, What algorithms did you come up with and what where their time complexities? – Henry Jun 24 '19 at 02:15
  • You posted (and deleted) [this same question](https://stackoverflow.com/questions/56728658/how-can-i-sort-a-given-record-in-two-different-ways-on-and-onlogk-where-k) 1 hour ago. Why did you post this duplicate instead of improving the other one? – Blastfurnace Jun 24 '19 at 02:38
  • @Henry I tried with hash map and tree map, but I am having a tuff time understanding how the run-time complexity would be O(nlogk) when I am using a tree map. I am self-learning algorithms and am trying to solve some problems that I came across in the books. – Gokkul Jun 24 '19 at 03:11
  • @Blastfurnace I am quite new to the stackoverflow community. I wanted to improve the quality of the question. That is why I decided to take it down. I will remember going forward to edit the same question. Thank you for your valuable suggestions. Sorry for the inconvenience. – Gokkul Jun 24 '19 at 03:16
  • @Gokkul You should update the question with what you have tried. Stackoverflow works best when you tell what you tried and where you are stuck. – Gaurav Singh Jun 24 '19 at 07:06

1 Answers1

0

I just started learning algorithms so correct me if im wrong. I think we can use redblack tree or treemap for sorting the key,value pair in running time of O(n) and then traverse through the key-value pair to display the distinct values of k in running time of O(log k). So total running time would for this algorithm would be n * log k =O(n log k).

priyanka
  • 24
  • 2
  • `we can use redblack tree or treemap for sorting the key,value pair in running time of O(n)` What does "use redblack tree or treemap" mean here? You mean inserting values? – Gaurav Singh Jun 24 '19 at 07:03
  • @gokkul: I think for this question this would be helpful:https://stackoverflow.com/questions/7965132/java-sort-hashmap-by-value?noredirect=1&lq=1 – priyanka Jun 24 '19 at 15:33
  • @GauravSingh: Treemap for getting the unique elements without any duplicates and to get the sorted order – priyanka Jun 24 '19 at 15:35
  • For Treemap (and [red-black trees](http://bigocheatsheet.com/) in general), O(NlogN) to insert N values, and O(N) to traverse. – Gaurav Singh Jun 24 '19 at 17:53