Не следует обвинять спящего в том, что он на всё закрывает глаза (В. Ломаный).

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

2 мин для чтения
FavoriteLoadingДобавить в избранное
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...
7 ноября 2018
Алгоритм сортировки выборки в javascript

Сортировка выбора – это алгоритм сортировки со сложностью со временем O(n2). Он работает очень медленно на больших наборах данных.

Как работает сортировка выборки?

Сортировка выбора начинается с выбора минимального элемента и сравнивает его с несортированным массивом.

Образец :

1.) [ 4,3,5,2 ]

  • Сортировка выбирает 4 в качестве минимального элемента и начинает сравнивать его с оставшейся частью массива, если какой-либо элемент меньше 4, то нам нужно его поменять.

2.) [ 2,3,5,4 ].

  • После замены он выбирает 3 в качестве минимального элемента и начинает сравнивать с оставшейся частью массива нет элемента, который меньше, чем 3, поэтому мы переходим к следующему элементу, который является 5.
  • Теперь 5 является минимальным элементом, но мы находим элемент 4, который меньше, чем 5, поэтому мы меняем его.

Массив с окончательной сортировкой [2,3,4,5 ]

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

function selectionSort(arr){
  return arr
}

 

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

function selectionSort(arr) {
    for (var i = 0; i < arr.length; i++) {
        let min = i; //  хранение индекса минимального элемента
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j; // обновление индекса минимального элемента
            }
        }
    }
    return arr
}

 

Последний шаг нам нужно поменять местами.

function selectionSort(arr) {
    for (var i = 0; i < arr.length; i++) {
        let min = i; //  хранение индекса минимального элемента
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[ j ]) {
                min = j; // обновление индекса минимального элемента
            }
        }
        if (i !== min) {
            let temp = arr[ i ];
            arr[ i ] = arr[min];
            arr[min] = temp;
        }
    }
    return arr
}

 

Можно даже использовать разрушение массива для замены элементов.

function selectionSort(arr) {
    for (var i = 0; i < arr.length; i++) {
        let min = i; //  хранение индекса минимального элемента
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j; // обновление индекса минимального элемента
            }
        }
        if (i !== min) {
            [arr[ i ],arr[min]]= [arr[min],arr[ i ]];
        }
    }
    return arr
}

 

Вторая реализация с использованием метода map

function selectionSort(arr, length = arr.length) {
    arr.map((e, i) => {
        let min = i; //  хранение индекса минимального элемента
        for (let j = i + 1; j < length; j++) {
            if (arr[min] > arr[j]) {
                min = j; // обновление индекса минимального элемента
            }
        }
        if (i !== min) {
            [arr[ i ],arr[min]]= [arr[min],arr[ i ]]; // замена
        }
    })
    return arr
}

console.log(selectionSort([3,1,5,0,-4,44,9,20]));
//[-4,0,1,3,5,9,20,44]

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Просмотров: 13

Если статья понравилась, то поделитесь ей в социальных сетях:

Добавить комментарий

Войти с помощью: 

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам:

Заполните форму и наш менеджер перезвонит Вам в самое ближайшее время!

badge
Обратный звонок 1
Отправить
galka

Спасибо! Ваша заявка принята

close
galka

Спасибо! Ваша заявка принята

close