Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / быстродейсвенный алгоритм сортировки / 13 сообщений из 13, страница 1 из 1
16.06.2017, 16:01
    #39473240
dimkalimit
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
Имеется например лист ArrayList =[234,2143,23,542,2,42,254,3].(размер листа будет большой)

Нужно его отсортировать причем, чтобы временная сложность была наименьшей должно использоваться мало памяти.
Хотел использовать метод из класса Collections: Collections.sort(list);
есть ли более лучший способ ?
...
Рейтинг: 0 / 0
16.06.2017, 16:12
    #39473247
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
dimkalimitчтобы временная сложность была наименьшей должно использоваться мало памяти
Фтопку "временную сложность". Нужна производительность - тратим память. Нужна память - теряем в производительность. Стандартный trade off.
...
Рейтинг: 0 / 0
16.06.2017, 16:14
    #39473249
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
dimkalimit,

Можно существенно выиграть в производительности, если выкинуть обертки для целых чисел и перейти на массив и примитивы.
...
Рейтинг: 0 / 0
16.06.2017, 16:33
    #39473269
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
...
Рейтинг: 0 / 0
16.06.2017, 16:56
    #39473305
dimkalimit
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
Т.е. оптимальный вариант использовать quicksort
...
Рейтинг: 0 / 0
16.06.2017, 16:57
    #39473308
dimkalimit
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
dimkalimitТ.е. оптимальный вариант использовать quicksort
???
...
Рейтинг: 0 / 0
16.06.2017, 16:59
    #39473311
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
dimkalimit,

YouTube Video
...
Рейтинг: 0 / 0
16.06.2017, 17:02
    #39473314
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
dimkalimitТ.е. оптимальный вариант использовать quicksort
В определённых обстоятельствах - да. В других, возможно, нет. Я же привел ссылку.
...
Рейтинг: 0 / 0
17.06.2017, 10:09
    #39473549
vas0
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
Если диапазон допустимых значений в списке небольшой, то лучше вообще не сортировать, а подсчитать количество вхождений каждого элемента. Потом "воссоздать" нужный список.

Трудоемкость будет линейная (n), а не как у одного из алгоритмов быстрой сортировки n * log(n).

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 2, 2, 1};
        int[] b = {0, 0, 0, 0};

        for (int elem : a) {
            b[elem]++;
        }

        for (int elem : b) {
            System.out.print(elem + " ");
        }
    }
...
Рейтинг: 0 / 0
17.06.2017, 10:13
    #39473551
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
vas0,

Напомнили про bitmap .
...
Рейтинг: 0 / 0
17.06.2017, 21:16
    #39473667
dimkalimit
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
vas0Если диапазон допустимых значений в списке небольшой, то лучше вообще не сортировать, а подсчитать количество вхождений каждого элемента. Потом "воссоздать" нужный список.

Трудоемкость будет линейная (n), а не как у одного из алгоритмов быстрой сортировки n * log(n).

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 2, 2, 1};
        int[] b = {0, 0, 0, 0};

        for (int elem : a) {
            b[elem]++;
        }

        for (int elem : b) {
            System.out.print(elem + " ");
        }
    }



не понял этого решения. Здесь же мы не получим отсортированный список ?
...
Рейтинг: 0 / 0
17.06.2017, 21:56
    #39473672
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
dimkalimitне понял этого решения. Здесь же мы не получим отсортированный список ?vas0Потом "воссоздать" нужный список.
...
Рейтинг: 0 / 0
17.06.2017, 22:43
    #39473680
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
быстродейсвенный алгоритм сортировки
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / быстродейсвенный алгоритм сортировки / 13 сообщений из 13, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]