При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка и для ее решения существуют различные методы. Рассмотрим некоторые из них.

Пузырьковая сортировка

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=< K'1, K'2,...,K'n >, в котором для любого 1<=i<=n элемент K'(i) <= K'(i+1).

При обменной сортировке упорядоченный список В' получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.

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

Пример:

                 B=,   исходный список;

                 B1=<-5,10,8,7,20>,  первый просмотр;

                 B2=<-5,8,7,10,20>,  второй просмотр;

                 B3=<-5,7,8,10,20>,  третий просмотр.

В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса n до индекса m) в порядке возрастания элементов.

Нижеприведенная функция bubble сортирует входной массив методом пузырьковой сортировки.

     /*   сортировка   пузырьковым   методом           */

     float * bubble(float * a, int m, int n)

     {

     char is=1;

     int i;

     float c;

       while(is)

       {   is=0;

           for (i=m+1; i<=n; i++)

           if ( a[i] < a[i-1] )

           {    c=a[i];

                a[i]=a[i-1];

                a[i-1]=c;

                is=1;

           }

       }

       return(a);

     }

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

 Сортировка вставкой

Упорядоченный массив B' получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B' так, что B' остается упорядоченным списком длины i.

Например, для начального списка B=< 20,-5,10,8,7 > имеем:

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

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

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

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

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

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

Функция insert реализует сортировку вставкой.

      /*    сортировка  методом   вставки              */

      float *insert(float *s, int m, int n)

      {

      int i,j,k;

      float aux;

      for (i=m+1; i<=n; i++)

           { aux=s[i];

             for (k=m; k<=i && s[k]=k; j--)  s[j+1]=s[j];

             s[k]=aux;

           }

           return(a);

      }

Здесь оба списка В и В' размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B' - часть s c индексами от m до i-1 (см. рис.26).

При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.

Рис.26. Схема движения индексов при сортировке вставкой.

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

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

Например:

            B=, B'=< >

            B=,    B'=<-5>

            B=,      B'=<-5,7>

            B=,        B'=<-5,7,8>

            B=,           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; i<=n;j++)

            if(s[i]>s[j])

             {  c=s[i];

                s[i]=s[j];

                s[j]=c;

             }

        return(s);

      }

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

Рис.27. Схема движения индексов при сортировке выбором.

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

Оглавление.