Нужна помощь в поиске ошибки в сортировке arraylist sort

Я пытаюсь реализовать алгоритм сортировки слияния для arraylists строк, но я не могу найти ошибку, которая заворачивает упорядочивание arraylist.Нужна помощь в поиске ошибки в сортировке arraylist sort

private static void sort(java.util.ArrayList<String> a) 
{ 

    // End recursion 
    if (a.size() < 2) 
    { 
     return; 
    } 


    int mid = a.size()/2; 


    java.util.ArrayList<String> left = new java.util.ArrayList<String>(); 


    int i; 

    for (i = 0; i < mid; i++) 
    { 

     left.add(a.remove(i)); 

    } 


    java.util.ArrayList<String> right = new java.util.ArrayList<String>(); 

    // Copy the second half to the "right" 
    for (; i < a.size(); i++) 
    { 
     right.add(a.remove(i)); 
    } 


    sort(left); 
    sort(right); 

    merge(a, left, right); 
} 

private static void merge(java.util.ArrayList<String> result, java.util.ArrayList<String> left,java.util.ArrayList<String> right) 
{ 
    int i, l, r; 

    i = l = r = 0; 


    while (l < left.size() && r < right.size()) 
    { 
     if ((left.get(l)).compareTo(right.get(r)) < 0) 
     { 
     result.add(left.get(l)); 
     l++; 
     } 
     else 
     { 
     result.add(right.get(r)); 
     r++; 
     } 

     i++; 
    } 


    while (l < left.size()) 
    { 
     result.add(left.get(l)); 
     l++; 
     i++; 
    } 

    // Append rest of the values in the right half, if any... 
    while (r < right.size()) 
    { 
     result.add(right.get(r)); 
     r++; 
     i++; 
    } 
}

источник

2012-05-06 Bob the builder

Это выглядит как домашнее задание, и вы не говорите нам, что вы пробовали или что проблема ... – tonio

На самом деле я сказал вам, в чем проблема, если вы читаете мое заявление. Я говорю: «Кажется, не может найти ошибку, которая заворачивает упорядочение архариста». Другими словами, список массивов упорядочен неправильно. Его список массивов строк так очевидно, что строки не в алфавитном порядке. Также я уверен, вы говорите, что это выглядит как домашнее задание для каждого нового плаката. В любом случае, что вы хотите, чтобы я рассказал вам о том, что я пробовал? Его довольно бесполезно рассказывать то, что ive пыталось, поскольку многие из них ошибочны, так как я относительно новый программист. –

Потому что для сортировки массива строк можно использовать Collections.sort или просто поместить строки в TreeSet, если разумно удалить дубликаты, если только назначение не говорит о реализации сортировки слияния или есть веская причина, чтобы свернуть ваши собственный вид. Который вы не упомянули. – tonio

Вопрос находится в функции sort.

Что происходит, если вы используете a.remove(i)? Элемент с индексом i удаляется из массива, поэтому элемент, который ранее был у индекса i+1, теперь находится в индексе i, а размер массива уменьшен. Если вы затем сделаете i++, и снова a.remove(i), вы пропустите один элемент в массиве.

В вашей функции sort, при звонке merge, вы должны проверить, что a.size() == 0. Вы увидите, что это не всегда так. Функция merge кажется прекрасной, но расщепление вашего массива неверно: вы забываете, что использование remove(int i) изменяет массив; его размер и индексы его элементов.

источник

2012-05-06 08:34:17 tonio

Нужна помощь в поиске ошибки в сортировке arraylist sort

ответ

Смежные вопросы