Как считать сравнения в сортировках выбором и вставкой?

Я пишу 2 разных вида, один из которых - выбор, другой - вставка. Ниже приведен мой метод сортировки вставками.

public static void  iSort(String[] array)
{
  int i, j, k;
  String temp; 
  for(i = 1; i<array.length; i++)
  {
   k=i;
   for(j = k-1; j>=0 && array[j].compareTo(array[k])>0; j--)
   {
    ccounter++;
     temp = array[j];
     array[j] = array[k];
     array[k] = temp;
     k--;
   }
   }
 }

где ccounter — статическая переменная класса. Когда я проверяю это, используя массив строк из 1000 элементов, я получаю значение 239507. Однако, когда я тестирую правильно упорядоченный массив строк, я получаю нулевое значение, которое, как я знаю, неверно, поскольку в лучшем случае производительность n сравнений для n терминов. Интересно, мой метод написан неправильно, или счетчик поставлен неправильно


java selection-sort insertion-sort
person rubikscube09    schedule 30.09.2014    source источник
comment
вы считаете свопы, а не сравнения. (т.е. вы не учитываете сравнения, которые приводят к <=0)   -  person njzk2    schedule 30.09.2014
comment
Во внутреннем цикле for переместите сравнение внутрь цикла for. В настоящее время вы считаете только тогда, когда вам нужно поменять местами. Если сравнение выполняется внутри цикла, вы подсчитаете все сделанные сравнения.   -  person arunmoezhi    schedule 30.09.2014
comment
@arunmoezhi Под этим вы имеете в виду взять условие из скобок цикла и поместить их в фактическое тело цикла?   -  person rubikscube09    schedule 30.09.2014
comment
Да. Поместите его в тело цикла после приращения счетчика.   -  person arunmoezhi    schedule 30.09.2014
comment
@ njzk2 Да, я только что это понял, спасибо, что обратил на это мое внимание. То, что вы говорите, имеет полный смысл, не могу поверить, что я это пропустил.   -  person rubikscube09    schedule 30.09.2014
comment
@arunmoezhi Большое спасибо, что помогли. Однако, когда я делаю лучший случай (все по порядку), он должен дать мне n сравнений, верно? Это не дает мне этого, и я начинаю думать, что неправильно написал сортировку   -  person rubikscube09    schedule 30.09.2014
comment
В лучшем случае ваш внутренний цикл должен выполняться один раз для каждой итерации внешнего цикла. Вы выходите из внутреннего цикла, если обнаружите, что новый элемент уже находится в отсортированном порядке?   -  person arunmoezhi    schedule 01.10.2014
comment
@arunmoezhi Я сделал несколько исправлений, и все заработало! Большое спасибо. Хотел бы я представить тебя   -  person rubikscube09    schedule 01.10.2014

Ответы (2)


arrow_upward
1
arrow_downward

Проблема в том, что если вы выходите из цикла, потому что compareTo() вернуло false, вы не учитываете это окончательное сравнение.

Если бы я писал это, я бы обернул код сравнения в функцию, которая вызывала бы compareTo() и увеличивала счетчик. Затем я бы использовал исключительно эту функцию-оболочку для выполнения всех сравнений. Таким образом, нет никаких шансов ошибиться в счете.

person NPE    schedule 30.09.2014

arrow_upward
0
arrow_downward

увеличивайте счетчик для каждого выполнения внутреннего цикла и выполняйте сравнение после увеличения счетчика

public static void  iSort(String[] array)
{
  int i, j, k,ccounter=0;
  String temp; 
  for(i = 1; i<array.length; i++)
  {
        k=i;
        for(j = k-1; j>=0; j--)
        {
                 ccounter++; //increment counter for every execution of inner loop
                 //better to do integer comparison than string comparison
                 if(Integer.parseInt(array[j]) <= Integer.parseInt(array[k]))
                 {
                     break;
                 }
                 temp = array[j];
                 array[j] = array[k];
                 array[k] = temp;
                 k--;
        }
   }
}
person arunmoezhi    schedule 30.09.2014