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

Implementing a Selection Sort Algorithm in JavaScript

Welcome to another entry in my Sorting Algorithms in JS series here on Dev! I’ve previously covered Insertion Sort in last week’s post, so check that out if you’re interested.

Intro

In computer science, few tools are used quite as often as sorting algorithms. We rely on them every day as programmers and engineers to sift through data, and they’re built into nearly every modern programming language in one way or another. While using a language’s built-in sorting functions may get the job done for most day-to-day work, it’s important to understand what’s going on under the hood, and what different sorting algorithms are actually doing and why they work the way they do. While it may not come up often, there’s always the chance you may be asked to implement or explain a sorting algorithm in a technical interview setting, which is exactly what this post is here to prepare you for! Today, we’ll be looking at Selection Sort, another one of the fundamental sorting algorithms in Computer Science.

What is Selection Sort?

Selection sort is an in-place comparison sorting algorithm.
.
The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

This might be a bit confusing without a visualization, so here’s an animation to help put it all into perspective (I recommend watching it a few times to get a grasp on what’s happening): As we traverse through the array in an initial loop, we push forward through the array with a second pointer in a nested loop at the same time, comparing each value to the starting value (beginning with our first loop’s initial index.) If we find a lower value, we set that new value as our new lowest value to be compared against, and continue pushing. By doing this, we ensure that each time we traverse through the array we will always find the next lowest value. When we reach the end of our second loop, we swap the lowest value with our very first initial index’s value, and proceed to the next step. This could also be done in reverse order, by searching for the largest values, if we were interested in sorting from highest to lowest. It’s your choice!

How efficient is it?

Selection Sort, while relatively simple to comprehend and implement, unfortunately lags behind other sorting algorithms like Quick Sort, Heap Sort, and Merge Sort for larger data sets. However, since Selection Sort functions in-place and requires no auxiliary memory, it does have a space advantage over some other more complicated algorithms. Generally speaking, Insertion Sort is likely to be a more performant alternative, although Selection Sort is still important to know and understand as a programmer and computer scientist. Selection Sort has a best case, worst case, and average case runtime complexity of O(n^2), meaning it will always be quadratic in nature.

How do we implement it?

Here’s where the fun starts! Since we’re implementing Insertion Sort in JavaScript, we’ll be making use of modern ES6+ syntax to handle swapping elements in the array, which will help keep the number of lines of code that we need to write down. Here’s what the final algorithm will look like:

function selectionSort(array)  for (let i = 0; i  array.length - 1; i++)  let minIndex = i; for (let j = i + 1; j  array.length; j++)  if (array[j]  array[minIndex])  minIndex = j; > > [array[i], array[minIndex]] = [array[minIndex], array[i]]; > return array; > 

Let’s break this down step by step. First off, let’s declare our function, its return value (the sorted array), and the initial loop in which we’ll be doing all of our logic:

function selectionSort(array)  for (let i = 0; i  array.length - 1; i++)  > return array; > 

You might be wondering why we’re telling our loop to stop at array.length — 1 rather than the normal array.length . This is because in the next loop, we’ll start by comparing i against its neighbor i + 1 in the array. This means we’ll need to stop our initial loop one index short of the full array length. Next we’ll declare the variable that will hold the index of our current smallest element, minIndex , and the second loop that will do our comparison work:

function selectionSort(array)  for (let i = 0; i  array.length - 1; i++)  let minIndex = i; for (let j = i + 1; j  array.length; j++)  > > return array; > 

As you can see, this loop starts at i + 1 , assigning that value to the pointer j . The minIndex variable is only set to i as a temporary measure, since it will likely be changed within this loop. However, there is the chance that i will in fact be the next smallest value in the unsorted section of the array and will simply stay where it is. Last but not least, we’ll add in the core comparison logic within our nested loop, as well as the ES6 swap that exchanges the two values once the loop completes:

function selectionSort(array)  for (let i = 0; i  array.length - 1; i++)  let minIndex = i; for (let j = i + 1; j  array.length; j++)  if (array[j]  array[minIndex])  minIndex = j; > > [array[i], array[minIndex]] = [array[minIndex], array[i]]; > return array; > 

As we went over back at the top of this tutorial, the core of Selection Sort is the idea of selecting the next lowest value and keeping track of it until we hit the end of the array, then swapping it with the right boundary of the sorted section of the array (our initial i index.) We do this here by evaluating if array[j] If you’ve come this far, thanks so much for reading! I hope this was a helpful tutorial to anyone learning about sorting algorithms, JavaScript, or programming fundamentals in general. I’ll continue working through more sorting algorithms in future posts, so stay tuned!

Источник

Распространенные алгоритмы сортировки с примерами на 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; >

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

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

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

Заключение

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

Источник