Программирование на языке С - Сортировка посредством выбора

Written on .

ОГЛАВЛЕНИЕ

Страница 76 из 85
 

2.2.3. Сортировка посредством выбора

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

Например: 

            B=<20,10,8,-5,7>, B'=<>
            B=<20,10,8,7>,    B'=<-5>
            B=<20,10,8>,      B'=<-5,7>
            B=<20,10>,        B'=<-5,7,8>
            B=<20>,           B'=<-5,7,8,10>
            B=<>,            B'=<-5,7,8,10,20> .

Функция select упорядочивает массив s сортировкой посредством выбора. 

      /*    сортировка  методом  выбора          */
      double *select( double *s, int m, int n)
      {
        int i,j;
        double c;
        for (i=m; is[j])
             {  c=s[i];
                s[i]=s[j];
                s[j]=c;
             }
        return(s);
      }

Здесь, как и в предыдущем примере оба списка В и В' размещаются в разных частях массива s. При сортировке посредством выбора требуется Q=(n-m)*(n-m) действий и не требуется дополнительной памяти.

Сортировка квадратичной выборкой. Исходный список В из N элементов делится на М подсписков В1,В2,...,Вm, где М равно квадратному корню из N, и в каждом В1 находится минимальный элемент G1. Наименьший элемент всего списка В определяется как минимальный элемент Gj в списке , и выбранный элемент Gj заменяется новым наименьшим из списка Bj. Количество действий, требуемое для сортировки квадратичной выборкой, несколько меньше, чем в предыдущих методах Q= N*N, но требуется дополнительная память для хранения списка G.

форум c++