Сортировка массива строк

Question

Итак, я пытаюсь отсортировать массив строк с помощью алгоритма.

ПРИМЕЧАНИЕ. Для этого назначения мне не разрешено использовать какие-либо встроенные функции сортировки.

public boolean insert(String s) 
{ 
    boolean result = false; 
    int index = 0; 
    int k = 0; 
    String temp = ""; 

    if (numUsed < values.length) 
    { 
    if (index == 0) 
    { 
     values[index] = s; 
    }  
    else 
    { 
     index = 0; 
     while (values[index].compareTo(s) < 0); 
     k = index; 
     while (k < numUsed) 
     { 
     values[k + 1] = values[k]; 
     } 
     values[index] = s; 
    } 
    numUsed++; 
    result = true; 
    } 
} 

Учитывая ввод «яблоки», «кошки» и «пчел» выход находится в том же порядке, что это был вход. Независимо от того, что я делаю, он просто никогда не сортируется.

Может кто-нибудь помочь мне найти проблему?

Answer 1

Начните с изучения основ. Представьте, что у вас есть большая куча индексных карт, отсортированных случайным образом перед вами, и вам нужно их алфавит. Простой, но работоспособный метод состоит в том, чтобы сначала найти все слова, начинающиеся с A, и поместить их в отдельную кучу (подсказка: как вы можете имитировать отдельную кучу в вашей программе?). Затем вы пойдете по первой куче, найдите все слова, начинающиеся с буквы B, и верните их в назад вашей сортированной кучи (другой намек).

Я бы рекомендовал отложить ваш текущий код и начать новый. Напишите цикл, который проходит через несортированный массив, и находит слово, самое близкое к началу словаря. Вот некоторые psuedocode, чтобы вы начали с этим:

String leastSoFar = "ZZZZZZ"; 
for each String in values: 
    compare the string to leastSoFar 
    if the string is closer to the start of the dictionary than leastSoFar: 
     leastSoFar = ???? //I'll let you fill those in 

Answer 2

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

Если вы просто пытаетесь реализовать простой алгоритм сортировки, простым (но не оптимальным) алгоритмом, который легко кодировать, является «замедленная замена». ПСЕВДОКОД FPR алгоритма для сортировки в порядке возрастания описан кратко ниже: алгоритм сортировки

Begin DELAYEDSORT 
    For ITEM=1 to maximum number of items in list-1 
     LOWEST=ITEM 
     For N=ITEM+1 to maximum number of items in list 
      Is entry at position N lower than entry at position LOWEST? 
       If so, LOWEST=N 
     Next N 
     Is ITEM different from LOWEST 
      If so, swap entry at LOWEST with entry in ITEM 
    Next ITEM 
    End DELAYEDSORT 

Задержанный замены легко понять и легко кода. Это обычно быстрее, чем сортировка пузырьков (меньше свопов), но все еще имеет сложную сложность O (n^2), и поэтому не подходит для сортировки очень больших наборов данных.

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

Альтернативное решение, которое все еще имеет O (N^2) временную сложность, но которые могут быть адаптированы, чтобы объединить добавление и сортировка является «сортировка вставкой», чьи псевдокод приводится ниже:

// The values in A[i] are checked in-order, starting at the second one 
for i ← 1 to i ← length(A) 
    { 
    // at the start of the iteration, A[0..i-1] are in sorted order 
    // this iteration will insert A[i] into that sorted order 
    // save A[i], the value that will be inserted into the array on this iteration 
    valueToInsert ← A[i] 
    // now mark position i as the hole; A[i]=A[holePos] is now empty 
    holePos ← i 
    // keep moving the hole down until the valueToInsert is larger than 
    // what's just below the hole or the hole has reached the beginning of the array 
    while holePos > 0 and valueToInsert < A[holePos - 1] 
     { //value to insert doesn't belong where the hole currently is, so shift 
     A[holePos] ← A[holePos - 1] //shift the larger value up 
     holePos ← holePos - 1  //move the hole position down 
     } 
    // hole is in the right position, so put valueToInsert into the hole 
    A[holePos] ← valueToInsert 
    // A[0..i] are now in sorted order 
    }