Java Insertion Sorting with ArrayLists of Strings

Question

I have an assignment on sorting which requires me to sort a list of random words by putting letters that start with the same letter in a group/zones and sorting that group alphabetically. My code sorts the words but my problem is that some of the words have changed. For example instead of having an output as

angela
APPLE
Apple
apple
Baboon
Ball
Cat
cat
PINK
Pink
Steve

I would have an output of :

apple
apple
apple
apple
Ball
Ball
cat
cat
Pink
PINK
Steve

As you can see, some of the words have been changed and in some cases, words with a capital letter are turned into lower cases like "cat" and I can't seem to find where my mistake is.

This is my sorting code; my driver class just takes in the list of random words :

import java.util.ArrayList;
import java.util.Collections;

public class ZoneSort 
{


ArrayList[] arrayOfZones;
ArrayList<String> words; 

public ZoneSort(ArrayList<String> words)
{
    arrayOfZones = new ArrayList [ 26 ];
    
    for(int index = 0; index < 26;index++)
        arrayOfZones [ index ] = new ArrayList();
    
    this.words = words; 
    
    putWordsIntoZones();
}

private  void putWordsIntoZones()
{
    for(String word: words)
    {
        int index = Character.toLowerCase(word.charAt(0)) - 97; 
        ArrayList<String> zoneAtIndex = arrayOfZones[index];
        zoneAtIndex.add(word);
    }
}

public  void sortTheArrayOfZones() 
    {
        for(ArrayList<String> zone : arrayOfZones )
        {
            sortZone(zone);
        }
    }


private  void sortZone(ArrayList<String> zone)
{
        for(int i = 1; i < zone.size(); i++)
        {
            String key = zone.get(i);
            int j = i-1;
            while(j>=0 && key.compareTo(zone.get(j)) > 0)
            {
                String x = zone.get(j+1);
                zone.set(j, x);
                j--;
            }
            
            String x = zone.get(j+1);
            x = key;
        }
}   

public   void printArrayOfZones()
{
    System.out.println("The sorted words are");
    for(ArrayList<String> zone:arrayOfZones)
    {
        for(String word: zone)
        {
            
            System.out.println(word);
        }
    }
}

Can you explain what your sortZone method is supposed to do? It doesn't look quite right. — Joni
– Joni, Commented Jul 5, 2020 at 18:26
Clear what you want? What is logic behind change the string uppercase to lowercase ? — Eklavya
– Eklavya, Commented Jul 5, 2020 at 18:31

Anass ABEA · Accepted Answer · 2020-07-05 18:35:03Z

1

Reading your code and viewing your results, it seems that your code overwrites the values instead of swapping them. To fix this you need to take a look at the function sort. I have modified your code so that instead of overwriting, you swap the two elements :

private  void sortZone(ArrayList<String> zone){
    for(int i = 1; i < zone.size(); i++){
        String key = zone.get(i);
        int j = i-1;
        while(j>=0 && key.compareTo(zone.get(j)) > 0){
            String x = zone.get(j+1);
            zone.set(j+1,zone.get(j)); // line added
            zone.set(j, x);
            j--;
        }
        String x = zone.get(j+1);
        x = key;
    }
}

I hope this fixed your problem.

answered Jul 5, 2020 at 18:35

Anass ABEA

4795 silver badges14 bronze badges

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

Comments

Joni · Accepted Answer · 2020-07-05 19:00:19Z

If I compare your sortZone implementation with a reference insertion sort implementation such as https://www.baeldung.com/java-insertion-sort I see the following differences - see inline comments

        for(int i = 1; i < zone.size(); i++)
        {
            String key = zone.get(i);
            int j = i-1;

// The sort order is reversed.
// You've used "key > zone[j]" when it should be "key < zone[j]"

            while(j>=0 && key.compareTo(zone.get(j)) < 0)
            {
// This is copying items backwards, towards the beginning of the array. 
//                String x = zone.get(j+1);
//                zone.set(j, x);
// It should be copying items forwards, towards the end, to make room for "key"
// Like this:
                String x = zone.get(j);
                zone.set(j+1, x);
                j--;
            }
            
// You should be setting zone[j+1] = "key" - this does not do it: 
//            String x = zone.get(j+1);
//            x = key;
// This is how you set a value in a list:
            zone.set(j+1, key);
          
        }

Collectives™ on Stack Overflow

Java Insertion Sorting with ArrayLists of Strings

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related