Все технические форумы на одном сайте Удобный поиск информации с популярных форумов в одном месте
Вопрос: Какой алгоритм сортировки быстрее найдет k-й элемент

Пусть дан массив чисел. Отсортируем его по возрастанию. k-e число назовем k-й порядковой статистикой. Модификация какого из алгоритмов сортировки позволяет быстро найти k-ю порядковую статистику?
Ответ: сортировка вставками?
Ответ: HeapSort'ом быстрее. На основе QSort'а вообще ищется за O(n) в худшем случае.
Но если этот вопрос в разделе Python, то вероятный ответ - стандартной питоновской сортировкой. Я как-то пытался накидать по Кнуту алгоритм, который O(n) в худшем случае, но на рандомных данных полная сортировка всего массива получилась быстрее.
Читать все 3 сообщений
Вопрос: Сравнение скорости двух алгоритмов сортировки jUnit

Решил потестить алгоритмы, заодно поучить jUnit.

Вот класс сортировок,
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

public class Sort {
 
    private int[] array;
 
    public Sort(int[] array) {
        this.array = array;
    }
 
    public void perebor() {
        for (int i = 0; i < array.length; ++i) {
            for (int j = i; j < array.length;  ++j) {
                if (array[j] < array[i]) {
                    swap(j, i);
                }
            }
        }
    }
 
    public void bubble() {
        boolean change;
        do {
            change = false;
            for (int i = 0; i < array.length-1; ++i) {
                if (array[i] > array[i+1]) {
                    swap(i, i+1);
                    change = true;
                }
            }
        } while (change);
    }
 
    private void swap(int firstIndex, int secondIndex) {
        int temp = array[firstIndex];
        array[firstIndex] = array[secondIndex];
        array[secondIndex] = temp;
    }
 
    public int[] getArray() {
        return array;
    }
}
И класс тестов
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

import org.junit.Before;
import org.junit.Test;
 
public class SortTest {
    private final int LENGTH = 50000;
    private Sort sort;
    private int[] array = new int[LENGTH];
 
    @Before
    public void init() {
        for (int i = 0; i < array.length; ++i) {
            array[i] = (int)(Math.random() * LENGTH);
        }
 
        sort = new Sort(array);
    }
 
    @Test(timeout = 30000)
    public void test_perebor() {
        sort.perebor();
    }
 
    @Test(timeout = 30000)
    public void test_bubble() {
        sort.bubble();
    }
}
Так вот. Пузырьковый метод всегда быстрее.
У меня вопрос. Или я не правильно понимаю алгоритмы сортировки или я не правильно пишу тесты.
Ответ: Что за перебор? Никогда не слышал о такой сортировке.
Можете дать описание?
Почему вы думаете, что пузырёк должен быть медленнее перебора?
Читать все 5 сообщений
Вопрос: Распараллеливание алгоритма сортировки

Доброго времени суток.

Есть программа, в которой реализуется распараллеливание алгоритма сортировки массива. Проблема заключается в том, что я не знаю как синхронизировать эти потоки с помощью критических секций, мьютексов и семафоров.

Помогите пожалуйста с синхронизацией сортировки. Заранее спасибо!

Мой код:

C++ (QT)
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include <iostream>
#include <stdlib.h>
#include <Windows.h>
#include <ctime>
using namespace std;
 
typedef struct threadParam_tag{
    int *ptr;
    int indexStart;
    int indexEnd;
    int length;
}threadParam;
 
//========================================================
 
