Форум программистов, компьютерный форум 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, 20:52  [ТС]     Сортировки
Пользоваться уметь надо!
Вот SelectionSort
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
#include <iostream>
#include <ctime>
 
using namespace std;
 
void SelectionSort(int Array[], int size) {
    int i, j, k, x;
    for( i = 0; i < size; i++) { // i - номер текущего шага
        k = i; x = Array[i];
        for( j = i + 1; j < size; j++) // цикл выбора наименьшего элемента
            if ( Array[j] < x ) {
                k = j; x = Array[j]; // k - индекс наименьшего элемента
            }
            Array[k] = Array[i]; Array[i] = x; // меняем местами наименьший с a[i]
    }
}
 
 
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;
        SelectionSort(arr, size);       
        cout << "\nОтсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}
BubbleSort
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
#include <iostream>
#include <ctime>
 
using namespace std;
 
void BubbleSort(int Array[], int size) {
    int i, j, x;
    for(i = 0; i < size; i++) {  // i - номер прохода
        for( j = size - 1; j > i; j-- ) {  // внутренний цикл прохода
            if ( Array[j - 1] > Array[j] ) {
                x = Array[j - 1]; Array[j - 1] = Array[j]; Array[j] = x;
            }
        }
    }
}
 
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;
        BubbleSort(arr, size);      
        cout << "\nОтсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}


RUSya82, последний вопрос, где в той ссылке что вы дали MergeSort и QuickSort? На русском как будет?
QuickSort
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
#include <iostream>
#include <ctime>
 
using namespace std;
 
void QuickSort(int *a, int N) {
// На входе - массив a[], a[N] - его последний элемент.
 
  int i = 0, j = N;            // поставить указатели на исходные места
  int temp, p;
 
  p = a[ N>>1 ];                // центральный элемент
 
  // процедура разделения
  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 ) QuickSort(a, j);
  if ( N > i ) QuickSort(a+i, N-i);
}
 
 
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;
        QuickSort(arr, size);       
        cout << "\nОтсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}
криво работает =(

Добавлено через 10 минут
QuickSort
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
#include <iostream>
#include <ctime>
 
using namespace std;
 
#define MAXSTACK 2048 // максимальный размер стека
 
void qSortI(int a[], long size) {
 
long i, j; // указатели, участвующие в разделении
long lb, ub; // границы сортируемого в цикле фрагмента
 
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
int pivot; // опорный элемент
int temp;
 
lbstack[1] = 0;
ubstack[1] = size-1;
 
do {
// Взять границы lb и ub текущего массива из стека.
lb = lbstack[ stackpos ];
ub = ubstack[ stackpos ];
stackpos--;
 
do {
// Шаг 1. Разделение по элементу pivot
ppos = ( lb + ub ) >> 1;
i = lb; j = ub; pivot = a[ppos];
do {
while ( a[i] < pivot ) i++;
while ( pivot < a[j] ) j--;
if ( i <= j ) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i <= j );
 
// Сейчас указатель i указывает на начало правого подмассива,
// j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
// Возможен случай, когда указатель i или j выходит за границу массива
 
// Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub
if ( i < ppos ) { // правая часть больше
if ( i < ub ) { // если в ней больше 1 элемента - нужно
stackpos++; // сортировать, запрос в стек
lbstack[ stackpos ] = i;
ubstack[ stackpos ] = ub;
}
ub = j; // следующая итерация разделения
// будет работать с левой частью
} else { // левая часть больше
if ( j > lb ) {
stackpos++;
lbstack[ stackpos ] = lb;
ubstack[ stackpos ] = j;
}
lb = i;
}
} while ( lb < ub ); // пока в меньшей части более 1 элемента
} while ( stackpos != 0 ); // пока есть запросы в стеке
}
 
 
 
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;
        qSortI(arr, size);      
        cout << "\nОтсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}
:dance3:
MergeSort не могу понять какой именно.

Добавлено через 46 минут
MergeSort
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
#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 MergeSort(int *A, int n) { //Отсортировать массив A, содержащий n элементов
    if( n < 2 ) return; //Сортировка не нужна
    if( n == 2 ) {  //Два элемента проще поменять местами,
                    //  если нужно, чем делать слияние
        if( A[0] > A[1] ) { int t(A[0]); A[0] = A[1]; A[1] = t; 
        }
        return;
    }
    MergeSort(A, n / 2); //Сортируем первую половину
    MergeSort(A + n / 2, n - n / 2); //Сортируем вторую половину
    int *B( new int[n] ); //Сюда запишем результат слияния
    Merge(A, n / 2, A + n / 2, n - n / 2, B); //Слияние половин
    //Копирование результата слияния в исходный массив:
    for(int i(0); i < n; i++) A[i] = B[i];
    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;
        MergeSort(arr, size);       
        cout << "\nОтсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}
 
Текущее время: 20:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru