Форум программистов, компьютерный форум CyberForum.ru

Сортировка - C++

Восстановить пароль Регистрация
 
maks_b1
 Аватар для maks_b1
1 / 1 / 0
Регистрация: 26.11.2011
Сообщений: 29
16.12.2011, 18:27     Сортировка #1
помогите пожалуйста создать сортировку, а то у меня даже фантазии не хватает как это сделать:
"Еще один практически важный алгоритм сортировки таков: чтобы отсортировать массив, выберем случайный его элемент b, и разобъем массив на три части: меньшие b, равные b и большие b. Теперь осталось отсортировать первую и третью части: это делается тем же способом. Время работы этого алгоритма - случайная величина; можно доказать, что в среднем он работает не больше C*n*log n. "

Добавлено через 44 секунды
может в виде бинарного дерева можно?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2011, 18:27     Сортировка
Посмотрите здесь:

C++ Сортировка подсчетом и LSD сортировка
C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) C++
шейкерная сортировка + сортировка слиянием C++
Пирамидальная сортировка и сортировка Шелла C++
2 сортировки: пирамидальная сортировка и сортировка слиянием C++
C++ Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
16.12.2011, 18:42     Сортировка #2
Цитата Сообщение от maks_b1 Посмотреть сообщение
может в виде бинарного дерева можно?
Сортировка Хоар http://ru.wikipedia.org/wiki/%D0%91%...B2%D0%BA%D0%B0
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
16.12.2011, 19:02     Сортировка #3
выбираем максимальный элемент, ставим в начало и т.д.
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
58
59
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
void printArray(double* arr, const unsigned len)
{//Вывод массива. Отличный пример самого простого перебора элементов массива.
        for(int i = 0; i != len; ++i)
        {
                printf("%lf\n",arr[i]);
        }
}
 
double* maximum(double* arr, const unsigned len)
{//Поиск максимума.
        double* ret = arr;//Пусть, для начала максимальным элементом будет нулевой
        for(int i = 1; i != len; ++i)//Далее перебрать остальные элементы
        {//Если текущий элемент больше возвращаемого, назначить возвращаемый текущим, иначе ничего не делать
                ret = arr[i] > *ret ? arr + i : ret;
        }
        return ret;
}
void swap (double* a, double* b)
{//Поменять местами два элемента.
        double cnt = *a;//Значение из области памяти a записать временную переменную cnt
        *a = *b;//Переписать значение по адресу b в память по адресу a
        *b = cnt;//Записать значение из временной переменной в память по адресу b.
}
/*
1. Найти максимум
2. Поменять его с первым
3. повторить 1 и 2 для элементов кроме максимального
*/
void sort(double* arr, unsigned len)
{
        swap(arr, maximum(arr,len));//Поменять текущий элемент с максимальным
        if(--len)//Уменьшить длинну на 1, и если она не стала нулевой
                sort(++arr, len);//Выполнить то же, для массива без первого элемента
}
void main()
{
        srand( time(0) );//Инициализация генератора случайных чисел
 
        const unsigned sizeOfArray = 5;
        double* arrayOfNumbers = new double[sizeOfArray];//Выделить память под массив
 
        for(int i = 0; i != sizeOfArray; ++i)
        {
                arrayOfNumbers[i] = (double) rand() / ( 1 + rand() ) * ( ( rand() % 2 ) ? -1 : 1 );
        }
 
        printArray(arrayOfNumbers, sizeOfArray);
 
        sort(arrayOfNumbers, sizeOfArray);
 
        printf("Otsortirovani massiv:\n");
        printArray(arrayOfNumbers, sizeOfArray);
 
        delete[] arrayOfNumbers;//Освобождаем память.
}
Добавлено через 3 минуты
Хоара
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
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
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
 
//При объявлении внешней функции необходимо так же указывать соответствующий тип данных принятых в векторе. 
template <typename T> void random(std::vector<T>& arr, unsigned size)
{
    arr.resize(0);
    arr.reserve(size);
 
    for (unsigned i = 0; i != size; ++i)
    {
        arr.push_back( rand() / 32767. * 20 - 10 );
    }
}
 
template <typename T> std::ostream& operator << (std::ostream& out, const std::vector<T>& arr)
{
    for (std::vector<T>::const_iterator it = arr.begin(), end = arr.end(); it != end; ++it)
    {
        out << *it << std::endl;
    }
    return out;
}
 
template <typename T> void sort (T* a, long long N)
{
    long long i = 0;
    long long j = N;
    const T p = a[ N >> 1 ];
    T temp;
 
    do
    {
        while ( a[i] < p )
        {
            ++i;
        }
        while ( a[j] > p )
        {
            --j;
        }
 
        if ( i <= j )
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            ++i;
            --j;
        }
    }
    while ( i <= j );
 
    if ( j > 0 )
    {
        sort( a,  j );
    }
 
    if ( N > i )
    {
        sort( a + i, N - i);
    }
}
 
template <typename T> inline void sort (std::vector<T>& v)
{
    sort( &v[0], v.size() - 1);
}
 
void main()
{
    srand( static_cast<unsigned int>( time(0) ) );
 
    //Теперь нужно указывать, для какого типа мы создаём экземпляр класса.
    std::vector<double> arrayOfNumbers;
 
    random(arrayOfNumbers, 23);
 
    std::cout << arrayOfNumbers;
 
    sort(arrayOfNumbers);
 
    std::cout << "Otsortirovani massiv:\n" << arrayOfNumbers;
}
Добавлено через 1 минуту
сортировка стандартной библиотеки
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
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
#include <algorithm>
 
//При объявлении внешней функции необходимо так же указывать соответствующий тип данных принятых в векторе. 
template <typename T> void random(std::vector<T>& arr, unsigned size)
{
    arr.resize(0);
    arr.reserve(size);
 
    for (unsigned i = 0; i != size; ++i)
    {
        arr.push_back( rand() / 32767. * 20 - 10 );
    }
}
 
template <typename T> std::ostream& operator << (std::ostream& out, const std::vector<T>& arr)
{
    for (std::vector<T>::const_iterator it = arr.begin(), end = arr.end(); it != end; ++it)
    {
        out << *it << std::endl;
    }
    return out;
}
 
void main()
{
    srand( static_cast<unsigned int>( time(0) ) );
 
    //Теперь нужно указывать, для какого типа мы создаём экземпляр класса.
    std::vector<double> arrayOfNumbers;
 
    random(arrayOfNumbers, 23);
 
    std::cout << arrayOfNumbers;
 
    std::sort(arrayOfNumbers.begin(), arrayOfNumbers.end(), std::less<double>() );
 
    std::cout << "Otsortirovani massiv:\n" << arrayOfNumbers;
}
Добавлено через 9 минут
С помощью стандартной реализации дерева
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
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
#include <set>
 
//При объявлении внешней функции необходимо так же указывать соответствующий тип данных принятых в векторе. 
template <typename T> void random(std::vector<T>& arr, unsigned size)
{
    arr.resize(0);
    arr.reserve(size);
 
    for (unsigned i = 0; i != size; ++i)
    {
        arr.push_back( rand() / 32767. * 20 - 10 );
    }
}
 
template <typename T> std::ostream& operator << (std::ostream& out, const std::set<T>& arr)
{
    for (std::set<T>::const_iterator it = arr.begin(), end = arr.end(); it != end; ++it)
    {
        out << *it << std::endl;
    }
    return out;
}
 
template <typename T> std::ostream& operator << (std::ostream& out, const std::vector<T>& arr)
{
    for (std::vector<T>::const_iterator it = arr.begin(), end = arr.end(); it != end; ++it)
    {
        out << *it << std::endl;
    }
    return out;
}
 
void main()
{
    srand( static_cast<unsigned int>( time(0) ) );
 
    //Теперь нужно указывать, для какого типа мы создаём экземпляр класса.
    std::vector<double> arrayOfNumbers;
 
    random(arrayOfNumbers, 23);
 
    std::cout << arrayOfNumbers << "Otsortirovani massiv:\n" << std::set<double>(arrayOfNumbers.begin(), arrayOfNumbers.end());
}
Yandex
Объявления
16.12.2011, 19:02     Сортировка
Ответ Создать тему
Опции темы

Текущее время: 13:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru