Stl алгоритмы представляют набор готовых функций, которые могут быть применены к stl коллекциям и могут быть подразделены на три основных группы


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

Loading...


бет5/5
Дата01.03.2021
өлшемі308 Kb.
1   2   3   4   5

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

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

void selection_sort(int *v, int n)

  • void selection_sort(int *v, int n)
  • {
  • for (int i = 0; i < n - 1; i++)
  • {
  • int best = i;
  • for (int j = i + 1; j < v.size(); j++) {
  • if (v[j] < v[best]) {
  • best = j; }
  • }
  • if (best != i) {
  • int temp = v[i];
  • v[i] = v[best];
  • v[best] = temp;
  • }
  • }
  • С++

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

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

Общая схема :

  • Быстрая сортировка
  • Общая схема :
  • из массива выбирается некоторый опорный элемент a[i],
  • запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,
  • теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого,
  • для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.
  • В конце получится полностью отсортированная последовательность.

Рассмотрим работу процедуру разделения для массива a[0]...a[6] и опорного элемента p = a[3].

  • Быстрая сортировка
  • Рассмотрим работу процедуру разделения для массива a[0]...a[6] и опорного элемента p = a[3].

Быстрая сортировка с помощью STL функции SORT

  • Быстрая сортировка
  • Быстрая сортировка с помощью STL функции SORT
  • int A[ ] = {1, 4, 2, 8, 5, 7};
  • const int N = sizeof(A) / sizeof(int);
  • sort(A, A + N);
  • copy(A, A + N, ostream_iterator(cout, " "));
  • // The output is " 1 2 4 5 7 8".
  • С++

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

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

Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1], a[9]), ... , (a[7], a[15]).

  • Сортировка Шелла
  • Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1], a[9]), ... , (a[7], a[15]).
  • 2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]).

3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).

  • Сортирока Шелла
  • 3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).
  • 4. В конце сортируем вставками все 16 элементов.


Достарыңызбен бөлісу:
1   2   3   4   5
Loading...




©melimde.com 2020
әкімшілігінің қараңыз

    Басты бет
Сабақтың тақырыбы
Сабақтың мақсаты
Сабақ тақырыбы
рсетілетін қызмет
Жалпы ережелер
бойынша жиынтық
ғылым министрлігі
қызмет стандарты
жиынтық бағалау
бекіту туралы
Әдістемелік кешені
туралы хабарландыру
Сабақ жоспары
тоқсан бойынша
бағалауға арналған
Қазақстан республикасы
жиынтық бағалаудың
тоқсанға арналған
Жұмыс бағдарламасы
республикасы білім
Қазақстан республикасының
білім беретін
біліктілік талаптары
арналған жиынтық
әкімінің аппараты
жиынтық бағалауға
туралы анықтама
мамандығына арналған
бағалау тапсырмалары
қойылатын жалпы
Конкурс туралы
жалпы біліктілік
мемлекеттік әкімшілік
арналған әдістемелік
Қазақстан тарихы
арналған тапсырмалар
мерзімді жоспар
жалпы конкурс
бағалаудың тапсырмалары
Мектепке дейінгі
қатысушыларға қойылатын
Қазақ әдебиеті
пәнінен тоқсанға
әдістемелік кешені
Қазақстан облысы
ортақ біліктілік
қызмет регламенті
ткізу туралы
оқыту әдістемесі
мамандығы бойынша
конкурс қатысушыларына

Loading...