Сортировка вставками на 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); > 
>
>

Источник

Insertion Sort in JavaScript

In this article, we will explain what the idea behind Insertion Sort is and implement it in JavaScript.

Insertion Sort is one of the simpler sorting algorithms. It’s highly intuitive, stable, in-place, and of comparison-type.

A stable sorting algorithm is an algorithm in which two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

In other words, if a sorting algorithm is stable, equivalent elements retain their relative positions after the sorting algorithm is done.

An in-place algorithm is an algorithm that uses no additional memory or data structures, rewriting the original memory locations of the elements in the input array or list.

Finally, a comparison algorithm is the one that, during its execution, only reads list elements through a single abstract comparison operation. Depending on your data type and goal, the comparison can be done via a relational operator or through a custom comparison function.

Despite it having a very large time complexity for a sorting algorithm, Insertion Sort can be very useful, sometimes even being able to outperform some of the most efficient sorting algorithms, such as Quicksort or Merge Sort, on small collections.

It’s rarely used as a standalone algorithm — you’d typically use a fast sorting algorithm like Quicksort and finish up the last «loose ends» with Insertion Sort since it’s highly efficient for that task.

Insertion Sort

The idea behind Insertion Sort is often compared to the way people sort a hand of cards while playing Rummy.

In this card game, the dealer deals out cards to each player. Then, the players take the cards given to them one by one, sorting them in their hand in ascending order by inserting each card in its place.

During this entire process, the players hold one sorted pile of cards in their hands, while the unsorted pile from which they draw new cards is in front of them.

A very useful property of Insertion Sort is the fact that it doesn’t need to know the entire array in advance in order for it to be sorted — it just inserts the given elements one by one.

This really comes in handy when we want to add more elements in an already sorted array, because Insertion Sort will add the new elements in their proper places without resorting the entire collection.

Here’s a visual representation of how Insertion Sort works:

Insertion Sort Implementation

Now that we understand the idea behind Insertion Sort, we can move on to the implementation:

function insertionSort(inputArr) < let n = inputArr.length; for (let i = 1; i < n; i++) < // Choosing the first element in our unsorted subarray let current = inputArr[i]; // The last element of our sorted subarray let j = i-1; while ((j > -1) && (current < inputArr[j])) < inputArr[j+1] = inputArr[j]; j--; > inputArr[j+1] = current; > return inputArr; > 

The iteration starts at the second element. We consider the first element sorted by default. For each iteration, we keep track of the current element. Each current element will be the first element of the unsorted array — and each element before it will belong to the sorted array.

Through a while loop, we go through the sorted array and shift elements to the right, opening up a space for the current element to be inserted.

Once we find the proper place for it, the current element is inserted into the newly-opened slot. This process is repeated for each iteration until the array is sorted.

Now, let’s populate an array and call our sorting algorithm:

let inputArr = [5, 2, 4, 6, 1, 3]; insertionSort(inputArr); console.log(inputArr); 

The output of this array will be:

Free eBook: Git Essentials

Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!

Let’s go over this example step-by step:

First Iteration:

Sorted array: 5
Unsorted array: 2, 4, 6, 1, 3

Second Iteration:

Sorted array: 2, 5
Unsorted array: 4, 6, 1, 3

Third Iteration:

Sorted array: 2, 4, 5
Unsorted array: 6, 1, 3

This is repeated until we’re greeted with a sorted array: 1, 2, 3, 4, 5, 6 .

We can notice an invariant in each of these iterations. For the k-th iteration of our loop, the interval of [0,k] is guaranteed to be sorted.

Time Comparison

The best running time of Insertion Sort is linear, and we get it if our input array is already sorted. This means that Insertion Sort works wonders when it comes to checking whether or not the array is sorted.

However, the worst and average time complexity is O(n 2 ), which is pretty bad for a sorting algorithm, especially when it is applied to arrays or lists of a bigger size. In this case, Quicksort or Merge Sort with a complexity of O(nlogn) would be a much better choice.

On the other hand, being one of the fastest quadratic sorting algorithms, Insertion Sort usually outperforms Bubble Sort, Gnome Sort and Selection Sort. In addition to that, when our input array size is very small (10-20 elements), Insertion Sort can even outperform Quicksort and Merge Sort.

This is why JavaScript, despite using Quicksort (in Chrome) or Merge Sort (in Mozilla) as the primary sorting algorithm, also uses Insertion Sort on small collections — and after Quicksort/Merge Sort has done the bulk of the work.

Conclusion

Insertion Sort is a simple, stable, in-place, comparison sorting algorithm.

Despite being pretty time-consuming with quadratic complexity, it is very useful when the input array is small in size. In this case, it even outperforms the most commonly used divide-and-conquer algorithms, which is why JavaScript uses a combination of Insertion Sort and Merge Sort or Quicksort when using built-in sorting functions.

When it comes to larger-sized arrays, it outperforms most other quadratic sorting algorithms, including Bubble Sort, Gnome Sort, as well as Selection Sort.

Источник