Radix сортировка в обратном порядке в Java

Question

У меня проблемы с пониманием сортировки по основам. Я должен отсортировать последнюю букву слова, как сортировать справа налево, пока не останется больше букв.

Текстовый файл выглядит так

бар кошка яблоко жук зубчатый капер рога медведь лодыжка

Мой вывод, как это

лодыжка рога яблоко бар медведь жук каперсов кошка винтик

Но я должен получить вывод, как это

бар ошибка кошка зубец медведь лодыжка яблоко капер рога

Такое ощущение, что я близок к тому, чтобы иметь правильный код, но я застрял и не знаю, что еще делать. Было бы очень признательно, если бы я мог получить помощь и указать мне в правильном направлении

Вот код, что я сделал

RadixSort.java

  public class RadixSort {
      public static void main(String[]args) throws FileNotFoundException{
    Linkedlist[] allNameLinkedList = new Linkedlist[26]; // create an array 
        of LinkedList for 26 letters in alphabets
    int count = 0;
    // initialize all the elements in the array to new LinkedList
    for (int i = 0; i < allNameLinkedList.length; i++) {
        allNameLinkedList[i] = new Linkedlist();
    }
    Scanner scan = new Scanner(new File("words.txt"));

    while(scan.hasNextLine())
    {
        String currentname = scan.nextLine();
        for(int i = 0; i < 26; i++){
            if(currentname.charAt(2) == (char)(i+97))
            {
                allNameLinkedList[i].addNodeToTheEndOfTheList(currentname);
            }
        }
        count++;
    }

    // copy sorted nodes to new LinkedList called container
    Linkedlist container = new Linkedlist();
    for (int i = 0; i < 26; i++) {
        Node n = allNameLinkedList[i].front;

        while(n != null){
            container.addNodeToTheEndOfTheList(n.name);
            n = n.next;
        }
    }
    // empty all the elements of array
    for (int i = 0; i < allNameLinkedList.length; i++) {
        allNameLinkedList[i] = new Linkedlist();
    }

    Node m = container.front;
    while(m!=null)
    {
        String currentname = m.name;
        for(int i = 0; i < 26; i++){
            if(currentname.charAt(1) == (char)(i+97))
            {
                allNameLinkedList[i].addNodeToTheEndOfTheList(currentname);
            }
        }
        m = m.next;
        count++;
    }
    container = new Linkedlist();
    for (int i = 0; i < 26; i++) {
        m = allNameLinkedList[i].front;

        while(m!=null){
            container.addNodeToTheEndOfTheList(m.name);
            m = m.next;
        }
    }
    for (int i = 0; i < allNameLinkedList.length; i++) {
        allNameLinkedList[i] = new Linkedlist();
    }
    m = container.front;

    while(m!=null)
    {
        String currentname = m.name;

        for(int i = 0; i < 26; i++){
            if(currentname.charAt(0) == (char)(i+97))
            {
                allNameLinkedList[i].addNodeToTheEndOfTheList(currentname);
            }
        }
        m = m.next;
        count++;
    }
    container = new Linkedlist();
    for (int i = 0; i < 26; i++) {
        m = allNameLinkedList[i].front;

        while(m!=null){
            System.out.println(m.name);
            container.addNodeToTheEndOfTheList(m.name);
            m = m.next;
        }
    }
    scan.close();
    System.out.println("The total number of comparisions was :"+count);
    }
    }

Answer 1

Ваша проблема в том, что сортируют только первый символ.

while(m!=null)
    {
        String currentname = m.name;

        for(int i = 0; i < 26; i++){
            // charAt(0) is first character in String
            if(currentname.charAt(0) == (char)(i+97)) 
            {
                allNameLinkedList[i].addNodeToTheEndOfTheList(currentname);
            }
        }
        m = m.next;
        count++;
    }

Вы должны перебирать каждого персонажа, а не только первого. Это объясняет, почему ваш вид в алфавитном порядке. Как это в идеальном лексикографическом порядке, мне не под силу. Фрагмент кода будет сортировать данные только в их "списки" связанных списков на основе charAt(0).

Ваши входные и выходные данные выглядят так, как будто они не суммируются, потому что входные данные не отсортированы, а ваши выходные данные фактически соответствуют тому, что вы должны иметь для сортировки по алфавиту: MSD Radix sort.

Наиболее значимая цифра - это то, что вы хотите для буквенных сравнений, потому что в случае лексикографического порядка более высокие сравнительные величины являются первыми символами. Другими видами могут быть LSD (наименее значимые цифры), как при сравнении целых чисел, но следует предупредить, что сортировка по LSD Radix здесь не подходит, потому что вам нужно беспокоиться о строках разной длины.

С сортировкой MSD Radix ничего страшного. Вы просто убедитесь, что не превышаете диапазон слова и не перемещаете его после того, как оно помещено, если только оно не перемещается другим словом. С ЛСД, вы должны индексировать в обратном направлении, сначала проверяя, если ваш current word length - current index > 0 прежде чем продолжить сортировку с вашим фактическим характером charAt(word length - current index), но ваш конечный результат, скорее всего, никогда не будет по-настоящему упорядочен по алфавиту - я не вижу особой цели в сортировке радиуса LSD по алфавиту, если только это не является проверкой концепции, которую вы можете заказать таким образом или задание, специально данное вам таким образом, чтобы Ваш конечный результат заказан только частично.

Во-вторых, ваша логика сортировки после каждой итерации, по-видимому, отсутствует. Вы должны сортировать внутри каждой корзины на каждой итерации, чтобы убедиться, что все в порядке сортировки.