Алгоритмы сортировок

@mik-a-el · Регистрация: 10.04.2006

Студворк — интернет-сервис помощи студентам

Наиболее часто задаваемые вопросы по С++. Реализация распространенных алгоритмов, решения типовых задач.

Статьи и учебники C++

Оглавление:

0. Сортировка

Выбором
Пузырьком
Вставками
Шелла
Пирамидальная
Быстрая (Хоара)
Поразрядная
Подсчётом

Если вы новичок, и не понимаете, что такое template<class T> или не проходили этого, то есть два способа справиться с этой проблемой:
1. Загуглить "Шаблоны С++". Материал простой, разберетесь
2. Убрать эту надпись, а в прототипе букву T заменить типом вашего массива (int, double, etc.)

@mik-a-el · 04.03.2007, 11:48 **[ТС]**

Алгоритмы сортировки строк

1. Сортировка выбором

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

Реализация на С++

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template< class T >
void selectSort(T* arr, int size) 
{
    T tmp;
    for(int i = 0; i < size; ++i) // i - номер текущего шага
    { 
        int pos = i; 
        tmp = arr[i];
        for(int j = i + 1; j < size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] < tmp) 
           {
               pos = j; 
               tmp = arr[j]; 
           }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}

Реализация на Си

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void selectSort(int* arr, int size) 
{
    int tmp, i, j, pos;
    for(i = 0; i < size; ++i) // i - номер текущего шага
    { 
        pos = i; 
        tmp = arr[i];
        for(j = i + 1; j < size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] < tmp) 
            {
               pos = j; 
               tmp = arr[j]; 
            }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}

2. Сортировка пузырьком (обменом)

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

Реализация на С++

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template< class T >
void bubbleSort(T* arr, int size)
{
    T tmp;
 
    for(int i = 0; i < size - 1; ++i) // i - номер прохода
    {            
        for(int j = 0; j < size - 1; ++j) // внутренний цикл прохода
        {     
            if (arr[j + 1] < arr[j]) 
            {
                tmp = arr[j + 1]; 
                arr[j + 1] = arr[j]; 
                arr[j] = tmp;
            }
        }
    }
}

Реализация на Си

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubbleSort(int* arr, int size)
{
    int tmp, i, j;
 
    for(i = 0; i < size - 1; ++i) // i - номер прохода
    {            
        for(j = 0; j < size - 1; ++j) // внутренний цикл прохода
        {     
            if (arr[j + 1] < arr[j]) 
            {
                tmp = arr[j + 1]; 
                arr[j + 1] = arr[j]; 
                arr[j] = tmp;
            }
        }
    }
}

Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает слишком медленно. А потому - почти не применяется.

3. Сортировка вставками

Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.

Реализация на С++

