0 / 0 / 1
Регистрация: 02.03.2017
Сообщений: 26
1

Эффективный алгоритм перетасовки элементов массива

02.03.2017, 09:39. Показов 1972. Ответов 8
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Друзья, написал вот такую функцию

Java
1
2
3
4
5
6
7
8
9
10
    public static void arrayShuffle(int[] arr)
    {
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            int rnd = (int)(Math.random() * length);
            int tmp = arr[i];
            arr[i] = arr[rnd];
            arr[rnd] = tmp;
        }
    }
Предполагаю, что это не самый совершенный вариант.
Для перетасовки n элементов производится n*4 действий (проверьте плиз правильно ли я понимаю таковые измерения).
Длину массива кладу в переменную length чтобы повторно в цикле не вызывать свойство array.length . Если в этом смысл? Экономлю я вообще тут что-нть?
Покажите алгоритм покруче.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.03.2017, 09:39
Ответы с готовыми решениями:

Эффективный алгоритм для задачи
Условия следующие: Даны n различных натуральных чисел и число m. Нужно выяснить, можно ли...

Эффективный алгоритм сортировки одного массива по данным другого массива
Всем привет! Время сортировки массива с 2 млн. строк - 0,85 сек., Время сортировки массива...

Подскажите эффективный алгоритм сортировки массива (желательно многомерного ) на VB
Подскажите эффективный алгоритм сортировки массива (желательно многомерного ) на VB

Какой самый эффективный алгоритм для поиска одинаковых элементов в двух возрастающих массивах?
какой?

8
183 / 110 / 44
Регистрация: 03.07.2016
Сообщений: 496
02.03.2017, 10:01 2
Как по мне с рандомом это дело плохое. Рандом он такой рандомный, может прост нехрена не перетасовать.
0
Эксперт Java
2398 / 2223 / 565
Регистрация: 28.12.2010
Сообщений: 8,672
02.03.2017, 10:20 3
Цитата Сообщение от shiva-it Посмотреть сообщение
Для перетасовки n элементов производится n*4 действий
никому не интересно сколько происходит действий. В данном случае тут линейная сложность.
Можете использовать Collections.shuffle.
0
0 / 0 / 1
Регистрация: 02.03.2017
Сообщений: 26
02.03.2017, 10:33  [ТС] 4
Цитата Сообщение от KEKCoGEN Посмотреть сообщение
никому не интересно сколько происходит действий. В данном случае тут линейная сложность.
Можете использовать Collections.shuffle.
А если все же решать задачу без привлечения высокоуровневых методов? задача-то не практическая, а учебная. Мне интересно есть ли какой-то алгоритм с "нелинейной сложностью" и красивым кодом.
0
Эксперт Java
2398 / 2223 / 565
Регистрация: 28.12.2010
Сообщений: 8,672
02.03.2017, 10:37 5
Цитата Сообщение от shiva-it Посмотреть сообщение
с "нелинейной сложностью"
а с какой? С константной? Логика говорит что нет такого алгоритма

Цитата Сообщение от shiva-it Посмотреть сообщение
красивым кодом.
Цитата Сообщение от shiva-it Посмотреть сообщение
без привлечения высокоуровневых методов
эти два утверждения противоречивы.

Посмотрите как написан shuffle. Там примерно то же что и у вас.
0
0 / 0 / 1
Регистрация: 02.03.2017
Сообщений: 26
02.03.2017, 10:51  [ТС] 6
Как смотреть устройство метода shuffle? сорри за тупой вопрос
0
183 / 110 / 44
Регистрация: 03.07.2016
Сообщений: 496
02.03.2017, 11:04 7
На вот такой алгорит. Тасование Фишера–Йетса
До вечера реализуй, домашнее задание тебе будет)
0
Эксперт Java
2398 / 2223 / 565
Регистрация: 28.12.2010
Сообщений: 8,672
02.03.2017, 12:44 8
shiva-it, http://grepcode.com/file/repos... il.List%29
0
0 / 0 / 1
Регистрация: 02.03.2017
Сообщений: 26
02.03.2017, 15:37  [ТС] 9
Borsche, как-то так. Готов к доработке, но "до вечера" без доработки. Отличная задача. Спасибо. Жду примечаний. Не уверен в присваивании возвращенного из метода массива. Как-то будто не красиво. Или ниче?

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.io.IOException;
 
 
public class Main {
 
    public static void main(String[] args) throws IOException{
 
        int[] arr = {1,11,1,5,7,9,2,6,8,0};
 
        //просто вывод
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
 
        arr = fisherYetsShuffle(arr);
 
        //просто вывод
        System.out.println();
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    public static int[] fisherYetsShuffle(int[] arr)
    {
        int[] resultArr = new int[arr.length];
 
        for (int i = 0; i < arr.length; i++) { //i будем использовать как индекс в результирующем массиве
            int pos = (int) (Math.random() * (arr.length - i)); // диапазон случайного число уменьшем на 1 при кажой итерации
            resultArr[i] = getValByIndex(pos,arr);
        }
 
        return resultArr;
    }
 
    public static int getValByIndex(int pos, int[] arr) {
    //возвращает значение pos-ного элемента не равного -1 и вносит на его место -1
        int counter = -1;
        int res = 0;
 
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != -1) {
                counter++;
            }
            if(counter == pos)
            {
                res = arr[i];
                arr[i] = -1;
                break;
            }
 
        }
        return res;
    }
}
0
02.03.2017, 15:37
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.03.2017, 15:37
Помогаю со студенческими работами здесь

Эффективный алгоритм поиска простых чисел на С++
Хотел написать функцию которая вычисляет простое число или сложное, но оно не вычисляется. Цикл...

Разработать эффективный алгоритм быстрой сортировки
Быстрая сортировка. Разработайте эффективный алгоритм для упорядочивания n элементов таким образом,...

Эффективный алгоритм поиска значения в столбце
У меня происходит просмотр столбца А, и последовательный поиск каждого значения из этого столбца в...

Более эффективный алгоритм нахождения суммы sin^n(x)
найти сумму sin(x)+sin^2(x)+...+Sin^n(x) или другую любую сумму cout &lt;&lt; &quot;input value of n&amp;x&quot; &lt;&lt;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru