Форум программистов, компьютерный форум 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...
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
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 21:28  [ТС]
Естественная сортировка:
Суть её в том, что нужно образовывать цепочки, и производить их слияние не в заранее определённом и фиксированном порядке, а анализировать имеющиеся в массиве данные.
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
#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 NaturalSort(int *&A, int  n) { 
    //Отсортировать массив A, содержащий n элементов.
    //При работе указатель на A, возможно, меняется.
    //(Функция получает ссылку на указатель на A)
    int *B(new int[n]); //Временный буфер памяти
    while(true) {
        //Выполняем слияния, пока не останется один
        //отсортированный участок. Выход из цикла
        //находится дальше
        int start1, end1; //Первый отсортированный участок
        int start2(-1), end2(-1); //Второй отсортированный участок
        while(true) { 
            //Цикл по всем парам отсортированных участков в массиве           
            //Начало первого участка для слияния находится после
            //конца второго участка предыдущей пары:
            start1 = end2 + 1; end1 = start1;
            //Двигаемся вправо до нарушения сортировки:
            while((end1 < n - 1) && (A[end1] <= A[end1 + 1])) end1++;
            //Первый участок пары простирается до конца массива:
            if(end1 == n - 1) break;           
            //Начало второго участка для слияния находится после
            //конца первого участка текущей пары:
            start2 = end1 + 1, end2 = start2;       
            //Двигаемся вправо до нарушения сортировки:
            while((end2 < n - 1) && (A[end2] <= A[end2 + 1])) end2++;
            //Выполняем слияние двух отсортированных участков
            Merge(A + start1, end1 - start1 + 1,
                    A + start2, end2 - start2 + 1,
                    B + start1);
            //Второй участок пары простирается до конца массива:
            if(end2 == n - 1) break;
        }
        //Данные полностью отсортированы и находятся в массиве A:
        if(( start1 == 0) && (end1 == n - 1)) break;       
        //Если последний кусочек остался без пары, просто копируем
        //его из A в B:
        if(end1 == n - 1) {
            for(; start1 < n; start1++) B[start1] = A[start1];
        }
        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;
        NaturalSort(arr, size);     
        cout << "\nОтсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}
2
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru