Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются следующие действия: проход по файлу с обменом местами соседних элементов, нарушающих заданный порядок, до тех пор, пока файл не будет окончательно отсортирован. Основное достоинство пузырьковой сортировки заключается в том, что его легко реализовать в виде программы. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма:
O(n2)O(n2).
Суть алгоритма пузырьковой сортировки состоит в сравнении соседних элементов и их обмене, если они находятся не в надлежащем порядке. Неоднократно выполняя это действие, мы заставляем наибольший элемент "всплывать" к концу массива. Следующий проход приведет к всплыванию второго наибольшего элемента, и так до тех пор, пока после
n−1n−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. }
Сортировка выбором на JavaScript
Сортировка выбором начинается с поиска наименьшего элемента в списке и обмена его с первым элементом (таким образом, наименьший элемент помещается в окончательную позицию в отсортированном массиве). Затем мы сканируем массив, начиная со второго элемента, в поисках наименьшего среди оставшихся
n−1n−1элементов и обмениваем найденный наименьший элемент со вторым, т.е. помещаем второй наименьший элемент в окончательную позицию в отсортированном массиве. В общем случае, при i-ом проходе по списку (0⩽i⩽n−2)(0⩽i⩽n−2) алгоритм ищет наименьший элемент среди последних n−in−i элементов и обменивает его с A[i]A[i]. После выполнения n−1n−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. }
Сортировка вставками на JavaScript
На каждом шаге алгоритма сортировки встаками выбирается один из элементов входного массива и вставляется на нужную позицию в уже отсортированном массиве, до тех пор, пока входных элементы не будут исчерпана. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. В приведённой ниже реализации на JavaScript алгоритма сортировки встаками используется именно эта стратегия выбора.
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. }
Сортировка Шелла на JavaScript
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; }
Сортировка подсчётом на JavaScript
Вначале для каждого элемента массива подсчитывается количество элементов, меньших, чем он, и на основе этой информации текущий элемент помещается в соответствующее место отсортированного массива. Ниже приведёна простая реализация алгоритм сортировки массива методом подсчета на JavaScript.
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; }
Answers & Comments
Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются следующие действия: проход по файлу с обменом местами соседних элементов, нарушающих заданный порядок, до тех пор, пока файл не будет окончательно отсортирован. Основное достоинство пузырьковой сортировки заключается в том, что его легко реализовать в виде программы. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма:
O(n2)O(n2).Суть алгоритма пузырьковой сортировки состоит в сравнении соседних элементов и их обмене, если они находятся не в надлежащем порядке. Неоднократно выполняя это действие, мы заставляем наибольший элемент "всплывать" к концу массива. Следующий проход приведет к всплыванию второго наибольшего элемента, и так до тех пор, пока после
n−1n−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.
}
Сортировка выбором на JavaScript
Сортировка выбором начинается с поиска наименьшего элемента в списке и обмена его с первым элементом (таким образом, наименьший элемент помещается в окончательную позицию в отсортированном массиве). Затем мы сканируем массив, начиная со второго элемента, в поисках наименьшего среди оставшихся
n−1n−1элементов и обмениваем найденный наименьший элемент со вторым, т.е. помещаем второй наименьший элемент в окончательную позицию в отсортированном массиве. В общем случае, при i-ом проходе по списку (0⩽i⩽n−2)(0⩽i⩽n−2) алгоритм ищет наименьший элемент среди последних n−in−i элементов и обменивает его с A[i]A[i]. После выполнения n−1n−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.
}
Сортировка вставками на JavaScript
На каждом шаге алгоритма сортировки встаками выбирается один из элементов входного массива и вставляется на нужную позицию в уже отсортированном массиве, до тех пор, пока входных элементы не будут исчерпана. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. В приведённой ниже реализации на JavaScript алгоритма сортировки встаками используется именно эта стратегия выбора.
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.
}
Сортировка Шелла на JavaScript
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;
}
Сортировка подсчётом на JavaScript
Вначале для каждого элемента массива подсчитывается количество элементов, меньших, чем он, и на основе этой информации текущий элемент помещается в соответствующее место отсортированного массива. Ниже приведёна простая реализация алгоритм сортировки массива методом подсчета на JavaScript.
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;
}