C++
1
2
3
4
5
6
7
8
9
10
11
12
template< class T >
void insertSort(T* a, int size) 
{
    T tmp;
    for (int i = 1, j; i < size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
}

Реализация на Си

C
1
2
3
4
5
6
7
8
9
10
11
void insertSort(int* a, int size) 
{
    int i, j, tmp;
    for (i = 1; i < size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
}

Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как O(n^2), дополнительная память при этом не используется.

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

Алгоритм можно слегка улучшить. Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия. Можно объединить из в одно, поставив в начало массива специальный сторожевой элемент. Он должен быть заведомо меньше всех остальных элементов массива.

4. Сортировка Шелла

Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.

Реализация

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int increment(long inc[], long size) 
{
    int p1, p2, p3, s;
    p1 = p2 = p3 = 1;
    s = -1;
    do 
    {
        if (++s % 2) 
        {
            inc[s] = 8*p1 - 6*p2 + 1;
        } 
        else 
        {
            inc[s] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
    p1 *= 2;
    } 
    while(3*inc[s] < size);  
 
    return s > 0 ? --s : 0;
}
 
 
template< class T >
void shellSort(T a[], long size) 
{
    long inc, i, j, seq[40];
    int s;
 
    s = increment(seq, size); // вычисление последовательности приращений
    while (s >= 0)  // сортировка вставками с инкрементами inc[] 
    {
         inc = seq[s--];         
         for (i = inc; i < size; ++i) 
         {
             T temp = a[i];
             for (j = i; (j >= inc) && (temp < a[j-inc]); j -= inc) {
                a[j] = a[j - inc];
             }
             a[j] = temp;
         }
    }
}

Часто вместо вычисления последовательности во время каждого запуска процедуры, ее значения рассчитывают заранее и записывают в таблицу, которой пользуются, выбирая начальное приращение по тому же правилу: начинаем с inc[s-1], если 3*inc[s] > size.

5. Пирамидальная сортировка

Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).

Реализация

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
template< class T >
void downHeap(T a[], long k, long n) 
{
    //  процедура просеивания следующего элемента 
    //  До процедуры: a[k+1]...a[n]  - пирамида 
    //  После:  a[k]...a[n]  - пирамида 
    T new_elem;
    long child;
    new_elem = a[k];
    
    while(k <= n/2) // пока у a[k] есть дети 
    {       
        child = 2*k;
        
        if( child < n && a[child] < a[child+1] ) //  выбираем большего сына 
            child++;
        if( new_elem >= a[child] ) 
            break; 
        // иначе 
        a[k] = a[child];    // переносим сына наверх 
        k = child;
    }
    a[k] = new_elem;
}
 
template< class T >
void heapSort(T a[], long size) 
{
    long i;
    T temp;
 
  // строим пирамиду 
    for(i = size / 2 - 1; i >= 0; --i) 
        downHeap(a, i, size-1);
  
  // теперь a[0]...a[size-1] пирамида 
 
    for(i=size-1; i > 0; --i) 
    {
        // меняем первый с последним 
        temp = a[i]; 
        a[i] = a[0]; 
        a[0] = temp;
        // восстанавливаем пирамидальность a[0]...a[i-1] 
        downHeap(a, 0, i-1); 
    }
}

Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды.

Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.

Метод не является устойчивым: по ходу работы массив так "перетряхивается", что исходный порядок элементов может измениться случайным образом.

6. Быстрая сортировка (сортировка Хоара)

"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Псевдокод

Code
1
2
3
4
5
6
7
8
quickSort ( массив a, верхняя граница N ) {
    Выбрать опорный элемент p - середину массива
    Разделить массив по этому элементу
    Если подмассив слева от p содержит более одного элемента,
    вызвать quickSort для него.
    Если подмассив справа от p содержит более одного элемента,
    вызвать quickSort для него.
}

Реализация

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
 
    long i = 0, j = N;      // поставить указатели на исходные места
    T temp, p;
 
    p = a[ N>>1 ];      // центральный элемент
 
    // процедура разделения
    do {
        while ( a[i] < p ) i++;
        while ( a[j] > p ) j--;
 
        if (i <= j) {
            temp = a[i]; a[i] = a[j]; a[j] = temp;
            i++; j--;
        }
    } while ( i<=j );
 
    // рекурсивные вызовы, если есть, что сортировать 
    if ( j > 0 ) quickSortR(a, j);
    if ( N > i ) quickSortR(a+i, N-i);
}

Каждое разделение требует, очевидно, O(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Итеративный алгоритм быстрой сортировки.

Псевдокод

Code
1
2
3
4
5
6
7
8
9
10
11
Итеративная QuickSort (массив a, размер size) {
    Положить в стек запрос на сортировку массива от 0 до size-1.
    do {
        Взять границы lb и ub текущего массива из стека.
        do {
            1. Произвести операцию разделения над текущим массивом a[lb..ub].
            2. Отправить границы большей из получившихся частей в стек.
            3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.
        } пока меньшая часть состоит из двух или более элементов
    } пока в стеке есть запросы
}

Реализация

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#define MAXSTACK 2048 // максимальный размер стека
template<class T>
void qSortI(T a[], long size) {
 
    long i, j; // указатели, участвующие в разделении
    long lb, ub; // границы сортируемого в цикле фрагмента
 
    long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
    // каждый запрос задается парой значений,
    // а именно: левой(lbstack) и правой(ubstack)
    // границами промежутка
    long stackpos = 1; // текущая позиция стека
    long ppos; // середина массива
    T pivot; // опорный элемент
    T temp;
 
    lbstack[1] = 0;
    ubstack[1] = size-1;
 
    do {
        // Взять границы lb и ub текущего массива из стека.
        lb = lbstack[ stackpos ];
        ub = ubstack[ stackpos ];
        stackpos--;
 
        do {
            // Шаг 1. Разделение по элементу pivot
            ppos = ( lb + ub ) >> 1;
            i = lb; j = ub; pivot = a[ppos];
            do {
                while ( a[i] < pivot ) i++;
                while ( pivot < a[j] ) j--;
                if ( i <= j ) {
                    temp = a[i]; a[i] = a[j]; a[j] = temp;
                    i++; j--;
                }
            } while ( i <= j );
 
            // Сейчас указатель i указывает на начало правого подмассива,
            // j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
            // Возможен случай, когда указатель i или j выходит за границу массива
 
            // Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub
            if ( i < ppos ) { // правая часть больше
                if ( i < ub ) { // если в ней больше 1 элемента - нужно
                    stackpos++; // сортировать, запрос в стек
                    lbstack[ stackpos ] = i;
                    ubstack[ stackpos ] = ub;
                }
            ub = j; // следующая итерация разделения
            // будет работать с левой частью
            } else { // левая часть больше
                if ( j > lb ) {
                    stackpos++;
                    lbstack[ stackpos ] = lb;
                    ubstack[ stackpos ] = j;
                }
                lb = i;
            }
        } while ( lb < ub ); // пока в меньшей части более 1 элемента
    } while ( stackpos != 0 ); // пока есть запросы в стеке
}

Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

7. Поразрядная сортировка

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

Реализация

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef struct slist_ { 
    long val;
    struct slist_ *next; 
} slist;
 
// функция сортировки возвращает указатель на начало отсортированного списка 
slist *radix_list(slist *l, int t) {
    //  t - разрядность (максимальная длина числа) 
    int i, j, d, m=1;
    slist *temp, *out, *head[10], *tail[10];
    out=l;
 
    for (j=1; j<=t; j++) { 
        for (i=0; i<=9; i++)
            head[i] = (tail[i]=NULL);
 
        while ( l != NULL ) {
            d = ((int)(l->val/m))%(int)10;
            temp = tail[d];
            if ( head[d]==NULL ) head[d] = l;
            else temp->next = l;
            temp = tail[d] = l;
            l = l->next;
            temp->next = NULL;
        }
        for (i=0; i<=9; i++)
            if ( head[i] != NULL ) break;
        l = head[i];
        temp = tail[i];
        for (d=i+1; d<=9; d++) {
            if ( head[d] != NULL) { 
                temp->next = head[d];
                temp = tail[d];
            }
        }
        m*=10;
    }
    return (out);
}

@odip · 22.07.2009, 00:40

Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

Для 32-битных машин достаточно взять MAXSTACK=32
Для 64-битных машин достаточно взять MAXSTACK=64

Совершенно незачем брать 2048

Maxim Prishchepa · 14.08.2013, 22:36

Сортировка подсчётом (предложил name?)

Алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза.

C++
1
2
3
4
5
6
7
8
9
10
11
void counting_sort (int *vec, int len, int min, int max) {
 
  int *cnt = new int[max-min+1];
 
  for(int i = min; i <= max; ++i) cnt[i - min] = 0;
  for(int i = 0; i < len; ++i) ++cnt[vec[i] - min];
 
  for(int i = min; i <= max; ++i)
    for(int j = cnt[i - min]; j--;)
      *vec++ = i;
}

@sourcerer · 09.12.2016, 16:09

Великолепная наглядная простая и понятная демонстрация разных видов сортировки (по наводке коллеги rikimaru2013):

Как упорядочить ну очень много книг по алфавиту?

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@mik-a-el Администратор 87915 / 53236 / 249 Регистрация: 10.04.2006 Сообщений: 13,770

	Алгоритмы сортировок 04.03.2007, 11:48. Показов 758000. Ответов 4 Метки нет (Все метки) Наиболее часто задаваемые вопросы по С++. Реализация распространенных алгоритмов, решения типовых задач. Статьи и учебники C++ Оглавление: 0. Сортировка Выбором Пузырьком Вставками Шелла Пирамидальная Быстрая (Хоара) Поразрядная Подсчётом Если вы новичок, и не понимаете, что такое template<class T> или не проходили этого, то есть два способа справиться с этой проблемой: 1. Загуглить "Шаблоны С++". Материал простой, разберетесь 2. Убрать эту надпись, а в прототипе букву T заменить типом вашего массива (int, double, etc.) 71

@sourcerer Модератор 5288 / 2376 / 342 Регистрация: 20.02.2013 Сообщений: 5,773 Записей в блоге: 20
	09.12.2016, 16:09
	Великолепная наглядная простая и понятная демонстрация разных видов сортировки (по наводке коллеги rikimaru2013): Как упорядочить ну очень много книг по алфавиту? 16