Java ShellSort ordena o array de string parcialmente invés de ordenar tudo.

[Brian Nicolas]

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class TrabalhoPratico {
    public static void main(String[] args) {
        // write your code here
        List<String> lista = new ArrayList<String>();
        String filename = "D:\\Downloads\\entrada-100-dec.txt";
        try {
            FileReader fr = new FileReader(filename);
            BufferedReader in = new BufferedReader(fr);
            String line = in.readLine();
            while (line != null) {
                lista.add(line);
                line = in.readLine();
            }
            in.close();
        } catch (FileNotFoundException e) {
            System.out.println("Arquivo \"" + filename + "\" não existe.");
        } catch (IOException e) {
            System.out.println("Erro na leitura do arquivo " + filename + ".");
        }

        String[] array = lista.toArray(new String[0]);
        ShellSort shellSort = new ShellSort();
        shellSort.sort(array);

    }
}

class ShellSort {
    public void sort(String[] arr) {
        // String[] arr = { "Elissa Eichmann",
        // "Meghan Johns III",
        // "Naomie Beier",
        // "Stephon Miller",
        // "Dexter Harber",
        // "Gerda Toy",
        // "Mabel Zemlak",
        // "Gage Gerhold",
        // "Berry Schaden",
        // "Roman Daniel",
        // "Lily Krajcik" };
        int counter = 0;
        int tamanho = arr.length;

        for (int gap = tamanho / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < tamanho; i++) {
                String aux = arr[i];
                int j;
                for (j = i; j >= gap && compara(arr[j], arr[j - gap]); j -= gap) {
                    counter++;
                    arr[j] = arr[j - gap];
                }
                arr[j] = aux;
            }
        }
        for (String string : arr) {
            System.out.println(string);
        }
        System.out.println(" Comparacoes:" + counter);
    }

    private static boolean compara(String v, String w) {
        return v.compareTo(w) < 0;
    }

    // private static boolean comparaString(Comparable v, Comparable w) {
    // return v.compareTo(w) < 0;
    // }

}

 

[AdrianoSiqueira]

Veja se isso te ajuda:

package teste.cdh.shellsort;

import java.util.Comparator;

public class ShellSort<T> {

    /**
     * Based on: https://www.tutorialspoint.com/java-program-for-shellsort
     */
    public void sort(T[] array, Comparator<T> comparator) {
        int length = array.length;

        for (int gap = length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < length; i += 1) {
                T   temp = array[i];
                int j;

                for (j = i; j >= gap && comparator.compare(array[j - gap], temp) > 0; j -= gap)
                     array[j] = array[j - gap];

                array[j] = temp;
            }
        }
    }

    /**
     * From: https://www.tutorialspoint.com/java-program-for-shellsort
     */
    public void sort(int[] array) {
        int length = array.length;

        for (int gap = length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < length; i += 1) {
                int temp = array[i];
                int j;

                for (j = i; j >= gap && array[j - gap] > temp; j -= gap)
                     array[j] = array[j - gap];

                array[j] = temp;
            }
        }
    }
}

 

package teste.cdh.shellsort;

public class Person {

    public String name;
    public int    age;

    public Person(String name, int age) {
        this.name = name;
        this.age  = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Person person = (Person) o;

        if (age != person.age) return false;
        return name.equals(person.name);
    }

    @Override
    public int hashCode() {
        int result = name.hashCode();
        result = 31 * result + age;
        return result;
    }

    @Override
    public String toString() {
        return "Person{" +
               "name='" + name + '\'' +
               ", age=" + age +
               '}';
    }
}

 

package teste.cdh.shellsort;

import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Comparator;

class ShellSortTest {

    @Test
    void sort_SortsTheIntArray_WhenSuccessful() {
        int[] array = {5, 4, 3, 2, 1};

        new ShellSort<Integer>()
                .sort(array);

        Assertions.assertThat(array)
                  .isEqualTo(new int[]{1, 2, 3, 4, 5});
    }

    @Test
    void sort_SortsTheIntegerArrayWithComparator_WhenSuccessful() {
        Integer[]           array      = {5, 4, 3, 2, 1};
        Comparator<Integer> comparator = Integer::compareTo;

        new ShellSort<Integer>()
                .sort(array, comparator);

        Assertions.assertThat(array)
                  .isEqualTo(new Integer[]{1, 2, 3, 4, 5});
    }

    @Test
    void sort_SortsThePersonArrayWithComparator_WhenSuccessful() {
        Person[] array = {
                new Person("D", 2),
                new Person("D", 1),
                new Person("C", 3),
                new Person("B", 4),
                new Person("A", 5)
        };

        Person[] expectedResult = {
                new Person("A", 5),
                new Person("B", 4),
                new Person("C", 3),
                new Person("D", 1),
                new Person("D", 2)
        };

        // sort by name in alphabetical order
        // if the names are equals then sort by age ascending
        Comparator<Person> comparator = Comparator.comparing((Person o) -> o.name)
                                                  .thenComparingInt(o -> o.age);

        new ShellSort<Person>()
                .sort(array, comparator);

        Assertions.assertThat(array)
                  .isEqualTo(expectedResult);
    }

    @Test
    void sort_SortsTheStringArrayWithComparator_WhenSuccessful() {
        String[]           array      = {"5", "4", "3", "2", "1"};
        Comparator<String> comparator = String::compareTo;

        new ShellSort<String>()
                .sort(array, comparator);

        Assertions.assertThat(array)
                  .isEqualTo(new String[]{"1", "2", "3", "4", "5"});
    }
}