Форум программистов, компьютерный форум, киберфорум
Наши страницы

Сортировки - 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...
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 ...
C++ delete или new (typeid(void*))(void*) Доброе время суток. Пишу список. Телом каждого элемента (el) списка является void указатель(body). (предполагается что тело элемента может быть любого типа, т.е. переменные, классы, другой такой же... подробнее

Показать сообщение отдельно
Temirlan90
133 / 133 / 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.
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru