Запись элементов, сравниваемых в алгоритме сортировки в Java - PullRequest
Новая
       26

Запись элементов, сравниваемых в алгоритме сортировки в Java

1 голос
/ 10 февраля 2012

Привет! Я использую следующий алгоритм сортировки вставок и хочу записать сравниваемые элементы.В основном я хочу, чтобы сравнения были сохранены в двух списках массивов, arrList1 и arrList2.Если элемент находится на своем правильном месте, то оба списка массивов будут иметь один и тот же элемент.Если его нет, то arrList1 будет иметь выбранный элемент, а arrayList2 будет иметь элемент, с которым он сравнивает себя.В настоящее время я изо всех сил пытаюсь сделать это, поэтому мне было интересно, если кто-нибудь может помочь?Спасибо 

public static ArrayList<Integer> arrList1 = new ArrayList<Integer>();
public static ArrayList<Integer> arrList2 = new ArrayList<Integer>();
...
        public static void insertSort(int[] A){
      for(int i = 1; i < A.length; i++){
        int value = A[i];
        int j = i - 1;
        while(j >= 0 && A[j] > value){
          A[j + 1] = A[j];
          j = j - 1;
        }
        A[j + 1] = value;
      }
    }

РЕДАКТИРОВАТЬ: Например: если мой массив имел числа 1,3,2,4,6,5, то при сравнении, я хочу, чтобы мой список двух массивов выглядел: 

       arrList1    arrList2
#1        1           1
#2        3           3
#3        2           3 (As 2 goes before 3 then it must be compared to 3)
#4        4           4
#5        6           6
#6        5           6 (As 5 is lower then 6 then it must be compared to 6)

Сортированный массив: 1, 2, 3, 4, 5, 6

Как видите, arrList1 - это в основном порядок входного массива, тогда как arrList2 - это элемент, с которым он сравнивается, еслиэто не в правильном положении.Если он в правильном положении, arrList 2 будет иметь то же значение.

Ответы [ 2 ]

1 голос
/ 11 февраля 2012

Там у вас есть ... 

public class Test {
    public static List<Integer> arrList1;
    public static ArrayList<Integer> arrList2 = new ArrayList<Integer>();

    public static void main (String... args){
        Integer[] toSort = {1, 3, 2, 4, 6, 5};


        arrList1 = Arrays.asList(Arrays.copyOf(toSort, toSort.length));
        insertSort(toSort);

        List<Integer> sortedArray = new ArrayList<Integer>();
        for(int aux: toSort){
            sortedArray.add(aux);
        }

        System.out.println("Array list 1: " + arrList1);
        System.out.println("Array list 2: " + arrList2);
        System.out.println("Sorted array: " + sortedArray);
    }

    public static void insertSort(Integer[] A){
        arrList2.add(arrList1.get(0));
        for(int i = 1; i < A.length; i++){
            int value = A[i];
            int j = i - 1;
            if ((j >= 0 && A[j] > value)){
                arrList2.add(A[j]);
            }else{
                arrList2.add(A[i]);
            }
            while(j >= 0 && A[j] > value){
                A[j + 1] = A[j];
                j = j - 1;
            }

            A[j + 1] = value;
        }
    }
}

Вывод этого кода для меня:

Список массивов 1: [1, 3, 2, 4, 6, 5] Список массивов 2: [1, 3, 3, 4, 6, 6] Сортированный массив: [1, 2, 3, 4, 5, 6]

1 голос
/ 10 февраля 2012

РЕДАКТИРОВАТЬ: теперь, когда я понимаю, вопрос в том, что я предлагаю. Во-первых, обратите внимание, что сортировка вставки имеет сложность sqare (O (n ^ 2)), поэтому другие вычисления такой же сложности не изменят общую сложность алгоритма. Итак, вот что вы делаете - сначала вы вычисляете значения в arrList2, пересекая все значения слева от текущего элемента и ищите первое, большее, чем текущий элемент. Второй этап - это просто алгоритм сортировки - как вы уже указали, arrList1 содержит отсортированный A. Все это может быть реализовано с большей сложностью, но без использования сортировки вставкой. 

public static ArrayList<Integer> arrList1 = new ArrayList<Integer>();
public static ArrayList<Integer> arrList2 = new ArrayList<Integer>();
...
public static void insertSort(int[] A){
  for (int i = 0; i < A.length; ++i) {
    boolean found_greater = false;
    for (int j = i - 1; j >= 0; --j) {
      if (A[j] > A[i]) {
        found_greater = true;
        arrList2.add(A[j]);
        break;
      }
    }
    if (!found_greater) {
      arrList2.add(A[i]);
    }
  }

  for(int i = 1; i < A.length; i++){
    int value = A[i];
    int j = i - 1;
    while(j >= 0 && A[j] > value){
      A[j + 1] = A[j];
      j = j - 1;
    }

    arrList1.add(A[i]);
    A[j + 1] = value;
  }
}
...