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

07.11.2018

Время чтения: 2 мин.

Сортировка выбора — это алгоритм сортировки со сложностью со временем 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.

Просмотров поста: 22

Редактор: AndreyEx

Рейтинг: 5 (1 голос)

Поделиться в соц. сетях: