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

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

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

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

с индексом 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;
}

Ответы [ 2 ]

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

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

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 до тех пор, пока вам не придется обновлять минимум во внутреннем цикле. Таким образом, любой сегмент с минимумом в первой позиции будет считаться отсортированным.

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

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

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

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

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

Вариантов сортировки не существует - время выполнения не зависит от порядка.Для другого хорошего простого алгоритма O (n²), который имеет переменное время выполнения, см. сортировка вставки .

...