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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Шаблон http://www.cyberforum.ru/cpp-beginners/thread191476.html
Всем доброе время суток)) Вот нпаисал прогу: #include <string.h> #include <iostream> using namespace std; template<class T> class List{ private: struct Element{
C++ Дано число n. Найти сумму n-значных чисел Кто может решит такую задачу. Дано число n. Найти сумму n-значных чисел. Ограничениа 0<n<=100. Хочу сказать что эту задачу я решил, просто интересно кто кокой алгоритм придложет. http://www.cyberforum.ru/cpp-beginners/thread191461.html
C++ Удаление узла бинарного дерева
всем привет.вот есть у меня бинарное дерево тока фун-ии добавления и обхода.очень нужно удалени помогите плиз. .cpp #include <iostream> using namespace std; #include "TreeNode.h" int main(void) { TreeNode ob(3); ob.AddElement(5);
C++ Это массив?
static int attrListSgl = {GLX_RGBA, GLX_RED_SIZE, 4, GLX_GREEN_SIZE, 4, GLX_BLUE_SIZE, 4, GLX_DEPTH_SIZE, 16, None}; Это массив?
C++ Что это структура? http://www.cyberforum.ru/cpp-beginners/thread191425.html
#include<stdio.h> #include<stdlib.h> #include<X11/X.h> #include<X11/Xlib.h> #include<GL/gl.h> #include<GL/glx.h> #include<GL/glu.h> Display *dpy; Window root;
C++ delete или new (typeid(void*))(void*) Доброе время суток. Пишу список. Телом каждого элемента (el) списка является void указатель(body). (предполагается что тело элемента может быть любого типа, т.е. переменные, классы, другой такой же список и т.д.) Критерий - универсальность и скорость. У меня получилось что-то типа (*el).body = new typeid(NewType); где NewType - параметр функции, void * на какую либо известную переменную... подробнее

Показать сообщение отдельно
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 21:15  [ТС]     Сортировки
Посмотрел пирамидальную сортировку и сортировку слияния. Вот их плюсы в гибридной сортировке
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <ctime>
 
using namespace std;
 
void Merge(int const *const A, int const nA,
            int const *const B, int const nB,
            int *const C) { //Выполнить слияние массива A, содержащего nA элементов,
                            //  и массива B, содержащего nB элементов.
                            //  Результат записать в массив C.
                int a(0), b(0); //Номера текущих элементов в массивах A и B
                while( a + b < nA + nB ) { //Пока остались элементы в массивах
                    if( (b >= nB) || ( (a < nA) && (A[a] <= B[b]) ) ) { //Копирую элемент из массива A
                        C[a + b] = A[a];
                        a++;
                    } 
                    else { //Копирую элемент из массива B
                        C[a + b] = B[b];
                        b++;
                    }
                }
}
 
void SiftDown(int* const heap, int i, int const n) {   
    //Просеивает элемент номер i вниз в пирамиде heap.
    //n -- размер пирамиды
    //Идея в том, что вычисляется максимальный элемент из трёх:
    //  1) текущий элемент
    //  2) левый потомок
    //  3) правый потомок
    //Если индекс текущего элемента не равен индексу максималь-
    //  ного, то меняю их местами, и перехожу к максимальному
    //Индекс максимального элемента в текущей тройке элементов:
    int nMax(i);
    //Значение текущего элемента (не меняется):
    int const value(heap[i]);
    while (true) { 
        //Рассматривается элемент i и его потомки i*2+1 и i*2+2
        //В начале каждой итерации nMax == i и value == heap[i]
        int childN(i * 2 + 1); //Индекс левого потомка
        //Если есть левый потомок и он больше текущего элемента,
        if ((childN < n) && (heap[childN] > value))
            nMax = childN; //  то он считается максимальным
            ++childN; //Индекс правого потомка
            //Если есть правый потомок и он больше максимального,
            if ((childN < n) && (heap[childN] > heap[nMax]))
                nMax = childN; //  то он считается максимальным
            //Если текущий элемент является максимальным из трёх
            //  (т.е. если он больше своих детей), то конец:
            if (nMax == i) break;
            //Меняю местами текущий элемент с максимальным:
            heap[i] = heap[nMax]; heap[nMax] = value;
            //  при этом значение value будет в ячейке nMax,
            //  поэтому в начале следующей итерации значение value
            //  правильно, т.к. мы переходим именно к этой ячейке
            //Переходим к изменившемуся потомку
            i = nMax;
    }
}
 
void HeapSort(int* const heap, int n) {   //Пирамидальная сортировка массива heap.
    //  n -- размер массива 
    //Этап 1: построение пирамиды из массива
    for(int i(n / 2 - 1); i >= 0; --i) SiftDown(heap, i, n);
    //Этап 2: сортировка с помощью пирамиды.
    //Здесь под «n» понимается размер пирамиды
    while(n > 1) { //Пока в пирамиде больше одного элемента
        --n; //Отделяю последний элемент
        //Меняю местами корневой элемент и отделённый:
        int const firstElem(heap[0]);
        heap[0] = heap[n];
        heap[n] = firstElem;
        //Просеиваю новый корневой элемент:
        SiftDown(heap, 0, n);
    }
}
 
void HybridSort(int *&A, int n) { 
    //Отсортировать массив A, содержащий n элементов.
    //При работе указатель на A, возможно, меняется.
    //(Функция получает ссылку на указатель на A)   
    //Размер кусочка для сортировки пирамидой:
    //(нужно подбирать для максимального ускорения)
    int const tileSize(4096);
    for(int start(0); start < n; start += tileSize)
        HeapSort(A + start, min(tileSize, n - start));
    if(n <= tileSize) return; //Больше сортировать не нужно
    int *B(new int[n]); //Временный буфер памяти
    for(int size(tileSize); size < n; size *= 2) { 
        //Перебираем размеры кусочков для слияния,
        //  начиная с tileSize элементов
        int start(0); //Начало первого кусочка пары
        for(;(start + size) < n; start += size * 2) {
            //Перебираем все пары кусочков, и выполняем попарное
            //  слияние. (start+size)<n означает, что начало
            //  следующего кусочка лежит внутри массива
            Merge(A + start, size, A + start + size, min(size, n - start - size), B + start);
        }
        //Если последний кусочек остался без пары, просто копируем
        //его из A в B:
        for(; start < n; start++) B[start] = A[start];
        int *temp(B); B = A; A = temp; //Меняем местами указатели
    }
    delete[n] B; //Удаляем временный буфер
}
 
int main() {
        setlocale(LC_ALL,"Russian");  
        srand((unsigned)time(NULL));
        int *arr;
        int size;       
        cout << "Введите размер массива: ";
        cin >> size;
        arr = new int[size];        
        cout << "Сформированый массив: ";
        for(int i = 0; i < size; i++) {
                arr[i] = rand() % 100;
                cout << arr[i] << "  ";
        } 
        cout << endl;
        HybridSort(arr, size);      
        cout << "\nОтсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}
все легко, когда вникнешь =) Кстати эту сортировку можно бы и добавить в FAQ.
 
Текущее время: 13:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru