Напишите конспект на тему: Алгоритмы и исполнители!

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

Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются следующие действия: проход по файлу с обменом местами соседних элементов, нарушающих заданный порядок, до тех пор, пока файл не будет окончательно отсортирован. Основное достоинство пузырьковой сортировки заключается в том, что его легко реализовать в виде программы. Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма:

O (n2) O (n2).

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

n-1 n-1 итерации массив не будет полностью отсортирован.

function BubbleSort (A) / / A - массив, который нужно

{ / / отсортировать по возрастанию.

var n = A. length;

for (var i = 0; i < n-1; i++)

{ for (var j = 0; j < n-1-i; j++)

{ if (A[j+1] < A[j])

{ var t = A[j+1]; A[j+1] = A[j]; A[j] = t; }

}

}

return A; / / На выходе сортированный по возрастанию массив A.

}

Сортировка выбором на jа vascript

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

n-1 n-1 элементов и обмениваем найденный наименьший элемент со вторым, т. е. помещаем второй наименьший элемент в окончательную позицию в отсортированном массиве. В общем случае, при i-ом проходе по списку (0⩽i⩽n-2) (0⩽i⩽n-2) алгоритм ищет наименьший элемент среди последних n-i n-i элементов и обменивает его с A[i] A[i]. После выполнения n-1 n-1 проходов список оказывается отсортирован.

function SelectionSort (A) / / A - массив, который нужно

{ / / отсортировать по возрастанию.

var n = A. length;

for (var i = 0; i < n-1; i++)

{ var min = i;

for (var j = i+1; j < n; j++)

{ if (A[j] < A[min]) min = j; }

var t = A[min]; A[min] = A[ i ]; A[ i ] = t;

}

return A; / / На выходе сортированный по возрастанию массив A.

}

Сортировка вставками на jа vascript

На каждом шаге алгоритма сортировки встаками выбирается один из элементов входного массива и вставляется на нужную позицию в уже отсортированном массиве, до тех пор, пока входных элементы не будут исчерпана. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. В приведённой ниже реализации на jа vascript алгоритма сортировки встаками используется именно эта стратегия выбора.

function InsertionSort (A) / / A - массив, который нужно

{ / / отсортировать по возрастанию.

var n = A. length;

for (var i = 0; i < n; i++)

{ var v = A[ i ], j = i-1;

while (j > = 0 && A[j] > v)

{ A[j+1] = A[j]; j--; }

A[j+1] = v;

}

return A; / / На выходе сортированный по возрастанию массив A.

}

Сортировка Шелла на jа vascript

function ShellSort (A)

{

var n = A. length, i = Math. floor (n/2) ;

while (i > 0)

{ for (var j = 0; j < n; j++)

{ var k = j, t = A[j];

while (k > = i && A[k-i] > t)

{ A[k] = A[k-i]; k - = i; }

A[k] = t;

}

i = (i==2) ? 1 : Math. floor (i*5/11) ;

}

return A;

}

Сортировка подсчётом на jа vascript

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

function SimpleCountingSort (A)

{

var n = A. length, Count = [], B = [];

for (var i = 0; i < n; i++) Count[ i ] = 0;

for (var i = 0; i < n-1; i++)

{ for (var j = i+1; j < n; j++)

{ if (A[ i ] < A[j]) Count[j]++;

else Count[ i ]++;

}

}

for (var i = 0; i < n; i++) B[Count[ i ]] = A[ i ];

return B;

}