DWORD WINAPI SortArray(LPVOID lpParam)
{
    
 
    int *ptr = ((threadParam*)lpParam)->ptr;
    int startIndex = ((threadParam*)lpParam)->indexStart;
    int endIndex =  ((threadParam*)lpParam)->indexEnd;
    int length =  ((threadParam*)lpParam)->length;
 
 
 
    // ВЫВОД НА ЭКРАН
    cout<<"\n\nDiapazon: "<<startIndex<<" ->> "<<endIndex<<endl;
 
    cout<<"Before Sort:\n";
    for(int i=0; i<length; i++)cout<<ptr[i]<<", "; cout<<endl;
 
    // СОТРИРОВКА
 
    int tmp = 0;
    for(int i=startIndex; i<endIndex; i++)
        for(int j=startIndex; j<endIndex; j++)
            if(ptr[i] < ptr[j])
            {
                tmp = ptr[i];
                ptr[i] = ptr[j];
                ptr[j] = tmp;
            }
 
    // ВЫВОД НА ЭКРАН
    cout<<"After Sort:\n";
    for(int i=0; i<length; i++)cout<<ptr[i]<<", "; cout<<endl;
 
    return 0;
}
 
//========================================================
 
void main()
{
    srand(time(NULL));
    int arrSize;
    int numOfThreads;
    int numOfPriority;
    
 
    DWORD thread_priority; 
    DWORD thread_ID;
 
    cout<<"Array size: "; cin>>arrSize;
    cout<<"Num of Threads: "; cin>>numOfThreads;
    cout<<"NumOfPriority (0-IDLE; 1-LOWEST; 2-NORMAL; 3-HIGHEST; 4-TIME_CRITICAL):"; cin>>numOfPriority;
 
    if(numOfPriority == 0)thread_priority = THREAD_PRIORITY_IDLE;
    else if(numOfPriority == 1)thread_priority = THREAD_PRIORITY_LOWEST;
    else if(numOfPriority == 2)thread_priority = THREAD_PRIORITY_NORMAL;
    else if(numOfPriority == 3)thread_priority = THREAD_PRIORITY_HIGHEST;
    else if(numOfPriority == 4)thread_priority = THREAD_PRIORITY_TIME_CRITICAL;
 
    HANDLE *hThr = new HANDLE[numOfThreads];    // МАССИВ УКАЗАТЕЛЕЙ НА ПОТОК
 
    threadParam *MyParam = new threadParam[numOfThreads]; // МАССИВ СТРУКТУР ДЛЯ ПЕРЕДАЧИ ПАРАМЕТРОВ ПОТОКУ
 
    int *MyArray = new int[arrSize];    // СОРТИРУЕМЫЙ МАССИВ
    for(int i=0; i<arrSize; i++)MyArray[i] = 1+rand()%100; // ЗАПОЛНЕНИЕ МАССИВА
 
    int step = arrSize/numOfThreads;
 
    for(int i=0; i<numOfThreads; i++)
    {
        MyParam[i].ptr = MyArray;
        MyParam[i].indexStart = i*step;
        MyParam[i].indexEnd = i*step+step-1;
        MyParam[i].length = arrSize;
        if(i == numOfThreads - 1)MyParam[i].indexEnd = arrSize-1;
    }
 
 
    for(int i=0; i<numOfThreads; i++)
    {
 
        hThr[i] = CreateThread(NULL, 0, SortArray, (PVOID)&MyParam[i], CREATE_SUSPENDED, &thread_ID);
        SetThreadPriority(hThr[i],thread_priority);
        ResumeThread(hThr[i]);
        Sleep(100);
 
    }
    system("pause");
}
Ответ: yusovich,
1. У тебя сортируются только отдельные области массива, нужно потом эти области после сортировки сливать в один массив и уже потом выводить на экран
2. неправильно задан цикл сортировки,надо
C++
1
2
3
4
5
6
7
8

for(int i=startIndex; i<=endIndex; i++)
        for(int j=startIndex; j<=endIndex; j++)
            if(ptr[i] < ptr[j])
            {
                tmp = ptr[i];
                ptr[i] = ptr[j];
                ptr[j] = tmp;
            }
Читать все 3 сообщений
Вопрос: Распараллеливание алгоритма сортировки - метод вставки

Здравствуйте нужно осуществить распараллеливание алгоритма сортировки - метод вставки на N отдельных потоков. Есть идеи как это осуществить?

Добавлено через 1 час 54 минуты
согласен оплатить за работу
Ответ: сортировку масива методом вставки
Читать все 4 сообщений
Вопрос: Книги про алгоритмы сортировок

Подскажите книги про алгоритмы сортировки. Если можно русскоязычные.
Ответ: Ахо, Хопкрофт, Ульман. Структуры данных и алгоритмы.
Читать все 8 сообщений
Вопрос: Алгоритм сортировки массива методом чёт-нечет

где раздобыть алгоритм сортировки статичного массива однобайтных данных по возрастанию методом четное-нечётное? (картинка, блоксхема)? не программа, а схема нужна...
Ответ:
Сообщение от ololo111
даже схема сравнения чисел иная чем в паскале
Для блок-схемы алгоритм сравнения чисел в данном конкретном языке не имеет значения: рисуется ромб и в нем пишется, что с чем надо сравнить, и что делать в случае "да", и в случае "нет". А уж как потом сравнивать - это уже при реализации на конкретном языке пускай программист думает.
Читать все 5 сообщений
Вопрос: Программа, демонстрирующую работу различных алгоритмов сортировки

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

Необходимо реализовать три простых алгоритма «пузырёк», «вставка», «выбор» и «быстрая сортировка».
Числа сортируемого массива на экране отображается в виде цветных линий, большему числу соответствует более длинная линия. При запуске приложения массив сначала заполняется случайными числами в диапазоне от 5 до 100. Все четыре алгоритма сортировки работают с одинаковым исходным не отсортированным массивом чисел.

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


При запуске приложения кнопки для каждого алгоритма сортировки находятся в следующем состоянии:
• кнопка один доступна, отображается надпись «Старт»;
• кнопка два недоступна, отображается надпись «Пауза».
на рисунке в этом состоянии находятся сортировка «Пузырёк» и «Быстрая».

При нажатии на кнопку «Старт», начинает работать соответствующий алгоритм сортировки. После перестановке двух чисел в массиве, линии соответствующие данным числам также должны поменяться местами (работа алгоритма визуализируется). Алгоритмы должны работать с некоторой задержкой, между шагами сортировки, чтобы пользователь успевал просматривать происходящие над массивом изменения. В режиме работы алгоритма кнопки находятся в следующем состоянии:
• кнопка один доступна, отображается надпись «Стоп»;
• кнопка два доступна, отображается надпись «Пауза».
на рисунке в этом состоянии находится сортировка «Вставка».
При работающем алгоритме сортировки пользователь может нажать на любую из двух кнопок. Если пользователь нажимает на кнопку «Пауза», то работа алгоритма сортировки приостанавливается, с возможностью дальнейшего продолжения работы алгоритма, с места остановки. В этом случае кнопки для алгоритма сортировки находятся в следующем состоянии:
• кнопка один доступна, отображается надпись «Стоп»;
• кнопка два недоступна, отображается надпись «Продолжить».
на рисунке в этом состоянии находится сортировка «Выбор».
Если пользователь при приостановленной работе алгоритма нажимает на кнопку «Продолжить» то работа алгоритма возобновляется.

При нажатии на кнопку «Стоп» алгоритм останавливает свою работу, и переходит в своё первоначальное состояние, т.е. в состояние которое было у алгоритма в момент запуска приложения.
Если алгоритм сортировки отработал до конца, то визуальное отображение массива остаётся отсортированным, а кнопки переходят в своё первоначальное состояние.
Необходимо подсвечивать различными цветами отсортированную и не отсортированную часть массива, где это возможно.


Помогите с реализацией задания, хотя бы с графическим интерфейсом и с чего начать это всё делать.
Ответ: Таки такой апплет был где-то в демках самого jdk, в шестой версии так точно видел.
Читать все 4 сообщений
Вопрос: Алгоритмы сортировок

Наиболее часто задаваемые вопросы по С++. Реализация распространенных алгоритмов, решения типовых задач.


Статьи и учебники C++

Оглавление:
0. Сортировка
Выбором
Пузырьком
Вставками
Шелла
Пирамидальная
Быстрая (хоара)
Поразрядная

