Является ли реализация сортировки вставкой наихудшим вариантом O (n)? - PullRequest
Новая
       6

Является ли реализация сортировки вставкой наихудшим вариантом O (n)?

0 голосов
/ 12 ноября 2018

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

void main()
{
//insertion sort runs from i = 1 to i = n, thus is worst case O(n)
for (

    int i = 1,
    placeholder = 0,
    A[] = { 10,9,8,7,6,5,4,3,2,1 },
    j = i;

    i <= 10;

    j-- > 0 && A[j - 1] > A[j]
    ? placeholder = A[j], A[j] = A[j - 1], A[j - 1] = placeholder
    : j = ++i
)

{
for (
    int x = 0;
    x < 10; x++
) 
    cout << A[x] << ' ';
    cout << endl;
}


system("pause");
}

Существует толькоздесь задействован один цикл for, и он работает от 1 до n.Мне кажется, что это будет определение O (n).Что именно мне здесь не хватает?

Ответы [ 2 ]

0 голосов
/ 12 ноября 2018

Данный код не является правильным кодом C ++ и даже не близок к псевдокоду.Правильный код должен быть таким: 

void main()
{
 int i,j,key;
 int A[]={10,9,8,7,6,5,4,3,2,1};
 //cout<<"Array before sorting:"<<endl;
 //for(i=0;i<10;i++)
 //cout<<A[i]<<"\t";
 //cout<<endl;
 for(i=1;i<10;i++)
 {
  key=A[i];
  for(j=i-1;j>=0 && A[j]>key;j--)
  {
   A[j+1]=A[j];
  }
  A[j+1]=key;
 }
 //cout<<"Array after sorting:"<<endl;
 //for(i=0;i<10;i++)
 //cout<<A[i]<<"\t";
 //cout<<endl;
}

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

0 голосов
/ 12 ноября 2018

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

...