CODEWITHSUNDEEP
javascriptarraysalgorithmsorting
GirkovArpa
GirkovArpa

Reputation: 4912

Why is my sorting algorithm not sorting correctly?

I was given this sorting function in the best answer to a question I posted. It worked on the example data, but does not appear to work on my actual data and I am not sure why.

My data can be see here: JSON

It's an object of objects like this:

"Montana": {
    "superiors": [
      "Massachusetts",
      "Oklahoma",
      "New Mexico"
    ],
    "inferiors": [
      "North Carolina"
    ]
  }

It exists to instruct the sorting function. Here, Montana must be higher up in the list than North Carolina. But below Massachusetts, Oklahoma, and New Mexico (nothing to do with geography by the way).

Note to avoid confusion:

But the sorting isn't being followed precisely (it's mostly followed though). For example, states['North Carolina'].superiors.includes('Ohio') === true so why is 'Ohio' listed beneath 'North Carolina'?

  fetch('https://api.npoint.io/7571e85ef470a2a7f189')
    .then(data => data.json())
    .then(states => {
      function mySort(arr) {
        const scores = Array(arr.length).fill(0);
        for (let i = 0; i < arr.length; i++) {
          for (let j = 0; j < arr.length; j++) {
            if (i === j) continue;
            const a = arr[i];
            const b = arr[j];
            if (states[a].inferiors.includes(b) || states[b].superiors.includes(a)) scores[j]++;
            else if (states[b].inferiors.includes(a) || states[a].superiors.includes(b)) scores[i]++;
          }
        }
        // Sort arr by scores:
        return arr.map((val, i) => [scores[i], val])
          .sort((a, b) => a[0] - b[0])
          .map(pair => pair[1]);
      }

      const names = Object.keys(states);

      console.log(mySort(names));

      /*
      [
        'Tennessee',     'Oklahoma',             'Alaska',
        'Wisconsin',     'Arkansas',             'New York',
        'Nevada',        'Montana',              'Georgia',
        'Massachusetts', 'Hawaii',               'Connecticut',
        'California',    'Kansas',               'Utah',
        'North Dakota',  'New Mexico',           'Nebraska',
        'Pennsylvania',  'Louisiana',            'New Jersey',
        'Arizona',       'Colorado',             'Maryland',
        'Oregon',        'Missouri',             'Virginia',
        'Rhode Island',  'Mississippi',          'South Carolina',
        'Illinois',      'Texas',                'Florida',
        'Washington',    'District of Columbia', 'Kentucky',
        'Minnesota',     'Iowa',                 'Alabama',
        'New Hampshire', 'Idaho',                'South Dakota',
        'Indiana',       'Michigan',             'North Carolina',
        'Ohio'
      ]
      */
      // states['North Carolina'].superiors.includes('Ohio') === true
      // so why is 'Ohio' listed beneath 'North Carolina'?
    });

Here is the JSON data in case the data in my link gets vandalized:

{"Iowa":{"inferiors":[],"superiors":["Alaska","Oklahoma","California","Hawaii","New Jersey","Virginia","Florida","Washington","Minnesota","Texas","Idaho","Alabama","Ohio"]},"Ohio":{"inferiors":["North Carolina","Michigan","Iowa","New Hampshire"],"superiors":["New York","California","Arizona","Illinois","Texas","Pennsylvania","Florida","Indiana","Tennessee","Massachusetts","Washington","Colorado","District of Columbia","Maryland","Kentucky","Oregon","Oklahoma","Wisconsin","Nevada","New Mexico","Missouri","Virginia","Georgia","Nebraska","Minnesota","Louisiana","Hawaii","Alaska","New Jersey","Idaho","Alabama","Arkansas","Utah","Rhode Island","Mississippi","South Carolina","Connecticut","Montana","Kansas","North Dakota","South Dakota"]},"Utah":{"inferiors":["Idaho","South Dakota","Ohio","Michigan"],"superiors":["New York"]},"Idaho":{"inferiors":["Ohio","Iowa","South Dakota","Michigan","North Carolina"],"superiors":["Alaska","Oklahoma","California","Hawaii","Minnesota","New Jersey","Virginia","Florida","Washington","Texas","New York","Louisiana","Illinois","Arkansas","Utah","Rhode Island","Mississippi","Maryland","Nebraska","District of Columbia","Kentucky","Connecticut"]},"Texas":{"inferiors":["North Carolina","Michigan","Ohio","Indiana","Idaho","Alabama","Iowa"],"superiors":["New York","California","Tennessee","Massachusetts","Oklahoma","Wisconsin","Nevada","New Mexico","Alaska","Hawaii"]},"Alaska":{"inferiors":["California","Hawaii","New Jersey","Virginia","Florida","Washington","Minnesota","Texas","Idaho","Alabama","Ohio","Iowa","New Mexico","Mississippi","Rhode Island","North Dakota","South Carolina","District of Columbia","Colorado","Arizona","Kentucky","New Hampshire","Oregon","Nebraska","Illinois","Indiana","South Dakota","North Carolina"],"superiors":["Tennessee"]},"Hawaii":{"inferiors":["Minnesota","Kentucky","Washington","Pennsylvania","Illinois","Georgia","Maryland","Ohio","New Jersey","Virginia","Florida","Texas","Idaho","Alabama","Iowa","Mississippi","Rhode Island","North Dakota","South Carolina","District of Columbia","Colorado","Arizona","New Hampshire","Missouri","Utah","Louisiana","Michigan"],"superiors":["New York","Tennessee","Oklahoma","Alaska","Nevada"]},"Kansas":{"inferiors":["Indiana","North Carolina"],"superiors":["Wisconsin","New York","California"]},"Nevada":{"inferiors":["California","New Mexico","Illinois","Texas","Missouri","Virginia","District of Columbia","Ohio","North Carolina","Michigan","Maryland","Colorado","Arizona","Oregon","Indiana","Kentucky","Louisiana","Florida","Hawaii","Massachusetts","South Carolina","Mississippi","Minnesota","North Dakota","New Hampshire","Rhode Island","Washington","Utah","New Jersey","Nebraska","Alabama","South Dakota"],"superiors":["Tennessee","Oklahoma","Wisconsin"]},"Oregon":{"inferiors":["Ohio","Indiana","North Carolina","Michigan","Alabama","South Dakota"],"superiors":["New York","Tennessee","Massachusetts","Oklahoma","Wisconsin","California","Nevada","Alaska"]},"Alabama":{"inferiors":["Ohio","Iowa","North Carolina"],"superiors":["Tennessee","Nevada","Alaska","Nebraska","New Mexico","New Jersey","Kentucky","Oregon","Rhode Island","Illinois"]},"Arizona":{"inferiors":["Indiana","Ohio","North Carolina","Michigan","New Hampshire"],"superiors":["California","New York","Tennessee","Massachusetts","Wisconsin","Nevada","New Mexico","Alaska","Hawaii"]},"Florida":{"inferiors":["Indiana","Ohio","North Carolina","Michigan","Iowa","Idaho","South Dakota"],"superiors":["Tennessee","New York","Massachusetts","Wisconsin","California","New Mexico","Oklahoma","Nevada","Alaska","Hawaii"]},"Georgia":{"inferiors":["Ohio"],"superiors":["Tennessee","New York","Oklahoma"]},"Indiana":{"inferiors":["Ohio","North Carolina","Michigan","South Dakota"],"superiors":["New York","California","Arizona","Illinois","Texas","Pennsylvania","Florida","Oklahoma","Tennessee","Wisconsin","Oregon","District of Columbia","Maryland","Virginia","Washington","Missouri","Nebraska","Colorado","Kansas","Kentucky","Nevada","Louisiana","New Mexico","Minnesota","Rhode Island","Connecticut","Mississippi","Alaska","New Jersey"]},"Montana":{"inferiors":["North Carolina"],"superiors":["Massachusetts","Oklahoma","New Mexico"]},"Arkansas":{"inferiors":["South Dakota","Ohio","Michigan"],"superiors":["New York","California"]},"Colorado":{"inferiors":["Ohio","Michigan","North Carolina"],"superiors":["New York","Tennessee","Massachusetts","Wisconsin","California","Nevada"]},"Illinois":{"inferiors":["Indiana","Ohio","Michigan","South Dakota","Alabama","North Carolina"],"superiors":["New York","California","Tennessee","Massachusetts","Oklahoma","Wisconsin","Nevada","New Mexico","Hawaii"]},"Kentucky":{"inferiors":["Ohio","Indiana","Michigan","North Carolina","Idaho","South Dakota","New Hampshire"],"superiors":["New York","Tennessee","Massachusetts","Wisconsin","Nevada","California","Oklahoma","Hawaii","New Mexico","Alaska"]},"Maryland":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Idaho","South Dakota"],"superiors":["New York","Tennessee","Massachusetts","Oklahoma","California","Wisconsin","Nevada","New Mexico"]},"Michigan":{"inferiors":[],"superiors":["Florida","New York","California","Illinois","Texas","Pennsylvania","Arizona","Tennessee","Oklahoma","Wisconsin","Nevada","New Mexico","District of Columbia","Missouri","Virginia","North Carolina","Ohio","Washington","Georgia","Maryland","Nebraska","Colorado","Indiana","Oregon","Louisiana","Kentucky","Massachusetts","Hawaii","Rhode Island","Mississippi","Utah"]},"Missouri":{"inferiors":["Ohio","North Carolina","Michigan","Indiana"],"superiors":["Tennessee","Oklahoma","Wisconsin","California","Nevada","New Mexico","New York","Massachusetts","Hawaii"]},"Nebraska":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Idaho","South Dakota","Alabama"],"superiors":["New York","Tennessee","California","New Mexico","Oklahoma","Nevada","Alaska"]},"New York":{"inferiors":["California","Illinois","Texas","Pennsylvania","Arizona","Florida","Indiana","Ohio","North Carolina","Michigan","Washington","Colorado","District of Columbia","Maryland","Kentucky","Oregon","Massachusetts","New Mexico","Minnesota","Missouri","Nebraska","Virginia","Kansas","Louisiana","Georgia","Hawaii","Arkansas","Utah","Rhode Island","Mississippi","Idaho","South Dakota","South Carolina","New Jersey","Connecticut","New Hampshire"],"superiors":["Wisconsin","Tennessee","Oklahoma"]},"Oklahoma":{"inferiors":["Nevada","California","New Mexico","Illinois","Texas","Missouri","Virginia","District of Columbia","Ohio","North Carolina","Michigan","Wisconsin","Oregon","Maryland","Washington","Indiana","New York","Hawaii","Minnesota","Kentucky","Pennsylvania","Georgia","Florida","Louisiana","Idaho","South Dakota","Nebraska","Rhode Island","Connecticut","Mississippi","South Carolina","New Jersey","New Hampshire","Montana","Kansas"],"superiors":["Tennessee"]},"Virginia":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Iowa","Idaho","South Dakota"],"superiors":["Tennessee","Oklahoma","Wisconsin","California","Nevada","New Mexico","New York","Alaska","Hawaii"]},"Louisiana":{"inferiors":["Indiana","Ohio","Michigan","Idaho","South Dakota"],"superiors":["Nevada","New York","California","Tennessee","New Mexico","Oklahoma"]},"Minnesota":{"inferiors":["Ohio","North Carolina","Idaho","Alabama","Iowa","South Dakota","Michigan","Indiana","New Hampshire"],"superiors":["Wisconsin","New York","California","Massachusetts","New Mexico","Tennessee","Oklahoma","Hawaii","Alaska","Nevada"]},"Tennessee":{"inferiors":["Illinois","Washington","Florida","Colorado","District of Columbia","Texas","Maryland","Kentucky","Oregon","Arizona","Ohio","Oklahoma","Wisconsin","Nevada","California","New Mexico","Missouri","Virginia","North Carolina","Michigan","Georgia","Nebraska","Indiana","Pennsylvania","New York","Hawaii","Minnesota","Louisiana","Rhode Island","Mississippi","Utah","Alaska","New Jersey","Alabama","South Dakota"],"superiors":[]},"Wisconsin":{"inferiors":["Nevada","California","New Mexico","Illinois","Texas","Missouri","Virginia","District of Columbia","Ohio","North Carolina","Michigan","Oregon","Maryland","Washington","Indiana","Massachusetts","Pennsylvania","Florida","Minnesota","New York","Kansas","Arizona","Kentucky","Colorado"],"superiors":["Oklahoma","Tennessee"]},"California":{"inferiors":["Illinois","Texas","Pennsylvania","Arizona","Florida","Indiana","Ohio","North Carolina","Michigan","Missouri","Virginia","District of Columbia","Oregon","Maryland","Washington","Massachusetts","New Mexico","Minnesota","Nebraska","Colorado","Kansas","Kentucky","Louisiana","New Jersey","Idaho","Alabama","Iowa","Arkansas","Utah","Rhode Island","Mississippi","South Dakota","South Carolina","Connecticut","New Hampshire"],"superiors":["New York","Tennessee","Oklahoma","Wisconsin","Nevada","Alaska"]},"New Jersey":{"inferiors":["Iowa"],"superiors":["Alaska","Oklahoma","California","Hawaii","New York","New Mexico","Tennessee","Nevada"]},"New Mexico":{"inferiors":["Illinois","Texas","Missouri","Virginia","District of Columbia","Ohio","North Carolina","Michigan","Pennsylvania","Florida","Minnesota","Indiana","Kentucky","Louisiana","Arizona","Washington","Nebraska","Maryland","South Carolina","New Jersey","Rhode Island","Connecticut","New Hampshire","Mississippi","North Dakota","Colorado","Montana","Kansas","Oregon","Alabama","South Dakota"],"superiors":["Wisconsin","Tennessee","Oklahoma","New York","California","Nevada","Alaska"]},"Washington":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Iowa"],"superiors":["Tennessee","New York","Massachusetts","California","Oklahoma","Wisconsin","New Mexico","Hawaii","Alaska","Nevada"]},"Connecticut":{"inferiors":["Idaho","Indiana","South Dakota","North Carolina","Ohio","New Hampshire"],"superiors":["New York","Oklahoma","New Mexico","Massachusetts"]},"Mississippi":{"inferiors":["Idaho","South Dakota","Ohio","Michigan","Indiana","North Carolina","New Hampshire"],"superiors":["Alaska","Tennessee","Hawaii","New Mexico","Nevada","Massachusetts"]},"North Dakota":{"inferiors":["Ohio","New Hampshire"],"superiors":["Alaska","Tennessee","Hawaii","New Mexico","Nevada","Massachusetts"]},"Pennsylvania":{"inferiors":["North Carolina","Michigan","Indiana","Ohio","New Hampshire"],"superiors":["New York","California","Wisconsin","New Mexico","Massachusetts","Tennessee","Oklahoma","Hawaii"]},"Rhode Island":{"inferiors":["Idaho","South Dakota","Ohio","Michigan","Indiana","North Carolina","New Hampshire","Alabama"],"superiors":["New York","Oklahoma","New Mexico","California","Alaska","Tennessee","Hawaii","Nevada","Massachusetts"]},"South Dakota":{"inferiors":["Ohio","North Carolina"],"superiors":["New York","California","Illinois","Arkansas","Louisiana","Minnesota","Utah","Rhode Island","Florida","Mississippi","Maryland","Idaho","Oklahoma","Nebraska","District of Columbia","Kentucky","Connecticut","Virginia","Indiana"]},"Massachusetts":{"inferiors":["Illinois","Washington","Florida","Colorado","District of Columbia","Texas","Maryland","Kentucky","Oregon","Arizona","Ohio","Pennsylvania","Minnesota","Indiana","North Carolina","Montana","Connecticut","Rhode Island","Kansas","South Carolina","Mississippi","North Dakota","New Hampshire","Missouri","Utah","Louisiana","Michigan"],"superiors":["Wisconsin","New York","California","Nevada","Tennessee"]},"New Hampshire":{"inferiors":[],"superiors":["Oklahoma","New York","New Mexico","California","Pennsylvania","Maryland","South Carolina","Virginia","New Jersey","Rhode Island","Connecticut","Alaska","Nevada","Hawaii","Massachusetts","Mississippi","Minnesota","Arizona","North Dakota","Kentucky","Ohio"]},"North Carolina":{"inferiors":["Michigan"],"superiors":["New York","California","Texas","Illinois","Pennsylvania","Arizona","Florida","Indiana","Ohio","Wisconsin","Tennessee","Oklahoma","New Mexico","Nevada","Washington","Georgia","District of Columbia","Missouri","Maryland","Nebraska","Massachusetts","Minnesota","Colorado","Oregon","Virginia","Kentucky","Rhode Island","Connecticut","Mississippi","Idaho","Montana","Kansas","Alaska","New Jersey","Alabama","South Dakota"]},"South Carolina":{"inferiors":["New Hampshire"],"superiors":["Oklahoma","New York","New Mexico","California","Alaska","Tennessee","Hawaii","Nevada","Massachusetts"]},"District of Columbia":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Idaho","South Dakota"],"superiors":["New York","Tennessee","Massachusetts","Wisconsin","Oklahoma","California","Nevada","New Mexico","Alaska","Hawaii"]}}

Upvotes: 0

Views: 115

Answers (2)

Robo Robok
Robo Robok

Reputation: 22663

Your data doesn't contain contradictions, but it certainly doesn't list everything correctly.

Example: Iowa-Oklahoma pair. Oklahoma is listed as being superior to Iowa, but Iowa is not listed as being inferior to Oklahoma.

Upvotes: 1

Bergi
Bergi

Reputation: 664207

You have a partial order only not a total order (not all states list all others in their superiors/inferiors list), so your score calculation doesn't work. States end up with a score depending on how often they were mentioned, not what their relative order is. You'll need to implement a topological sort algorithm.

Upvotes: 1

Related Questions