Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Алгоритмы сортировок на JavaScript

Алгоритмы сортировок на JavaScript


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


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


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


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


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


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;
}



Сортировка расчёской на JavaScript


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


function newGap(gap)        // Вспомогательная функция.
{ gap /= 1.3;
if (gap == 9 || gap == 10) gap = 11;
if (gap < 1) return 1;
return gap;
}

function CombSort(A) // Функция сортировки расчёской.
{ var n = A.length, gap = n;
do { swapped = false;
gap = newGap(gap);
for (var i=0; i<n-gap; ++i)
{ if (A[ i ] > A[i+gap])
{ swapped = true;
var t = A[i+gap]; A[i+gap] = A[ i ]; A[ i ] = t;
}
}
} while (gap > 1 || swapped);
return A;
}



Сортировка слиянием на JavaScript



function Merge(a,low,mid,high)    //Вспомогательная функция.
{
var b = new Array(high+1-low), h, i, j = mid+1, k, h = low, i = 0;
while (h <= mid && j <= high )
{ if (a[h] <= a[j]){ b[ i ]=a[h]; h++; }
else { b[ i ]=a[j]; j++; }
i++;
}
if (h > mid){ for (k = j; k <= high; k++){ b[ i ]=a[k]; i++; } }
else { for (k = h; k <= mid; k++){ b[ i ]=a[k]; i++; } }
for (k=0; k<=high-low; k++) a[k+low]=b[k];
return a;
}

function MergeSort(A) //Функция сортировки слиянияем.
{
function merge_sort(a,low,high)
{ if (low < high)
{ var mid = Math.floor((low+high)/2);
merge_sort(a, low, mid);
merge_sort(a, mid+1, high);
Merge(a, low, mid, high);
}
}
var n = A.length;
merge_sort(A, 0, n-1);
return A;
}



Пирамидальная сортировка на JavaScript



function HeapSort(A) 
{
if (A.length == 0) return [];
var n = A.length, i = Math.floor(n/2), j, k, t;
while (true)
{ if (i > 0) t = A[--i];
else { n--;
if (n == 0) return A;
t = A[n]; A[n] = A[0];
}
j = i; k = j*2+1;
while (k < n)
{ if (k+1 < n && A[k+1] > A[k]) k++;
if (A[k] > t)
{ A[j] = A[k]; j = k; k = j*2+1; }
else break;
}
A[j] = t;
}
}



Быстрая сортировка на JavaScript



function QuickSort(A)
{
if (A.length == 0) return [];
var a = [], b = [], p = A[0];
for (var i = 1; i < A.length; i++)
{ if (A[ i ] < p) a[a.length] = A[ i ];
else b[b.length] = A[ i ];
}
return QuickSort(a).concat( p,QuickSort(b) );
}



Сортировка перемешиванием на JavaScript


Сортировка перемешиванием (шейкерная сортировка, англ. Cocktail sort) — разновидность пузырьковой сортировки.


function CocktailSort(A)    //Также называют ShakerSort.
{
var i = 0, j = A.length-1, s = true, t;
while (i < j && s)
{ s = false;
for (var k = i; k < j; k++)
{ if (A[k] > A[k+1]){ t = A[k]; A[k] = A[k+1]; A[k+1] = t; s = true; } }
j--;
if (s)
{ s = false;
for (var k = j; k > i; k--)
{ if (A[k] < A[k-1]){ t = A[k]; A[k] = A[k-1]; A[k-1] = t; s = true; } }
}
i++;
}
return A;
}



Гномья сортировка на JavaScript


Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком.


function GnomeSort(A)
{
var n = A.length, i = 1, j = 2;
while (i < n)
{ if (A[i-1] < A[ i ]){ i = j; j++; }
else
{ var t = A[i-1]; A[i-1] = A[ i ]; A[ i ] = t;
i--;
if (i == 0){ i = j; j++; }
}
}
return A;
}



Естественная сортировка строк на JavaScript


Естественная сортировка (англ. Natural sort) — простая и эффективная модификация сортировки слиянием, которая учитывает, что данные (или их часть) могут быть уже отсортированы. Суть её в том, что нужно образовывать цепочки, и производить их слияние не в заранее определённом и фиксированном порядке, а анализировать имеющиеся в массиве данные.


function NaturalSort(string_array)  // string_array - это массив со строками (!), не числами.
{
var splitters = string_array.map(makeSplitter),
sorted = splitters.sort(compareSplitters);
return sorted.map(function(splitter){ return splitter.item });
function makeSplitter(item){ return new Splitter(item) }
function Splitter(item)
{ var index = 0, from = 0, parts = [], completed = false;
this.item = item; var key = item; this.key = key;
this.count = function(){ return parts.length; };
this.part = function(i){ while (parts.length <= i && !completed) next();
return i < parts.length ? parts[ i ] : null;
};
function next()
{ if (index < key.length)
{ while (++index)
{ var currentIsDigit = isDigit(key.charAt(index - 1)),
nextChar = key.charAt(index),
currentIsLast = index === key.length,
isBorder = currentIsLast || xor(currentIsDigit, isDigit(nextChar));
if (isBorder)
{ var partStr = key.slice(from, index);
parts.push(new Part(partStr, currentIsDigit));
from = index;
break;
}
}
}
else completed = true;
}
function Part(text, isNumber)
{ this.isNumber = isNumber; this.value = isNumber ? Number(text) : text; }
}
function compareSplitters(sp1, sp2)
{ var i = 0;
do { var first = sp1.part(i), second = sp2.part(i);
if (null !== first && null !== second)
{ if (xor(first.isNumber, second.isNumber))
{ return first.isNumber ? -1 : 1; }
else { var comp = compare(first.value, second.value);
if (comp != 0) return comp;
}
} else return compare(sp1.count(), sp2.count());
} while(++i);
function compare(a, b){ return a < b ? -1 : a > b ? 1 : 0; }
}
function xor(a, b){ return a ? !b : b; }
function isDigit(chr)
{ var code = charCode(chr);
return code >= charCode("0") && code <= charCode("9");
function charCode(c){ return c.charCodeAt(0); }
}
}

Источник: http://habrahabr.ru/post/127943/


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved