Есть ли случаи, когда этот конкретный алгоритм сортировки не будет работать? - PullRequest
Новая
       51

Есть ли случаи, когда этот конкретный алгоритм сортировки не будет работать?

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

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

#include<stdio.h>
void insertion(int size, int[*]);
int main()
{
  int size;
  printf("Size of Array: ");
  scanf("%d",&size);
  int ary[size];
  for(int i=0; i<size; i++)
  scanf("%d",&ary[i]);
  insertion(size, ary);
  return 0;
}
 void insertion(int size, int A[size])
 {
   int value;
   int hole;
   int flag;

   for(int i=1; i<size; i++)
     {
       value = A[i];//the value of the current index of the unsorted list 
                    //gets stored in variable named value
       flag = 0;
           for(int j=i-1; j>=0; j--)
              {
                 if(A[j]>value)
                    {
                       flag = 1;
                       hole = j; //index position where value will be 
                                 //inserted into
                       A[j+1] = A[j];
                    }
              }
          if(flag) //ensures that insertion occurs only when one of the 
                   //sorted elements is less than value
     A[hole] = value;
    }

  for(int i=0; i<size; i++)
  printf("%d ",A[i]);
}

`

Этот следующий метод является альтернативным вариантом, в котором вместо флага используется цикл while: 

void unshuffle( int size, int* A )
{
int value;
int position;

for( int i=1; i<size; i++ )
    {
    value = A[i];
    position = i;

    while( A[position-1]>value && position>0 )
        {
        A[position] = A[position-1];
        position--;
        }
    A[position] = value;
    }

}

Является ли это предпочтительным методом написания вставки сортировки с точки зрения эффективности?

1 Ответ

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

Ваш подход становится менее эффективным; рассмотрим следующий вариант вашего алгоритма: 

for(int j=i-1; j>=0; j--)
{
    if(A[j] > value)
    {
        A[j+1] = A[j];
    }
    else
    {
        A[j+1] = value; // worst that could happen: self asignment;
                        // still less costly than another `if`!

        break;          // you're in the sorted part of the array, so all other
                        // values are smaller or equal as well -> can exit!
    }
}

Теперь вам больше не нужен флажок / отверстие, но, что более важно, вам больше не нужно перебирать уже отсортированную меньшую часть.

То же самое, что вы достигли бы с двойным условием в цикле while, с которого вы начали ...

На самом деле, есть ошибка, если текущий элемент меньше всех уже отсортированных, предложение else никогда не вводится, поэтому элемент не будет вставлен в первую позицию. Исправить это легко, хотя: 

int j;
for(j = i-1; j >= 0; j--)
{
    if(A[j] > value)
    {
        A[j+1] = A[j];
    }
    else
    {
        break;
    }
}
A[j+1] = value; // (still self-assignment possible)
                // if j got -1: insert at 0, so fine

Теперь мы стали еще ближе к оригинальному циклу while ...

Тем не менее, вы пытаетесь оптимизировать алгоритм, который хорошо известен своей неэффективностью (среднее (!) Время выполнения O(n²)), я не считаю, что стоит так сильно заботиться о таком, лучше переключиться на быстрая сортировка с самого начала (O(n log(n)) среднее время выполнения), сортировка кучи (с максимальным O(n log(n)) временем выполнения, но худшими константами, чем быстрая сортировка) или intro-sort (гибрид первых двух, стандартный алгоритм сортировки C ++ std::sort в большинстве реализаций).

...