Алгоритм быстрой сортировки javascript

Распространенные алгоритмы сортировки с примерами на JavaScript

Перевод статьи «Common Sorting Algorithms in JavaScript».

В этой статье я расскажу о нескольких распространенных алгоритмах сортировки. Изучить эти алгоритмы важно, потому что они часто позволяют снизить сложность задачи. Они также находят применение в алгоритмах поиска, при работе с базами данных и пр.

Мы рассмотрим следующие алгоритмы:

• Сортировка пузырьком
• Сортировка выбором
• Сортировка вставками
• Сортировка слиянием
• Быстрая сортировка
• Блочная сортировка

Примечание редакции Techrocks: объяснение алгоритмов сортировки с примерами на Python смотрите здесь.

Вспомогательные методы для перемены местами и сравнения

Мы часто будем менять местами элементы в массивах, поэтому давайте начнем с написания вспомогательного метода swap :

Также мы часто будем сравнивать элементы, поэтому, как мне кажется, будет не лишним написать отдельную функцию для этого:

const Compare = < LESS_THAN: -1, BIGGER_THAN: 1 >; function defaultCompare(a, b) < if (a === b) < return 0; >return a

Хорошо, с этим мы разобрались, можно переходить к сортировкам!

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

Временная сложность в наилучшем случае — O(N), в наихудшем — O(N^2).

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

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

function bubbleSort(arr, compare = defaultCompare) < const < length >= arr; for (let i = 0; i < length; i++) < for (let j = 0; j < length - 1 - i; j++) < // refer to note below if (compare(arr[j], arr[j + 1]) === Compare.BIGGER_THAN) < swap(arr, j, j + 1); >> > return arr; >

Учтите, что приведенное мною решение слегка улучшено по сравнению с обычным алгоритмом сортировки: мы вычитаем количество проходов из внутреннего цикла во избежание ненужных сравнений. Чтобы лучше понять, что на самом деле происходит, рассмотрите диаграмму с примером:

Сортировка выбором

Временная сложность в наилучшем и наихудшем случае — O(N^2).

В основе сортировки выбором лежит следующий подход: мы находим минимальное значение в структуре данных и помещаем его на первую позицию, затем находим второе минимальное значение и помещаем его на вторую позицию и так далее.

function selectionSort(arr, compare = defaultCompare) < const < length >= arr; let minIndex; for (let i = 0; i < length - 1; i++) < minIndex = i; for (let j = i; j < length; j++) < if (compare(arr[minIndex], arr[j]) === Compare.BIGGER_THAN) < minIndex = j; >> if (i !== minIndex) < swap(arr, i, minIndex); >> return arr; >

Следующая диаграмма показывает алгоритм сортировки выбором в действии:

Сортировка вставками

Временная сложность в наилучшем случае — O(N), в наихудшем — O(N^2).

Алгоритм сортировки вставками строит финальный отсортированный массив по одному значению за раз. Процесс выглядит следующим образом:

1. Предполагаем, что первый элемент уже отсортирован.
2. Сравниваем первый элемент со вторым: должно ли второе значение остаться на месте или же оно должно быть вставлено перед первым значением?
3. Далее аналогичное сравнение делается для третьего значения: должно ли оно быть вставлено на первую, вторую или третью позицию? И так далее.

function insertionSort(arr, compare = defaultCompare) < const < length >= arr; let temp; for (let i = 1; i < length; i++) < let j = i; temp = arr[i]; while (j >0 && compare(arr[j - 1], temp) === Compare.BIGGER_THAN) < arr[j] = arr[j - 1]; j--; >arr[j] = temp; > return arr; >

На диаграмме вы видите пример сортировки вставками в действии:

Если сортировать маленькие массивы, то у алгоритма сортировки вставками лучшая производительность, чем у алгоритмов сортировки выбором или пузырьком. Но я все равно не советовала бы его использовать для каких-либо целей помимо образовательных.

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

Временная сложность в наилучшем и наихудшем случае — O(N Log N).

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

Здесь реализация рекурсивная. Она состоит из двух функций: одна для деления массивов на более мелкие, а другая — для осуществления сортировки.

