How to randomly sort an array? | LeetCode task | JavaScript

Поділитися
Вставка
  • Опубліковано 18 гру 2024

КОМЕНТАРІ • 117

  • @igormuryy5722
    @igormuryy5722 3 роки тому +6

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

    • @frontendscience
      @frontendscience  3 роки тому +1

      Спасибо за поддержку! Очень вдохновляет. Как раз снимаю новое видео. 😀

  • @stravoytov
    @stravoytov Рік тому

    Отличное видео, спасибо большое за разъяснения. Много статей перечитал, но так и не понял логики. А тут всё логично объяснено.

  • @dmitrykorovin4356
    @dmitrykorovin4356 3 роки тому +2

    спасибо за ваши видео, не канал, а находка!

    • @frontendscience
      @frontendscience  3 роки тому

      И Вам спасибо за слова поддержки! Рад стараться)

  • @WebInterview
    @WebInterview 3 роки тому +5

    Можно еще чуть сократить - использовать деструктурирующее присваивание, вроде [arr[i], arr[rnd]] = [arr[rnd], arr[i]];
    Спасибо за контент :)

    • @frontendscience
      @frontendscience  3 роки тому +5

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

  • @ВиталийЗамирайло-щ9к

    Приятно, когда в начале видео написал своё решение, и этот вариант в последствии советует автор.
    Кстати, дополнительная переменная tmp не обязательна, можно просто
    [ arr[ rnd ], arr[ i ] ] = [ arr[i], arr[ rnd ] ];

    • @frontendscience
      @frontendscience  3 роки тому +3

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

  • @DenProgMan
    @DenProgMan 3 роки тому

    Решил пройтись с начала и брать весь диапазон, а не только оставшийся от текущей позиции, т.е. мой алгоритм меняет местами по всему массиву, вроде понятно объяснил :-D
    function shuffle(array) {
    for (let index = 0; index < array.length; index++) {
    const element = array[index];
    const randomIndex = Math.floor(Math.random() * array.length);
    array[index] = array[randomIndex];
    array[randomIndex] = element;
    }
    return array;
    }

    • @DenProgMan
      @DenProgMan 3 роки тому

      Math.floor, кстати, можно заменить на двойную тильду:
      Math.floor(Math.random() * array.length);
      ~~(Math.random() * array.length);

    • @ЕгорЧилиевич-ю9р
      @ЕгорЧилиевич-ю9р 3 роки тому

      такое перемешивание выдает не равномерно распределенные перестановки

  • @elenakhilalova
    @elenakhilalova Рік тому

    видео очень полезное , спасибо что так подробно разобрали задачу ❤

  • @EvilYou
    @EvilYou 3 роки тому +1

    Задачу из видео решил быстро, так как уже встречал такую раньше, но зайдя на leetcode, увидел дополнительные условия, там она немного усложнена прототипами. Мое решение с использованием синтаксиса классов:
    class Solution {
    constructor(nums) {
    this.nums = nums;
    }

    reset() { // возвращает первоначальный массив
    return this.nums;
    }

    shuffle() { // сортирует (задача из видео)
    let arr = this.nums.concat();
    for (let i = arr.length - 1; i > 0; i--) {
    let random = Math.floor((i + 1) * Math.random());
    [arr[i], arr[random]] = [arr[random], arr[i]]; // (*)
    }
    return arr;
    }
    }
    * - использовал деструктурирующее присваивание для более короткой записи, а также потому, что не нужна дополнительная переменная для хранения промежуточного значения.
    Результат на leetcode: Runtime: 224 ms, faster than 91.86%

    • @frontendscience
      @frontendscience  3 роки тому

      Отлично вышло! Благодарю за решение

  • @PEDRO-rs6ei
    @PEDRO-rs6ei Рік тому +1

    function shuffle(array) {
    for (let i = 0; i < array.length; i++) {
    let rand = Math.floor(Math.random() * array.length)
    let tmp = array[array.length - i - 1]
    array[array.length - i - 1] = array[rand]
    array[rand] = tmp
    }
    return array
    }

  • @alexbigar9769
    @alexbigar9769 3 роки тому +2

    Топ материал🔥

  • @vovaseagull1097
    @vovaseagull1097 3 роки тому

    Спасибо большое за видео!)
    Я решил пойти через рекурсию и понервничал)
    вот решение:
    const arr1 = [1, 2, 4, 76, 55, 33]
    const shuffle = (array) => {
    const newArray = [];
    const addNewNumToArray = (num) => {
    if (newArray.length === array.length) {
    return newArray
    }
    if (newArray.includes(num)) {
    return addNewNumToArray(array[Math.floor(Math.random() * array.length)])
    }
    newArray.push(num)
    return addNewNumToArray(array[Math.floor(Math.random() * array.length)])
    }
    return addNewNumToArray(array[Math.floor(Math.random() * array.length)]);
    }
    console.log('shuffle exec', shuffle(arr1))

    • @frontendscience
      @frontendscience  3 роки тому

      Сурово! :) тоже занервничал

  • @DmitriiKhoroshilov
    @DmitriiKhoroshilov 7 днів тому

    Подскажите, значение arr.length откуда берётся, оно же не указано?

  • @ПетроПередерий-р1у
    @ПетроПередерий-р1у 2 роки тому +2

    Я обычно делаю так. В цикле беру 2 случайных элемента и меняю их местами (а не как у автора перебор массива от конца к началу). В чём разница? А в том что я задаю количество итераций в цикле как захочу. Если мне нужно перемешать как у автора то достаточно сделать количество итераций в цикле равным половине длины массива. Но если мне нужно перемешать массив только ЧУТЬ-ЧУТЬ то я задаю меньшее число итераций чем половина длины массива. Можно задать число итераций и больше чем половина длины массива для "более крутого" перемешивания. Но это не имеет практического смысла.

  • @SergeiZahharenko
    @SergeiZahharenko 2 роки тому

    Развлёкся :)
    const shuffle = (arr) => {
    const result = []
    while(arr.length > 0) {
    const rand = Math.random() * arr.length
    result.push( arr.splice(rand,1)[0] )
    }
    return result
    }

  • @s.i.9988
    @s.i.9988 3 роки тому +1

    Отлично! :)

  • @EvilYou
    @EvilYou Рік тому

    Кстати, кто хочет проверить правильность своей функции, это можно сделать так:
    function shuffle(arr) { // ваша функция shuffle (здесь привел свою)
    for (let i = arr.length - 1; i > 0; i--) {
    let random = Math.floor( Math.random() * (i + 1) );
    [arr[random], arr[i]] = [arr[i], arr[random]];
    }
    }
    let arr = [1, 2, 3];
    let obj = {
    123: 0,
    132: 0,
    213: 0,
    231: 0,
    312: 0,
    321: 0,
    };
    for (let i = 0; i < 1e5; i++) {
    shuffle(arr);
    obj[arr.join('')]++;
    }
    console.log(obj); // у меня все значения вышли от 16471 до 16768
    распределение должно быть плюс минус одинаковым.

  • @lostsouls3151
    @lostsouls3151 3 роки тому +1

    Вот что получилось, тоже это прям простой вариант
    const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
    function shuffle(arr) {
    for (var i = 0; i < 10; i++) {
    arr.sort(() => 0.5 - Math.random());
    console.log(arr);
    }
    }
    shuffle(numbers);

    • @frontendscience
      @frontendscience  3 роки тому

      Благодарю за решение!

    • @Shtirlic_Isaev
      @Shtirlic_Isaev 3 роки тому

      Интуитивно, мне ваше решение кажется более простым и понятным. Правда, так как это сортировка, то сложность этого лаконичного алгоритма будет уже O(N*log(N))

    • @frontendscience
      @frontendscience  3 роки тому

      @@Shtirlic_Isaev Да помимо большей сложности есть еще момент с неравномерным распределением (скажем так не достаточно равномерной рандомности).

    • @Shtirlic_Isaev
      @Shtirlic_Isaev 3 роки тому

      @@frontendscience Да, позже прочитал об этом в другой ветке комментариев... И этот эффект значительно интереснее, требует гораздо более глубокого понимания !

  • @valeriakan6474
    @valeriakan6474 2 роки тому

    Классная задачка,
    а вот мое супер неоптимальное решение, решила зачем-то сделать хэш, короче жуть, но вам в копилку комментов:
    let input = [10,20,30,40,50]
    const shuffleMy = (arr) => {
    const obj = {}
    let len = arr.length;
    arr.forEach((elem) => { // Set random order for each element in array, ex: obj = {'10': 5, '20': 1, '30': 3, '40': 4, '50': 2}
    let k = getRandomInt(len);
    if (Object.values(obj).indexOf(k) > -1){
    do {
    k = getRandomInt(len);
    } while (Object.values(obj).indexOf(k) > -1)
    }
    obj[elem] = k
    })
    return Object.entries(obj).sort((a, b) => a[1] - b[1]).map((elem) => elem[0]);
    }
    function getRandomInt(max) {
    return Math.floor(Math.random() * max);
    }
    for (let i = 0; i < 5; i++) {
    console.log(shuffleMy(input))
    }

    • @frontendscience
      @frontendscience  2 роки тому

      Благодарю за решение! Интнесный вариант вышел! 👍

  • @empfaze
    @empfaze 3 роки тому

    Добрый день!
    const input = [1, 2, 3, 4, 5];
    const shuffle = function (arr) {
    const result = [];
    for (let i = 0; i < arr.length; i++) {
    let tmpIndex = Math.floor(Math.random() * arr.length);
    while (result[tmpIndex]) {
    tmpIndex = Math.floor(Math.random() * arr.length);
    }
    result[tmpIndex] = arr[i];
    }
    return result;
    //return arr.sort((prev, next) => Math.random(next) - Math.random(prev));
    };
    console.log(shuffle(input));

  • @denisoleksyuk5346
    @denisoleksyuk5346 3 роки тому

    перед началом видео попробовл свой вариант, и потом понял что опять затупил, сделал переменую для последнего индекса хотя можно было циклом же идти из конца ):
    ```js
    const shuffle = (arr) => {
    let lastIndex = arr.length - 1;
    for (let i = 0; i < arr.length; i++) {
    const rnd = Math.floor(Math.random() * lastIndex);
    [arr[rnd], arr[lastIndex]] = [arr[lastIndex], arr[rnd]]
    lastIndex--
    }
    return arr
    };```

  • @alexanderruzhik9234
    @alexanderruzhik9234 2 роки тому +2

    Вот мой вариант программы, написал его до просмотра решения и возник вопрос: Можно ли использовать вместо (i + 1) --- arr.length и обязательно ли совершать обход с конца массива??
    function random(arr) {
    for (let i = 0; i < arr.length; i++) {
    const random = Math.floor(Math.random() * arr.length);
    [arr[i], arr[random]] = [arr[random], arr[i]];
    }
    return arr;
    }

    • @frontendscience
      @frontendscience  2 роки тому

      Да, прекрасный вариант. Разницы нету, что с начала, что с конца - эффект будет такой же.

    • @medvedovsky2028
      @medvedovsky2028 2 роки тому +1

      Разница будет. Вероятность некоторых исходов больше, чем других (можно проверить циклом). Возможно это из-за того, что начиная сначала числа оставшиеся позади i также могут поменяться, в отличии от вариации с конца, где числа позади i не трогаются.
      let count = {
      '123': 0,
      '132': 0,
      '213': 0,
      '231': 0,
      '321': 0,
      '312': 0,
      toString() {
      return `
      '123': ${count['123']},
      '132': ${count['132']},
      '213': ${count['213']},
      '231': ${count['231']},
      '321': ${count['321']},
      '312': ${count['312']},
      `
      }
      }
      for (let i = 0; i < 1000000; i++) {
      let array = [1, 2, 3];
      shuffle(array);
      count[array.join('')]++;
      };
      console.log(String(count))
      Итог:
      '123': 148536,
      '132': 184897,
      '213': 186002,
      '231': 184753,
      '321': 148272,
      '312': 147540,"
      Такие дела

  • @St3rnhunt3r
    @St3rnhunt3r 3 роки тому +1

    ЧтоЖ) Я сделал вот так:
    let input = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    function shuffel(rand) {
    rand.sort(() => Math.random() - 0.5);
    }
    shuffel(input);
    console.log(input);

    • @frontendscience
      @frontendscience  3 роки тому +2

      :) Я это называю - "сортировка - загадочная"!

    • @ИмяФамилия-э4ф7в
      @ИмяФамилия-э4ф7в 3 роки тому

      Чёт стрёмно. В документации есть требование, что колбек для одних и тех же элементов должен возвращать одинаковый результат. Иначе сортировка будет неустойчивой (это нас, в данном случае, не парит) и неопределённой по времени, да и вообще, наверное, может выдать ошибку. Самую лучшую из ошибок: которая иногда появляется (не воспроизводимую). Это отдельная мука в аду, фиксить такие ошибки.

  • @artemDutchak
    @artemDutchak 3 роки тому

    Если мы поменяли местами последний элемент с третьим, получается, когда мы дойдем то третьего элемента, то его можно уже не менять, т.к. здесь "рандомно" уже другое значение, которое отличается от входящего массива. Я правильно понимаю?

    • @frontendscience
      @frontendscience  3 роки тому +1

      ну может и так - но если ты его еще раз переставишь то так можно добиться более "высокого уровня" перемешиваемости

    • @artemDutchak
      @artemDutchak 3 роки тому

      @@frontendscience
      А я прям задумался... если функцию, основанную на Math.random(), вызвать дважды... будет ли результат более рандомный? Ведь эта функция не выдает абсолютно рандомное число, а вычисляет его как-то, и будет ли второй результат "более рандомный" чем первый? Как вообще можно измерить рандомность результата... И как можно написать свою функцию, выдающую рандомное число, кроме как с привязкой ко времени.
      Есть над чем подумать вместо сна :)

  • @FredUA
    @FredUA 3 роки тому

    Не понял зачем умножать на i+1 (let rnd = Math.floor(Math.random() * (i + 1))). Получается, что чем ближе к нулевому элементу тем меньше шансов стать этому элементу в конец массива?

    • @frontendscience
      @frontendscience  3 роки тому +1

      Нет. Распределение равномерное. Вот тут можно подробней почитать про рандомное целое число в определенном диапазоне. developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random#getting_a_random_integer_between_two_values
      У нас минимум -0, а максимум это i. При этом нам надо i включительно. Поэтому умножаем на i+1

    • @bibblebabl
      @bibblebabl 3 роки тому

      @@frontendscience А в чем преимущество идти с конца массива, а не с начала? от 0 до array.length? В чем профит?

    • @frontendscience
      @frontendscience  3 роки тому

      @@bibblebabl ни в чем ) Можно инвертировать все и идти с начала массива - эффект будет тот же. Почему везде в книгах этот алгоритм приводится именно с началом в конце - не знаю. Видать так исторически сложилось.

    • @arealitcy
      @arealitcy 3 роки тому

      @@frontendscience исторически сложилось из-за того, что бытует мнение, будто обход массива из конца в начало быстрее
      а если касательно именно этого алгоритма: могу предположить, что проходя массив в обратном порядке, на каждой итерации нужно выбирать случайное число в диапазоне [0, i], а не [i, arr.length], что выглядит чуть лаконичнее и требует меньше операций (но тоже такая себе оптимизация)

  • @Neravarinn
    @Neravarinn 3 роки тому

    Учу js и ничего умнее не придумал, чем решение в лоб. Спасибо за интересную задачку.
    let array = [1,2,3,4,5,6,7,8,9,10]
    let shuffle = function(arr) {
    let j=arr.length
    let count = new Array
    for (let i=1; i

  • @ИмяФамилия-э4ф7в
    @ИмяФамилия-э4ф7в 3 роки тому

    Интересный алгоритм. Пару мыслей по поводу:
    - Мы же не обязаны проходить по всему массиву, мы можем пройти до половины, до трёх четвертей; пройти полтора, два или 42 раза по массиву. Интересно, после какого минимального числа итераций, грубо говоря "степень смешанности массива" уже не увеличивается (и как её вообще определить)?
    - Мы же не обязаны брать случайное число от 0 до i, мы можем брать до arr.length. Как это повлияет на перемешивание, и повлияет ли вообще?
    Оба вопроса, очевидно, больше к математикам, чем к программистам.

    • @EvilYou
      @EvilYou 3 роки тому

      1) Если нужна правильная (равномерная) сортировка, то обязаны. Например, если сортируем 1/5 массива из 10 элементов, то как минимум 6 элементов останутся на своих местах. Если проходить до 1/2 или 3/4 то там все равно есть вероятность у оставшихся элементов быть не сдвинутыми.
      2) Вопрос хороший. Я протестировал на большом количестве массивов, у меня в обоих случаях вышел одинаковый результат.

    • @sokoloff114
      @sokoloff114 3 роки тому

      2. задумался и решил проверить. Получилось, что для короткого массива [1,2,3] разница просто огромна: при прогоне до (i+1) всё хорошо, а вот при прогоне до length
      определенные комбинации выпадают в 2 раза чаще других.
      Пояснение по коду: взял [1,2,3], перед сортировкой сделал копию (Сергей, кстати, сортирует каждый раз результат предыдущей сортировки, а не исходный массив). 9000 тысяч раз сортирую массив и записываю получившийся результат (вариантов всего 6, поэтому все наглядно получилось).
      Соответственно, в среднем на 9000 прогонов и 6 вариантов каждая комбинация должна выпадать примерно 1500 раз. При i+1 так и вышло.
      const arr = [1,2,3];
      function shuffle(array) {
      const shuffled = array.slice();
      for (let i = shuffled.length - 1; i > 0; i--) {
      let j = Math.floor(Math.random() * (i+1)); // or shuffled.length
      [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
      }
      return shuffled.join('');
      }
      const results = [0,0,0,0,0,0];
      for (let i = 0; i < 9000; i++) {
      const res = shuffle(arr);
      if (res === '123') results[0]++;
      if (res === '132') results[1]++;
      if (res === '312') results[2]++;
      if (res === '231') results[3]++;
      if (res === '321') results[4]++;
      if (res === '213') results[5]++;
      }

      console.log(results);
      // [ 2028, 1955, 1973, 1004, 1025, 1015 ] for length
      // [ 1520, 1513, 1530, 1439, 1511, 1487 ] for i+1

  • @Никита-ы1к2ш
    @Никита-ы1к2ш 3 роки тому

    методом map возможно решить ?

    • @frontendscience
      @frontendscience  3 роки тому

      Нет - через map не выйдет. С помощью map можно заполнить массив рандомными числами например, но перемешать имеющиеся элементы - не выйдет.

  • @rssreader90
    @rssreader90 2 роки тому

    спасибо

  • @kost9n4eGG
    @kost9n4eGG 3 роки тому

    const mockData = [1,2,3,4,5,6,7]
    const shuffle = (incomingArray, resultArray = []) => {
    if (incomingArray.length === 0) {
    return resultArray
    }
    const randomItem = Math.floor(Math.random() * incomingArray.length);
    resultArray.push(incomingArray[randomItem])
    incomingArray.splice(randomItem, 1);
    return shuffle(incomingArray, resultArray)
    }
    console.log(shuffle(mockData))

  • @rakhimovkamran
    @rakhimovkamran 3 роки тому +2

    array.sort((a, b) => Math.random() > 0.5 ? 1 : -1)

  • @yarik83men51
    @yarik83men51 3 роки тому

    Java:
    public class ShuffleSortArray {
    public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for (int i = 0; i < 10; i++) {
    shuffleArray(array);
    }
    }
    private static void shuffleArray(int[] arr){
    for (int i = 0; i < arr.length; i++) {
    int i1 = (int) (Math.random() * arr.length);
    int i2 = (int) (Math.random() * arr.length);
    int temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
    }
    System.out.println(Arrays.toString(arr));
    }
    }

  • @АлександрОхременко-н8й

    А как же функциональное программирование с его иммутабельностью?) Изначальный массив изменяется внутри функции, что не есть хорошо.

    • @frontendscience
      @frontendscience  3 роки тому +1

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

    • @АлександрОхременко-н8й
      @АлександрОхременко-н8й 3 роки тому

      @@frontendscience давно фронтендеры занимаются обработкой огроменных массивов данных?)
      Любые мутации в процессе работы программы , потенциально, вызывают лишь геморрой, с которым после вас будет кто-то бороться и искать его, ценой в пару Кб оперативной памяти (не говорим о системах, которые обрабатывают огромные массивы данных, где пренебрежение этим вполне обоснованно, канал про фронтенд).

    • @frontendscience
      @frontendscience  3 роки тому

      ​@@АлександрОхременко-н8й Фронтенд бывает разный) Он не только такой, как в Ваших фантазиях. Если Вы для себя определили уже Вашу зону компетенции и зону развития - не учите алгоритмы. Выбор всегда за Вами.

    • @frontendscience
      @frontendscience  3 роки тому +2

      @@bohdanHutorIT Именно! Надо учитывать контекст! Конкретно в этом случае мы решаем задачи с Leetcode (попутно изучаем различные алгоритмы). На Leetcode для всех задач необходимо найти наиболее оптимальное решение как по времени, так и по памяти.

  • @andrey-frontend
    @andrey-frontend 2 роки тому

    Я сначала думал из массива брать подряд числа и в зависимости от того что покажет рандом либо добавлять их в начало, либо добавлять в конец массива

  • @ВасилийБарков-к2э

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

  • @Лесорубовлеха
    @Лесорубовлеха 2 роки тому

    у меня блин не получилось. я даже не догадался как сделать через метод sort, но теперь понял как делать через фишера

  • @-anonim-3008
    @-anonim-3008 2 роки тому

    Не понимаю, зачем нам нужно умножать на i+1 рандомное число

    • @andrey-frontend
      @andrey-frontend 2 роки тому +2

      Функция рандом выводит рандомное число оно выглядит так 0

  • @wisarty
    @wisarty 2 роки тому +1

    Дякую

  • @jorgen5462
    @jorgen5462 3 роки тому +1

    В субтитрах мне пишет: "с вами Сергей Пузырьков..." Ну, думаю, юморист, Серёга. Но нет, это ИИ юморит😂 хотя сортировки пузырьком тут, скорее всего, не будет 🤔

  • @michaelmorrison6379
    @michaelmorrison6379 3 роки тому +1

    мда уж, если бы на собесах такие задачи были :(

    • @frontendscience
      @frontendscience  3 роки тому +1

      В смысле? :) Так они и бывают на собесах - поэтому мы эту рубрику и ведем)
      Мне лично в 2015 году на собеседовании дали эту задачу.
      Присылайте задачи, которые попадались Вам.

  • @VYuhim
    @VYuhim 3 роки тому +1

    Лучше бы исходный массив не мутировать =)

    • @frontendrules7
      @frontendrules7 3 роки тому

      Лучше, но тогда сложность по памяти будет O(n) а не O(1) ;)

    • @ИмяФамилия-э4ф7в
      @ИмяФамилия-э4ф7в 3 роки тому

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

    • @frontendscience
      @frontendscience  3 роки тому

      @@ИмяФамилия-э4ф7в На Leetcode во всех задачах необходимо найти решение наиболее оптимальное как по времени, так и по памяти.

    • @ИмяФамилия-э4ф7в
      @ИмяФамилия-э4ф7в 3 роки тому

      @@frontendscience это тут ни при чём. Требование мутировать или не мутировать входные данные внешнее по отношению к задаче. Т.е. в условии должно быть либо "вернуть новый массив, который ..." либо "перемешать данный массив..." А вот как реализовать указанное поведение оптимально по времени и по памяти - это вопрос задачи.

    • @frontendscience
      @frontendscience  3 роки тому

      @@ИмяФамилия-э4ф7в Для того чтобы не мутировать входные данные, их необходимо будет скопировать. И это значит, что уже по памяти сложность будет O(n), а не O(1). Причем тут Ваш комментарий? У задачи есть четкие требования.

  • @viv81ster
    @viv81ster 3 роки тому

    Если точно знать что значения только int то можно избавится от tmp переменной

    • @frontendscience
      @frontendscience  3 роки тому

      Даже если можно избавиться - ч в решениях часто делаю избыточные переменные в угоду читаемости и для лучшего понимания что происходит в коде. К счастью на результирующую сложность это не особо влияет.

  • @ПетроПередерий-р1у
    @ПетроПередерий-р1у 3 роки тому +1

    Ну, блин, что за выражение ОТСОРТИРОВАНО в случайном порядке???? Да не отсортировано, а ПЕРЕМЕШАНО случайным образом. Я уже с перепугу подумал что можно сортировать массивы в убывающем или возрастающем порядке с помощью рандома.

    • @frontendscience
      @frontendscience  3 роки тому

      Ну вообще то есть такое выражение отсортирован в случайном порядке. Это и есть принцип сортировки - случайный порядок. Кстати когда-то видел вариант когда в функции sort, рандомным образом выбиралось -1,0,1 :)

    • @ИмяФамилия-э4ф7в
      @ИмяФамилия-э4ф7в 3 роки тому +1

      Можно сортировать, не вижу проблем. Перемешиваешь, проверяешь: если для каждого i arr[i] >= arr[i+1] то возвращаем результат, если нет, то снова перемешиваем...
      По-моему, этот алгоритм лежит в основе работы Windows, visual studio, android studio и т.п. Но это не точно...

    • @arealitcy
      @arealitcy 3 роки тому

      вообще можно, алгоритм называется bogosort (эзотерический алгоритм, больше для фана, чем для реальной пользы)

  • @ruff3d
    @ruff3d 3 роки тому +3

    не глядя решение
    [1,2,3,4,5].sort(()=>Math.floor(Math.random()*10) % 2 || -1)

    • @hakobandreasyan8239
      @hakobandreasyan8239 3 роки тому

      а почему атор не упомянул эту версию ?
      const shuffle = (arr) => arr.sort(() => 0.5 - Math.random());

    • @andreylomakin6353
      @andreylomakin6353 3 роки тому +2

      @@hakobandreasyan8239 потому что мы мутируем arr, нужно [...arr]

    • @goldstein1
      @goldstein1 3 роки тому +1

      Оно должно получиться больше по сложности, тк алгоритм сортировки внутри js в таком случае делает больше итераций) В документации напрямую просят не использовать конструкцию, возвращающую неопределенный результат, тк, кроме неустойчивого времени выполнения, могут быть выброшены неожиданные исключения

    • @ruff3d
      @ruff3d 3 роки тому

      @@andreylomakin6353 оно ж просто возвращает, не мутирует....🤔