Сортировка пузырьком javascript массива

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

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

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

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

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

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  < 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 < if (a[h]  
else < b[ i ]=a[j]; j++; > 
i++; 
> 
if (h > mid) < for (k = j; k > 
else < for (k = h; k > 
for (k=0; 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 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 function charCode(c)< return c.charCodeAt(0); > 
>
>

Источник

Bubble Sort In JavaScript

Bubble Sort is one of the most widely discussed algorithms, simply because of its lack of efficiency for sorting arrays. If an array is already sorted, Bubble Sort will only pass through the array once (using concept two below), however the worst case scenario is a run time of O(N²), which is extremely inefficient. Even former President Barack Obama recognizes the inefficiency of Bubble Sort. When we chart the growth-rate of O(N²), we see that, compared to other sorting algorithms like Merge Sort, which is O(N Log N), it grows at a much quicker scale. Given the atrocity that is Bubble Sort, it’s still important to understand the algorithm and decipher why it’s so poor. Let’s delve into two concepts for coding Bubble Sort.

Concept 1

• Iterate through the array and check each element against the next element in the array.
• If the current element is larger than the next element, swap them.
• If it’s not greater, move the pointers up and compare the next two elements.
• Once we reach the end of the array, we know that the largest element is in the last position.
• Repeat this process N times where N is the length of the array, and each time, iterate up to the last-sorted element.

Visualizing Concept 1

Let’s take a look at how this would be run on an array of length 6.

Concept 1 Code

We need to have two pointers (two nested loops) for concept one. Each time we iterate through, the upper bound decreases by one, as we know that this index contains a sorted value.

function bubbleSortConcept1(arr)  for (let j = arr.length - 1; j > 0; j--)  for (let i = 0; i  j; i++)  if (arr[i] > arr[i + 1])  let temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; > > > > 

Concept 2

• Iterate through the array and check each element against the next element in the array.
• If the current element is greater than the next item, swap them.
• Indicate that a swap has taken place.
• If a swap occurred, loop through the array again.
• We know that the array is sorted when no swaps have occurred.

Concept 2 Code

We only need one pointer with this method, as we’re using a variable to store a Boolean, indicating whether or not a swap occurred. In contrast to concept one, this concept requires us to iterate through each item in the array each time we pass through it.

function bubbleSortConcept2(arr)  let swapped; do  swapped = false; console.log(arr); arr.forEach((item, index) =>  if (item > arr[index + 1])  // Save the value to a variable so we don't lose it let temp = item; arr[index] = arr[index + 1]; arr[index + 1] = temp; swapped = true; > >) > while (swapped); > 

Run Time

Bubble Sort is one of the most inefficient sorting algorithms coming in at O(N²). In the worst case scenario, we will have to compare each element against every other element in the array, hence O(N²).

Источник