Using an insertion sort algorithm using more than one field from an array of objects

Question

I have to sort an array with state objects and sort it by region number, and population. I have imported this information from a text file so these are strings. I can sort using one of the fields but cant get it to work with both. It always just ends up sorting the last sort called in the method. For instance in my code it just finishes with sorting the region number, which unsorts the population. Is there anyway to sort by population, and then from that sort, sort the region number. Also, i cant use anything from java.util.

public void insertionSort()
    {
        int in, out;

        for (out = 1; out < getElementCount(); out++)
        {
            State temp = states[out];
            in = out;

            while (in > 0 && states[in - 1].getPopulation().compareTo(temp.getPopulation()) > 0)
            {
                states[in] = states[in - 1];
                --in;
            }
            states[in] = temp;

        }
         for (out = 1; out < getElementCount(); out++)
        {
            State temp = states[out];
            in = out;

            while (in > 0 && states[in - 1].getRegionNumber().compareTo(temp.getRegionNumber()) > 0)
            {
                states[in] = states[in - 1];
                --in;
            }
            states[in] = temp;
    }
    }




 public void Execute()
    {
        StateCollection sc = new StateCollection();

        String filename = "States.Search.txt";
        String file = "States.Input.txt";

        String[] stateSearch = new String[15];
        String[] state = new String[50];


        stateSearch = readFile(filename, stateSearch);
        state = readFile(file, state);

        for (int i = 0; i < state.length; i++)
        {

            String stateName = state[i].substring(0, 15).trim();
            String stateCapital = state[i].substring(15, 30).trim();
            String abbr = state[i].substring(30, 32).trim();
            String population = state[i].substring(32, 40).trim();
            String region = state[i].substring(40, 55).trim();
            String regionNumber = state[i].substring(55).trim();

            State s = new State(stateName, stateCapital, abbr, population, region, regionNumber);

            sc.add(i, s);


        }


        sc.bubbleSort();

Unless you have a lot of identical population counts, you should really start by sorting everything according to region, then doing a separate sort by population for each region. — samhareem
– samhareem, Commented Sep 26, 2015 at 6:30
Why can't you use "anything from java.util"? It would be the correct approach to either have your State class implement Comparable (which is in package java.lang by the way) or write a Comparator (in package java.util) for it. — Seelenvirtuose
– Seelenvirtuose, Commented Sep 26, 2015 at 6:41
This is for a data structures course so im not allowed to use the prebuilt methods — Codylee14
– Codylee14, Commented Sep 26, 2015 at 14:00

Community · Accepted Answer · 2017-05-23 10:27:00Z

1

Separate your problem into smaller problems which are easier to solve.

Sorting logic :

public void insertionSort() {
    int in, out;

    for (out = 1; out < getElementCount(); out++) {
        State temp = states[out];
        in = out;

        while (in > 0 && compare(states[in-1], temp) > 0) {
            states[in] = states[in - 1];
            --in;
        }
        states[in] = temp;

    }
}

Comparision logic :

int compare( State a, State b )
{
    int comparePopulation =  a.getPopulation().compareTo(b.getPopulation());
    if ( comparePopulation!=0 )
        return comparePopulation;
    else
        return a.getRegionNumber().compareTo(b.getRegionNumber());
}

That sorts 1st by population and then by region number.

Here follows a Minimal, Complete, and Verifiable example

import java.util.concurrent.ThreadLocalRandom;

class Test {

static int compare(State a, State b) {
    int comparePopulation = a.getPopulation().compareTo(b.getPopulation());
    if (comparePopulation != 0) {
        return comparePopulation;
    } else {
        return a.getRegionNumber().compareTo(b.getRegionNumber());
    }
}

static void insertionSort() {
    int in, out;

    for (out = 1; out < getElementCount(); out++) {
        State temp = states[out];
        in = out;

        while (in > 0 && compare(states[in - 1], temp) > 0) {
            states[in] = states[in - 1];
            --in;
        }
        states[in] = temp;

    }
}

static class State {

    private final Integer population;
    private final Integer regionNumber;

    public State(int population, int regionNumber) {
        this.population = population;
        this.regionNumber = regionNumber;
    }

    public static State getRandomState() {
        return new State(ThreadLocalRandom.current().nextInt(10, 14),
                ThreadLocalRandom.current().nextInt(1, 4));
    }

    public Integer getRegionNumber() {
        return regionNumber;
    }

    public Integer getPopulation() {
        return population;
    }

    @Override
    public String toString() {
        return "P=" + population + " R=" + regionNumber;
    }
}

static int getElementCount() {
    return states.length;
}

static State[] states;

public static void main(String[] args) {
    // Create 10 random states
    states = new State[10];
    for (int n = 0; n < 10; ++n) {
        states[n] = State.getRandomState();
    }
    // Print them
    System.out.println("----States unsorted----");
    for (State s : states) {
        System.out.println(s);
    }
    // Sort
    insertionSort();
    // Print them sorted
    System.out.println("----States sorted----");
    for (State s : states) {
        System.out.println(s);
    }
}

}

It generates 10 random states, prints them, sorts them and prints them sorted. In the output we can see that the states are properly sorted 1st by population and among those with the same population they are "sub-sorted" by region number.

----States unsorted----
P=10 R=1
P=10 R=2
P=12 R=1
P=11 R=2
P=11 R=2
P=13 R=1
P=12 R=2
P=13 R=1
P=10 R=2
P=12 R=1
----States sorted----
P=10 R=1
P=10 R=2
P=10 R=2
P=11 R=2
P=11 R=2
P=12 R=1
P=12 R=1
P=12 R=2
P=13 R=1
P=13 R=1

edited May 23, 2017 at 10:27

CommunityBot

11 silver badge

answered Sep 26, 2015 at 6:46

Anonymous Coward

3,2101 gold badge25 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Codylee14 Over a year ago

I can still only get this code to sort one of the fields. Although it looks correct i cant get it to work. Also for the last .compareTo(b) I assumed that was suppose to be compareTo(b.getRegionNumber); correct? Any ideas why the above code may not be working correctly?

Anonymous Coward Over a year ago

Yes, last compareTo was supposed to be against b.getRegionNumber(), I've corrected it. Hard to tell what does not work for you without a complete example. May you provide the minimal code for State needed to make your example compile?

Codylee14 Over a year ago

I added some more code. Its at the bottom in my execute method. Im not sure if thats what you wanted or not. I found that in the code you provided too that if you change the (comparePopulationtion !=0) which sorts by population to (comparePopulation == 0) than it sorts by region number. Again, im just missing something on how to make it sort using both. Thanks for the help

Anonymous Coward Over a year ago

What I wanted was the class State. But never mind I have simulated one. Try and run the complete example in my updated answer you will see that it sorts correctly 1st by population then by region number. Just adapt that to your needs.

Codylee14 Over a year ago

Thank you so much!! That did it. I just needed to switch it to sort the region first then the population because there weren't two populations that were the same so it was coming back looking like unsorted regions. Thanks again. Your the man!

|

Vaseph · Accepted Answer · 2015-09-26 07:03:29Z

0

You can declare State class that implements Comparator as follow:

  public class State implements Comparator<State> {
     // your fields
     // getter and setter;
    @Override
    public int compare(State o1, State o2) {
      int sort1 = o1.getPopulation().compareTo(o2.getPopulation());
      if (sort1 != 0) {
         return sort1;
      }
      int sort2 = o1.getRegionNumber().compareTo(o2.getRegionNumber());
      if (sort2 != 0) {
         return sort2;
      }
      else{
       // other fields as you like. 
      }
   }

 }

answered Sep 26, 2015 at 7:03

Vaseph

7121 gold badge9 silver badges20 bronze badges

Collectives™ on Stack Overflow

Using an insertion sort algorithm using more than one field from an array of objects

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related