Сортировки внутренние и внешние, показатели эффективности

Основными показателями сортировка являются:

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

Память –характеризует количество памяти, выделяемой сверх сортируемых данных.

Устойчивость отвечает за то, что сортировка не меняет взаимного расположения равных элементов.

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

По скорости работы сортировки делят на обычные и совершенные у совершенных в формуле скорости находится lg(N) где N количество элементов.

По сферам применения сортировки делят на два вида:

внутренние сортировки работают с данным в оперативной памяти с произвольным доступом;

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

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

2. объем данных не позволяет им разместиться в ОЗУ

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

ПУЗЫРЕК расположим массив сверху вниз, от нулевого элемента - к последнему. Идея метода: шаг сортировки состоит в проходе снизу-вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию…

Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.

#include "stdafx.h"

#include <iostream>

#include <math.h>

#include <ctime>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "Russian");

int n;

cout << "Введите размер массива" << endl;

cin >> n;

cout << "Сортировка пузырьком " << n << " элеметнов \n";

srand(time(0));

int arr[50];

for (int idx = 0; idx<n; ++idx)

{

arr[idx] = rand()%100;

cout << arr[idx] << " ";

}

cout << endl;

//cout << sizeof(arr)/sizeof(*arr);

int temp, numSortIndex;

numSortIndex = 0;

while (numSortIndex < n)

{

for (int idx = n - 1; idx > numSortIndex; --idx)

{

if (arr[idx] < arr[idx-1])

{

temp = arr[idx];

arr[idx] = arr[idx-1];

arr[idx-1] = temp;

}

}

++numSortIndex;

}

cout << "\n";

for (int idx = 0; idx<n; ++idx)

{

cout << arr[idx] << " ";

}

cout << endl;

// float intermediatResult;

// cout.precision(20);

system("pause");

return 0;

}

ВЫБОРА

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

Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1).

Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:

n + (n-1) + (n-2) + (n-3) +... + 1 = 1/2 * (n2+n) = Theta(n2).

#include "stdafx.h"

#include <iostream>

#include <math.h>

#include <ctime>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "Russian");

int n;

cout << "Введите размер массива" << endl;

cin >> n;

cout << "Сортировка выбора " << n << " элеметнов \n";

srand(time(0));

int arr[50];

for (int idx = 0; idx<n; ++idx)

{

arr[idx] = rand()%100;

cout << arr[idx] << " ";

}

cout << endl;

//cout << sizeof(arr)/sizeof(*arr);

int min = arr[0];

int minIndex = 0;

for (int idx = 0; idx < n; ++idx)

{

min = arr[idx];

minIndex = idx;

for (int jdx = idx; jdx < n; ++jdx)

{

if (min > arr[jdx])

{

min = arr[jdx];

minIndex = jdx;

}

}

arr[minIndex] = arr[idx];

arr[idx] = min;

}

cout << "\n";

for (int idx = 0; idx<n; ++idx)

{

cout << arr[idx] << " ";

}

cout << endl;

// float intermediatResult;

// cout.precision(20);

system("pause");

return 0;

}

Date: 2015-08-15; view: 783; Нарушение авторских прав