Общие проблемы с пузырьками arraylist

Question

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

Итак, вот что я имел, совершив одну ошибку для другой для другого, до сих пор у меня есть только ошибки в двух местах (заключенные в маркеры «**»), с необходимостью выяснить, как сравнивать.

package sort; 
import java.util.ArrayList; 

public abstract class Sort<E> implements Comparable<E> { 

    public void swap(ArrayList<E> a, int i, int j) { 
    E c = a.get(i); 
    a.set(i,a.get(j));// = a[j]; 
    a.set(j, c); 
    } 

    public void bubbleSort(ArrayList<E> a) { 
    boolean inOrder = false; 
    while (!inOrder) { 
     inOrder = true; 
     for (int i = 1; i < a.size(); i++) { 
     **if(a.get(i - 1).compareTo(a.get(i)) > 0)** { 
//cannot find symbol: method compareTo(E); location: class Object 
//where E is a type-variable: E extends Object declared in class Sort     
     inOrder = false; 
      swap(a, i, i - 1); 
     } 
     } 
    } 
    } 

    public static void main(String args[]) //hadda lose 'static' for 'setLayout' to work 
    { 
    ArrayList<Integer> ary = new ArrayList<>(); 
    ary.add(2); ary.add(4); ary.add(7); ary.add(3); 
    **bubbleSort(ary)**; 
//method bubbleSort in class Sort<E> cannot be applied to given types; 
//required: ArrayList<E> 
//found: ArrayList<Integer> 
//reason: actual argument ArrayList<Integer> cannot be converted to ArrayList<E> 
//by method invocation conversion where E is a type-variable: 
//E extends Object declared in class Sort 
    for (int i = 0; i < ary.size(); i++) { 
     System.out.println(ary.get(i)); 
    } 
    } 

    @Override 
    public int compareTo(E o) { 
    **return 0;** // fixing errors above may help this fall into place 
    } 
} 

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

Answer 1

Это:

public abstract class Sort<E> implements Comparable<E> { 

означает, что E произвольный тип объекта, и, что экземпляры Sort<E> можно сравнить с экземплярами E. (Таким образом, ваше сообщение об ошибке жалуются, что E.compareTo не существует, так как Object не имеет такой метод.) То, что вы хотите, это:

public abstract class Sort<E extends Comparable<E>> { 

, что означает, что E должен быть тип, экземпляры которого могут быть по сравнению друг с другом.

---

Edited добавить: Собственно, как SLaks вместе указывают, что нет никаких реальных оснований для Sort быть общим; вам просто нужен метод bubbleSort. Кроме того, как предполагает MadProgrammer, либо Sort должен быть не abstract (так что вы можете его создать непосредственно), либо bubbleSort должен быть static (поэтому его можно вызывать без создания экземпляра Sort) или обоих. Например:

public class Sort { 
    private static <E> void swap(ArrayList<E> a, int i, int j) { 
     ... 
    } 

    private static <E extends Comparable<E>> void bubbleSort(ArrayList<E> a) { 
     ... 
    } 

    ... 
} 

еще лучше, Sort может быть интерфейс с методом sort и BubbleSort.sort(...) это просто реализация этого (а не давать Sort конкретный bubbleSort метод).

Answer 2

После взятия советов SLaks' и становится гораздо более знакомы с обобщениями (из общего стека и классов очередей вчера), сегодня я использовал схему ruakh в (но пришлось изменить private к public в строке „BubbleSort“), что позволило осуществить главно меняющуюся main к чему-то вменяемому (который теперь сводится к одному делать-то, что-полезную линию Sort.bubbleSort(ary);), и она работала, но у меня есть два горения вопросов:

(1) Что именно делает первый <E> средний/у/предполагающих в эта линия:

private static <E> void swap(ArrayList<E> a, int i, int j) { 

(2) Точно так же ... что с <E extends Comparable<E>> здесь:

private static <E extends Comparable<E>> void bubbleSort(ArrayList<E> a) { 

Чтобы ответить на мой собственный вопрос, "? Теперь, почему я не думаю, что из тех, кто" ...«Почему WOOD Я думаю о них ??"

EDIT: «параметризованные» или «общие» методы являются законными, как параметризованные/общие типы, и почему бы и нет?

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

EDIT: Одно слово: опыт

Answer 3

Я хотел бы просто сделать замечание, если я могу.

Изучение BubbleSort - прекрасный способ узнать, как использовать структуры данных в Java. Я согласен с остальными, что в реальном мире вы никогда не будете использовать BubbleSort, потому что он предлагает худшую производительность любого алгоритма сортировки, за исключением «StoogeSort».

Тем не менее, есть смысл пройти упражнение в качестве нового ученика, если он учит, как делать важные вещи, такие как использование и применение типового параметра типа, работа с операторами потока управления (например, для циклов) и даже делать обработку исключений. Не слушайте скептиков. Основным преимуществом Bubblesort является то, что алгоритм прост.

На мой взгляд, еще более простой алгоритм сортировки - это «Отложенная замена», также известная как «Сортировка выбора». Отложенный запрос на замещение имеет такую ​​же сложную сложность, как BubbleSort (O (n^2)), но в отличие от BubbleSort, сортировка сортировки по-прежнему используется в определенных приложениях. Он включен как субалгоритм в некоторых оптимизированных алгоритмах сортировки, и поскольку он минимизирует количество свопов, необходимых для заказа коллекции, выбор Сортировка по-прежнему используется, когда стоимость выполнения свопа высокая.

псевдокод для отложенной замены Sort следует и, на мой взгляд, даже проще, чем BubbleSort:

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 

запаздывающего Замена Сортировка может быть столько, сколько 50% быстрее, чем BubbleSort, но до сих пор не должно быть используется для сортировки очень больших коллекций.