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...