Может ли алгоритм сортировки выбором выйти из цикла раньше, чем это может сделать пузырьковая сортировка?

Эта программа будет работать нормально, если я не включу флаг досрочного завершения, но для полной сортировки списка требуется только 10 проходов сортировки, а не все 12. Однако, когда включен флаг завершения, сортировка завершается слишком рано. Следуя логике, я вижу, что это происходит потому, что после третьего прохода массив упорядочивается так: введите здесь описание изображения

с индексом i, который в настоящее время равен 7, нет меньших значений для его замены, поэтому флаг не получает назначенного ему значения 1, и цикл завершается. Итак, я думаю, мой вопрос в том, можно ли выйти из алгоритма сортировки выбором раньше и при этом полностью завершить сортировку?

#include<stdio.h>
int main()
{
     int list[13]= {23,8,4,7,22,18,39,42,5,88,16,11,3};
     int temp,min,flag;
     printf( "Before Sorting\n" );
     printf( "23 8 4 7 22 18 39 42 5 88 16 11 3\n" );

for( int i=0; i<12; i++ )
    {
        flag = 0;
        min = i;

        for( int j=i+1; j<13; j++ )
            {
                if( list[j]<list[min] )
                    {
                        flag = 1;
                        min = j  ;
                    }
            }

        if( !flag )
            break;

        temp = list[i];
        list[i]=list[min];
        list[min]=temp;

        printf( "\nAfter Pass %d.\n",i+1 );
        for( int i=0; i<13; i++ )
            printf( "%d ",list[i] );

        printf( "\n" );
    }

return 0;
}

c selection-sort flags
person Nicholas Cousar    schedule 15.11.2018    source источник
comment
Вы не можете вырваться, как это. Здесь текущее значение 7 является самым нижним в списке, поэтому оно (должно) ничем не меняться, но это ничего не говорит об оставшемся файле (за исключением того, что все значения, как известно, равны ›= 7) .   -  person 500 - Internal Server Error    schedule 15.11.2018
comment
Вместо того, чтобы пытаться оптимизировать сортировку выбором, вы могли бы обратиться к более умным алгоритмам сортировки с лучшей временной сложностью.   -  person paddy    schedule 16.11.2018
comment
Единственное, что вы можете пропустить при сортировке выбором, это своп.   -  person Tim Randall    schedule 16.11.2018

Ответы (2)


arrow_upward
2
arrow_downward

Действительно можете. Вот такая реализация,

int selsort(int v[], int n){

  bool sorted = false; // v not known to be sorted
  int  i = 0;          // i smallest elements in place 

  while(!sorted){
    // find min v[i..n-1]
    // check if v[i..n-1] is sorted

    int  j   = i+1;
    int  min = i;    // position of minimum of v[i..j-1]
    sorted   = true; // v[i..j-1] sorted

    while(j<n){
      if(v[j]<v[min]) min = j;        // update min
      if(v[j]<v[j-1]) sorted = false; // update sorted
      j++;
    }

    if (!sorted){
      // place min v[i..n-1] in v[i]
      int aux = v[i];
      v[i]    = v[min];
      v[min]  = aux;      

      i++;
    }
  }

  return EXIT_SUCCESS;
}

Как обычно, в итерации i мы начинаем с v[0..i-1], отсортированных с i наименьшими элементами массива в правильном месте. Итак, мы хотим найти min v[i..n-1], чтобы поместить его в позицию i. В этом варианте, когда мы делаем это, мы также проверяем, отсортировано ли v[i..n-1]. Если он отсортирован, то больше нечего делать.

Ваша реализация

В вашей реализации способ проверки упорядоченного сегмента неверен.

if( list[j]<list[min] )
    {
        flag = 1;
        min = j  ;
    }

Ваш флаг останется на 0 до тех пор, пока вам не придется обновлять минимум во внутреннем цикле. Таким образом, любой сегмент с минимумом в первой позиции будет считаться отсортированным.

person Jorge Adriano    schedule 15.11.2018

arrow_upward
2
arrow_downward

В пузырьковой сортировке почти нет искупительных качеств, самое приятное в ней — это ее название. Дональд Кнут сказал, что

у пузырьковой сортировки, кажется, нет ничего, что можно было бы рекомендовать, кроме броского названия и того факта, что она приводит к некоторым интересным теоретическим проблемам.

И действительно, из Википедии о сортировке выбором:

Среди простых алгоритмов Θ(n²) среднего случая сортировка выбором почти всегда превосходит пузырьковую сортировку и сортировку гномов.

В сортировке выбором нет вариаций — время ее выполнения не зависит от упорядочивания. Еще один хороший простой алгоритм O(n²) с переменным временем выполнения см. в разделе сортировка вставками.

person Antti Haapala    schedule 15.11.2018