function mergeSort(arr, compare = defaultCompare) < if (arr.length >1) < const < length >= arr; const middle = Math.floor(length / 2); const left = mergeSort(arr.slice(0, middle), compare); const right = mergeSort(arr.slice(middle, length), compare); arr = merge(left, right, compare); > return arr; > function merge(left, right, compare) < let i = 0; let j = 0; const result = []; while (i < left.length && j < right.length) < result.push(compare(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]); >return result.concat(i

Вот диаграмма для визуализации процесса:

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

Временная сложность в наилучшем/среднем случае — O(N Log N), в наихудшем — O(N^2).

Быстрая сортировка это один из наиболее часто используемых алгоритмов сортировки. Подобно алгоритму сортировки слиянием, этот алгоритм также использует подход «разделяй и властвуй».

Быстрая сортировка немного сложнее, чем уже рассмотренные нами, поэтому, чтобы лучше разобраться, давайте рассмотрим процесс пошагово:

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

function quickSort(arr, compare = defaultCompare) < return quick(arr, 0, arr.length - 1, compare); >function quick(arr, left, right, compare) < let i; if (arr.length >1) < i = partition(arr, left, right, compare); if (left < i - 1) < quick(arr, left, i - 1, compare); >if (i < right) < quick(arr, i, right, compare); >> return arr; > function partition(arr, left, right, compare) < const pivot = arr[Math.floor((right, left) / 2)]; let i = left; let j = right; while (i while (compare(arr[j], pivot) === Compare.BIGGER_THAN) < j--; >if (i > return i; >

Блочная сортировка

Временная сложность в наилучшем/среднем случае — O(N + k), в наихудшем — O(N^2).

function bucketSort(arr, bucketSize) < if (arr.length < 2) < return arr; >// create buckets and distribute the elements const buckets = createBuckets(arr, bucketSize); // sort the buckets using insertion sort and add all bucket elements to sorted result return sortBuckets(buckets); > function createBuckets(arr, bucketSize) < // determine the bucket count let min = arr[0]; let max = arr[0]; for (let i = 1; i < arr.length; i++) < if (arr[i] < min) < min = arr[i]; >else if (arr[i] > max) < max = arr[i]; >> const bucketCount = Math.floor((max - min) / bucketSize) + 1; // initialize each bucket (a multidimensional array) const buckets = []; for (let i = 0; i < bucketCount; i++) < buckets[i] = []; >// distribute elements into buckets for (let i = 0; i < arr.length; i++) < const bucketIndex = Math.floor((arr[i] - min) / bucketSize); buckets[bucketIndex].push(arr[i]); >return buckets; > function sortBuckets(buckets) < const sortedArr = []; for (let i = 0; i < buckets.length; i++) < if (buckets[i] != null) < insertionSort(buckets[i]); // quick sort is another good option sortedArr.push(. buckets[i]); >> return sortedArr; >

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

Обратите внимание, что наилучшим образом алгоритм блочной сортировки работает тогда, когда элементы можно распределить по блокам поровну. Если элементы слишком разбросаны, лучше использовать побольше блоков (и наоборот).

Следующая диаграмма показывает алгоритм блочной сортировки в действии:

Заключение

Мы рассмотрели лишь некоторые из наиболее часто встречающихся алгоритмов сортировки. На самом деле таких алгоритмов гораздо больше.

Источник

Quick Sort Algorithm in JavaSript (pivot as the first element + pivot as the random element)

Quick Sort is one of the most famous and effective Sorting Algorithms. The comprehension of how it works will undoubtedly help you in your JavaScript learning. Also, questions on algorithms are popular in job interviews, so there is a big chance you will be asked to describe how Quick Sort works.

I’m sure that I convinced you that Quick Sort is important. Let’s start!

Basic knowledge for Quick Sort Implementation

At first, this lesson assumes that you know how to work with arrays, loops and know the array’s methods in JavaScript. If not, you can read about some information in the appropriate links. And after reading you can return to this article.

Array’s methods which are used for the Quick Sort Implementation:

Implementation

Firstly, we need to write a function quickSort which will sort our array.

Okay, let’s start to fill out the body of our function.

Quick Sort is an algorithm which implements recursively. And thus we need to add a base case for quickSort function.

This string means that if the length is less than 2 we just return an array. We write it because we don’t need to sort an empty array or array with a single element.
The next step is to write the main variables which we need for our algorithm. There are pivot, left and right.

• pivot — the element of the array (in our case is the first element) which is compared with other elements in the same array.
• left — is an array that stores elements of the passed array which are less than the pivot.
• right — the same as left, but stores elements greater or equal to the pivot.

Now we need to sort elements of the passed array in left and right arrays. This requires a for loop.

function quickSort(arr) < if (arr.length < 2) return arr; let pivot = arr[0]; const left = []; const right = []; for (let i = 1; i < arr.length; i++) < if (pivot >arr[i]) < left.push(arr[i]); >else < right.push(arr[i]); >> > 

Here we just check each element of the passed array and compare it with the pivot. When a for loop iterates through all elements our left array fills with elements less than the pivot and right — greater than the pivot. The method push here adds elements at the end of the left and right arrays.

Let’s look at the simple example with the following array:
[5, 2, 6, 1, 30, -10].

Pivot is the first element. It is 5. The algorithm compares each element after the pivot. It compares 5 and 2. 2 is less and 5 (2 < 5) and hence 2 is added to the left array. Then it compares 5 and 6. 6 is greater than 5 (6 >5) and the algorithm adds 6 to the right array. And it does the same with the other elements.

Final left and right arrays will look as follows:

Okay, let’s return to our code. In order to return the final sorted array, we need to write the return and the something which we want to return. In our case it is:

 return quickSort(left).concat(pivot, quickSort(right)); 

In order to fully understand the Quick Sort Algorithm let’s continue with our example of [5, 2, 6, 1, 30, -10].

After one iteration we got the following result:

In our example, there is only one array that doesn’t match this condition. It is left: [1, -10]. And now it will be iterated. Here is a result after the iteration:

return quickSort(left).concat(pivot, quickSort(right)); 

Let’s look at the recursive stack of the left array. After it, your comprehension of the Quick Sort Algorithm will be advanced!

Note: the sign «↓» here is just for explanation. It isn’t the part of JavaScript

And when the left array riches an array with a single element [-10] the quickSort function will return results of the call stack. It will simply insert each pivot between the left and right arrays (pivot is highlighted in bold and underlined).

The sample: left + pivot + right (“+” = merge in this example).

The Final code

The final code of the Quick Sort function:

function quickSort(arr) < if (arr.length < 2) return arr; let pivot = arr[0]; const left = []; const right = []; for (let i = 1; i < arr.length; i++) < if (pivot >arr[i]) < left.push(arr[i]); >else < right.push(arr[i]); >> return quickSort(left).concat(pivot, quickSort(right)); > 

Moreover, you can look at the .gif explanation from Wikipedia.

I don’t know about you, but it’s always been difficult for me to understand such graphical explanations of algorithms. And so I write this article with the hope that there will be people who are just like me.

And what about efficiency?

The average case for the Quick Sort Algorithm is O(n log n) where n is the length of an array. But the worst case is O(n²). You can look at the graph (X-axis is the number of elements in the array; Y-axis — operations or time)

In order to achieve the average case, we need to choose a random pivot each time. There are various implementations of Quick Sort with the random pivot but I usually do it so:

function quickSort(arr) < if (arr.length < 2) return arr; let min = 1; let max = arr.length - 1; let rand = Math.floor(min + Math.random() * (max + 1 - min)); let pivot = arr[rand]; const left = []; const right = []; arr.splice(arr.indexOf(pivot), 1); arr = [pivot].concat(arr); for (let i = 1; i < arr.length; i++) < if (pivot >arr[i]) < left.push(arr[i]); >else < right.push(arr[i]); >> return quickSort(left).concat(pivot, quickSort(right)); > 

Note: if you want the explanation of this code just writes about it in the comments below. If I see that people want to know it I will publish a new article “Quick Sort with Random Pivot” in a wink.

Conclusion

I’m sure that after reading this article you fully understood the Quick Sort Algorithm and you will be confident in your job interview.

Moreover, if you want to plunge into algorithms learning I highly recommend you to read the book Aditya Bhargava “Grokking Algorithms”(taken from https://github.com/KevinOfNeu). It contains a lot of simple explanations of all popular algorithms.

Maybe you have much simpler explanation of the Quick Sort Algorithm in JS. Write about it in the comments!

Also if you want to get notifications about my new articles you can follow me in Medium and my Twitter account:

My social networks

If you have questions or you interested in my articles, you can check and subscribe on my social media:

Источник