Лучший случай, Худший случай, Случайный ввод данных для алгоритма сортировки вставок? - PullRequest
Новая
       15

Лучший случай, Худший случай, Случайный ввод данных для алгоритма сортировки вставок?

1 голос
/ 08 ноября 2011

Это код, который я написал для первоначального ввода случайных чисел и последующей их сортировки методом сортировки вставок. 

        #include<iostream>

        #include <cstdlib>

        #include <ctime>

        using namespace std;

        int main(void)
        {

           int array[10];

           srand (time(0));

           for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )// inputting values into array[10]
           {
              array[i] = 1 + (rand()%100); //any random number between 1 - 100
           }
           cout <<" Before sorting " << " ---" <<endl;
           for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )// printing the values
           {
               cout  <<  array[i]<< endl;
           }


           int key ;
           int t;//for future purpose
           int compcount = 0;//to keep track of comparisons
           for (int j = 1; j<sizeof(array)/sizeof(array[0]);j++)
           {
               key = array[j];//assign to second element initially
               t = j-1;//assign to first element initially
               while (j > 0 && array[t]>key)
               {
                   array[t+1] = array[t];//moving array if bigger than next element
                   t = t-1;
                   compcount++;
               }
               array[t+1] = key;
           }
           cout << " After sorting" << " --- " <<endl;

           for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )
           {
               cout  <<  array[i]<< endl;
           }
           cout << "comparison count is " << compcount << endl;
           system ("pause");

           return 0;

        }

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

Теперь случайный ввод будет иметь смысл для этого.Когда я сделал другой код с «уже отсортированным» массивом чисел (наилучший сценарий), число ключевых сравнений было равно 0. Может ли кто-то пролить свет на то, является ли худший сценарий полной противоположностью этому?Если бы это было так, я попытался сделать это, но я получил только 32 сравнения с размером массива 32.

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

Ответы [ 2 ]

2 голосов
/ 08 ноября 2011

В вашей программе есть одна ошибка 

           while (j > 0 && array[t]>key)

должно быть 

           while (t >= 0 && array[t]>key)

Кроме этого, он работает для меня с обратным сортированным входом. Это действительно худший случай, и результат ясно показывает это.

Вы получили результат n-1, но это небольшая проблема. Для решения см. Ответ @ Mranz.

2 голосов
/ 08 ноября 2011

Вы проводите сравнение как часть условного оператора while, что означает, что вы рассчитываете только успешное сравнение, поэтому ваш лучший результат неверен. compcount ++ также должен находиться прямо над циклом while.

Edit: 

compCount++;
while (t >= 0 && array[t] > key)
{
    array[t+1] = array[t];//moving array if bigger than next element
    t = t-1;

    if (t >= 0) // This is a hack to ensure that 't >= 0' will pass
       compCount++; // and another comparison will happen
}
...