Если вы новичок,и не понимаете,что такое template<class T> или не проходили этого, то есть два способа справиться с этой проблемой:
1. Загуглить "Шаблоны С++". Материал простой,разберетесь
2. Убрать эту надпись,а в прототипе букву T заменить типом вашего массива (int, double,..etc)
Ответ: Сортировка подсчётом (предложил name?)

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

Код C++
1
2
3
4
5
6
7
8
9
10
11

void counting_sort (int *vec, int len, int min, int max) {
 
  int *cnt = new int[max-min+1];
 
  for(int i = min; i <= max; ++i) cnt[i - min] = 0;
  for(int i = 0; i < len; ++i) ++cnt[vec[i] - min];
 
  for(int i = min; i <= max; ++i)
    for(int j = cnt[i - min]; j--;)
      *vec++ = i;
}
Читать все 5 сообщений
Вопрос: Исследование эффективности алгоритмов сортировки

Разработать программу, определяющую какое время требуется для сортировки с помощью каждого из трех методов (обменами, вставками, выбором).
Алгоритм сортировки обменами (алгоритм "пузырька")
Алгоритм сортировки вставками
Алгоритм сортировки выбором элемента
если вас не затруднит,помогите мне!
Ответ: Уважаемый не путайте "Помогите" и Сделайте за меня"...
Если вам нужна помощь то скидывайте код. Место где вылетает ошибка.
Читать все 4 сообщений
Вопрос: Обобщенный алгоритм сортировки

как это можно сделать???

необходимо модифицировать
шаблонный класс связного списка: добавить метод, реализующий обобщенный
алгоритм сортировки, независимый от типа элементов списка и критериев
сортировки.
С этой целью необходимо применить паттерн «стратегия» (strategy):
инкапсулировать алгоритм сравнения объектов по определенному критерию в
специальный класс-компаратор и передавать объект данного класса в качестве
параметра метода сортировки связного списка. Таким образом,
обеспечивается взаимозаменяемость алгоритмов сравнения двух объектов по
различным критериям при реализации обобщенного алгоритма сортировки.
Чтобы унифицировать прототипы методов сравнения в различных
классах-компараторах и гарантировать единообразный механизм их применения,
следует использовать такие принципы ООП, как наследование и полиморфизм
(динамическое связывание). В классах-компараторах должен замещаться
виртуальный метод сравнения, унаследованный от общего родительского
класса. Чтобы обеспечить возможность применения компаратора к любым
типам, в качестве параметров метод сравнения должен принимать указатели на
пустой тип данных.

Связный список есть

Добавлено через 5 часов 28 минут
upupup
Ответ: cherc,
C++
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
56
57

class Comp_base
{   // базовый класс компаратор
protected:
    const void* my_data;    // для унарного operator()
    Comp_base(const void* data = nullptr) : my_data(data) {}    // конструктор
public:
    virtual bool operator()(const void* lh, const void* rh) const = 0;  // бинарный предикат сравнения сравнения
    virtual bool operator()(const void* obj) const = 0; // унарный предикат сравнения сравнения
    virtual ~Comp_base() {}
};
 
template<typename T> void MergeSort(MyList<T>& list, const Comp_base& foo)
{
    if (list.size > 1)
    {
        MyList<T> left;
        MyList<T> right;
        DivList(list, left, right);
 
        MergeSort(left);
        MergeSort(right);
        MyList<T> temp;
        while (0 < left.size || 0 < right.size)
        {
            if (foo(&left.GetData(0), &right.GetData(0)))
            {
                temp.Add(left.GetData(0));
                left.Remove(0);
            }
            else
            {
                temp.Add(right.GetData(0));
                right.Remove(0);
            }
            if (left.size == 0)
            {
                while (right.size)
                {
                    temp.Add(right.GetData(0));
                    right.Remove(0);
                }
                break;
            }
            if (right.size == 0)
            {
                while (left.size)
                {
                    temp.Add(left.GetData(0));
                    left.Remove(0);
                }
                break;
            }
        }
 
        list = temp;
    }
}
Читать все 3 сообщений