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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.71
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 13:33     Сортировки #1
Есть динамичный массив:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <ctime>
 
using namespace std;
 
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() % 9 + 1;
        cout << arr[i] << "  ";
    }   
    cout << endl;   
    delete [] arr;
    system("pause");
}
Мне надо его отсортировать 5 способами:
Insertion sort
Selection sort
Merge sort
Bubble sort
Quick sort
Уважаемые оставляйте комментарии в коде. В заранее благодарю.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 13:57     Сортировки #2
Алгоритмы сортировок
Тема разжована, пользуйтесь поиском
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 16:40  [ТС]     Сортировки #3
я понимаю алгоритмы, но не понимаю как в этом коде сделать.
panicwassano
591 / 559 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
15.11.2010, 16:51     Сортировки #4
Цитата Сообщение от Temirlan90 Посмотреть сообщение
я понимаю алгоритмы, но не понимаю как в этом коде сделать.
взять псевдокод и подставить, наверное так
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 16:55  [ТС]     Сортировки #5
я с Bubble sort пытался, но там не получалось, а вот с другим исходником вышло, поэтому и создал эту тему =)
panicwassano
591 / 559 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
15.11.2010, 17:04     Сортировки #6
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
39
#include <iostream>
#include <ctime>
 
using namespace std;
 
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() % 9 + 1;
        cout << arr[i] << "  ";
    } 
 
    char flag = true;                             // была ли замена
    while (flag){                     
        flag = false;
        for (int i = 0; i < size - 1; i++){
            if (arr[i] > arr[i + 1]){
                swap(arr[i],arr[i + 1]);   
                flag = true;                 // замена была
            }
        }
    }
 
    cout << endl; 
    for(int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    cout << endl; 
      
    delete [] arr;
    system("pause");
}
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 17:07  [ТС]     Сортировки #7
panicwassano, спасибо, осталось ещё 4 алгоритма =)
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 17:16     Сортировки #8
Функция сортировки вставками, загоняешь туда массив и размер
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InSort(double *Array, int n)
 {
      int i,j;
      double t;
      for (i=1;i<n;i++)
      {
          j = i;
          t = Array[i];
          while(j>0 && t<Array[j-1])
          {
                    Array[j] = Array[j-1];
                    j--;
          }
          Array[j] = t;
      }
 }
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 17:26  [ТС]     Сортировки #9
не хочу показаться ленивым, но у меня не выходит. Я эту функцию должен в мэйне вызывать?
panicwassano
591 / 559 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
15.11.2010, 17:32     Сортировки #10
Цитата Сообщение от Temirlan90 Посмотреть сообщение
не хочу показаться ленивым, но у меня не выходит. Я эту функцию должен в мэйне вызывать?
да, подставляя свои аргументы
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 17:36  [ТС]     Сортировки #11
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 InsertionSort(double *Array, int n) {
    int i, j;
    double t;
    for (i = 1; i < n; i++) {
        j = i;
        t = Array[i];
        while(j > 0 && t < Array[j - 1]) {
            Array[j] = Array[j - 1];
            j--;
        }
        Array[j] = t;
    }
}
 
int main() {
        setlocale(LC_ALL,"Russian");  
        srand((unsigned)time(NULL));
        int *arr;
        int size;
        int i;
        cout << "Введите размер массива: ";
        cin >> size;
        arr = new int[size];        
        cout << "Сформированый массив: ";
        for(int i = 0; i < size; i++) {
                arr[i] = rand() % 100;
                cout << arr[i] << "  ";
        }       
        double InsertionSort((arr, size));          
        cout << arr <<endl;   
        delete [] arr;
        system("pause");
}
где ошибка?
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 18:05     Сортировки #12
Так вы не вывели массив после сортировки

Добавлено через 45 секунд
C++
1
2
3
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 18:15  [ТС]     Сортировки #13
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
#include <iostream>
#include <ctime>
 
using namespace std;
 
void InsertionSort(int *Array, int n) {
    int i, j;
    double t;
    for (i = 1; i < n; i++) {
        j = i;
        t = Array[i];
        while(j > 0 && t < Array[j - 1]) {
            Array[j] = Array[j - 1];
            j--;
        }
        Array[j] = t;
    }
}
 
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] << "  ";
        }       
        int InsertionSort((arr, size));
        cout << endl;
        cout << "Отсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}
RUSya82, а что он у меня копирует массив, а не сортирует?
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 19:24     Сортировки #14
Занят был.
строка 33
C++
1
InsertionSort(arr, size)
Добавлено через 2 минуты
Все работает, я лабу по сортировкам сдавал. Пользоваться уметь надо!
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 20:52  [ТС]     Сортировки #15
Пользоваться уметь надо!
Вот 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");
}
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 21:09     Сортировки #16
quicksort - быстрая сортировка
MergeSort - сортировка слиянием

Добавлено через 1 минуту
Вот SelectionSort...
Молодец!

Добавлено через 1 минуту
Цитата Сообщение от Temirlan90 Посмотреть сообщение
криво работает =(
разбирайся:-)
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 21:15  [ТС]     Сортировки #17
Посмотрел пирамидальную сортировку и сортировку слияния. Вот их плюсы в гибридной сортировке
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.
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 21:27     Сортировки #18
Цитата Сообщение от Temirlan90 Посмотреть сообщение
все легко, когда вникнешь =)
Ну вот видишь!
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 21:28  [ТС]     Сортировки #19
Естественная сортировка:
Суть её в том, что нужно образовывать цепочки, и производить их слияние не в заранее определённом и фиксированном порядке, а анализировать имеющиеся в массиве данные.
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");
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2010, 22:30     Сортировки
Еще ссылки по теме:

Си++, Сортировки C++
Сортировки C++
C++ Сделать так, чтобы после сортировки вектора указатель показывал на тот же элемент, что и до сортировки
C++ Напишите функцию сортировки, похожую на функцию которая использовалась для сортировки массивов, с той разницей, что ее а
C++ Изменить метод "быстрой сортировки" на метод "сортировки вставками"

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

Или воспользуйтесь поиском по форуму:
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 22:30     Сортировки #20
Ну тогда для полноты картины:
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
/*Программа сортирует обменом на расстоянии, Пирамидальной сортировкой и сортировкой вставками
случайную, обратно-упорядоченную, упорядоченную и квазиупорядоченную последовательности
 вещественных чисел разных размеров. Выводит время сортировки и количество операций сравнения.
 Выполнил */
#include <iostream>
#include <conio.h>
#include <cstdlib>
#include <windows.h>
#include <cmath>
#include <iomanip>
 
using namespace std;
//----------- Функции генерации последовательностей -------------------------
void up_double( double *Array, double min, double max, int size);
void ob_up_double( double *Array, double min, double max, int size);
void rnd_double(double *Array, double max, double min, int Size);
void kvazi_double( double *Array, double min, double max, int size);
//----------- Функции сортировки ---------------------------------------
void sort_puz(double *Array, int size, int step, int l);
void ShellPuzir(double* Array, int size);
void InSort(double *Array, int n);
void piramida(double* Array,int size);
void pros (double* Array, int k, int size);
//---------------- Функция тестирования времени выполнения ---------------
void wTime (void SortFunction(double*, int), void Generate(double*, double, double, int), double* Array);
//----------------- Вспомогательные функции---------------------------
char* RUS(const char* text);
char Buf[128];
bool prov(double* Array, int size);
void obm(double& a, double& b);
bool bolshe(double a, double b);
bool menshe(double a,double b);
double z;//глобальная переменная для подсчета количества операций сравнения
 
int main()
{   
    void (*SortFunction)(double*, int);//Указатель на функцию сортировки
    void (*Generate)(double*, double, double, int);//  Указатель на функцию генерации
    int n=0, size = 250000;
    double A[250000];
    double* Array = A;
    /////////////////////   Случайная последовательность /////////////////////////////
    cout << RUS("Сортировка обменом на расстоянии случайной последовательности: ") << endl;
    SortFunction = ShellPuzir;
    Generate = rnd_double;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //---------------------------------
    cout << RUS("Пирамидальная сортировка случайной последовательности: ") << endl;
    SortFunction = piramida;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //--------------------------------
    SortFunction = InSort;
    cout << endl << RUS("Сортировка вставками случайной последовательности:  ") << endl;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    /////////// Обратно упорядоченная последовательность   //////////////////////////////
    Generate = ob_up_double;
    SortFunction = ShellPuzir;
    cout << RUS("Сортировка обменом на расстоянии обратно упорядоченной последовательности");
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";  
    //---------------------------------
    cout << RUS("Пирамидальная сортировка обратно упорядоченной последовательности: ") << endl;
    SortFunction = piramida;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //--------------------------------
    SortFunction = InSort;
    cout << endl << RUS("Сортировка вставками обратно упорядоченной последовательности:  ") << endl;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    ////////////////////////// Упорядоченная последовательность   //////////////////////
    Generate = up_double;
    SortFunction = ShellPuzir;
    cout << RUS("Сортировка обменом на расстоянии упорядоченной последовательности");
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";  
    //---------------------------------
    cout << RUS("Пирамидальная сортировка упорядоченной последовательности: ") << endl;
    SortFunction = piramida;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //--------------------------------
    SortFunction = InSort;
    cout << endl << RUS("Сортировка вставками упорядоченной последовательности:  ") << endl;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    /////////////////// Квазиупорядоченная последовательность   ///////////////////////*/
    Generate = kvazi_double;
    SortFunction = ShellPuzir;
    cout << RUS("Сортировка обменом на расстоянии квазиупорядоченной последовательности");
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";  
    //---------------------------------
    cout << RUS("Пирамидальная сортировка квазиупорядоченной последовательности: ") << endl;
    SortFunction = piramida;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //--------------------------------
    SortFunction = InSort;
    cout << endl << RUS("Сортировка вставками квазиупорядоченной последовательности:  ") << endl;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для выхода из программы нажмите любую клавишу") << endl;
    getch();
    return 0;
}
 
//////////Генерация упорядоченной последовательности ///////////////
void up_double( double *Array, double min, double max, int size)
 {
  for(int i=0;i<=size;++i)
  Array[i]=min +((max-min)/size)*i;
 }
///// Генерация последовательности случайных чисел///////////////
void rnd_double(double *Array, double max, double min, int Size)
{
    srand(time(NULL));
    for( int i = 0; i<Size; ++i)
       Array[i] = min + (max-min)*((double) rand()/RAND_MAX);
}
 
///// Генерация обратно-упорядоченной последовательности///////////
  void ob_up_double( double *Array, double min, double max, int size)
 {
  for(int i=0;i<size;++i)
  Array[i]=max -((max-min)/(size-1))*i;
 }        
 
//////////Генерация квазиупорядоченной последовательности//////////          
void kvazi_double( double *Array, double min, double max, int size)
 {
  int proc, i;
  for(i=0;i<size;++i)
    Array[i]=min +((max-min)/size)*i;
  proc = (int)ceil(0.05*size);
  srand(time(NULL));
  for (i=0; i<proc; ++i)
    Array[rand()%size] = min + (max-min)*((double) rand()/RAND_MAX);
 }
 //////Функция проверки массива на упорядоченность//////////////
bool prov(double* Array, int size)
 {
     for (int i=1;i<size;i++)
     { 
         if(Array[i]<Array[i-1])
             return false;
     }
     return true;
}
 
////////Для вывода русских букв////////////
char*RUS(const char* text)
 {
  CharToOem(text, Buf);
  return Buf;
 }
///////  Функция обмена   /////////////////
 void obm(double& a, double& b)
{    
     double temp = a;
     a = b;
     b = temp;
}
 
 /////////////Функция сортировки методом пузырька////////////////
 void sort_puz(double *Array, int size, int step, int l)
 {
     int i, j, n;
     for (i=0;i<(size-l)/step;i++)
     {
         n = 0;
         for(j=step+l;j<size;j+=step)
         {
              if (menshe(Array[j], Array[j-step]))
              { 
                     obm(Array[j],Array[j-step]);
                     n++;
              }
         }
         if(n == 0)//если при очередном проходе перестановок не было, то массив упорядочен
         break;
     }
     
 } 
 
 
 ///////////////////Функция сортировки обменом на расстоянии///////////////////
 //step[] - Массив последовательности шагов 1, 4, 9 ...
void ShellPuzir(double* Array, int size)
{
     int step[11],l;
     step[0] = 1;
     for(int i = 1;i < 11;i++)//заполнение массива шагов
        step[i] = step[i - 1]*3  + 1;
     for (int t = 10; t > 0;t--)//изменяет значение шага
        for( l = 0;l<step[t] && (step[t]+l)<size;l++)//цикл t-упорядочивает файл
           sort_puz (Array,size,step[t],l);//внутри t - файла сортируем обменом
     InSort(Array,size); //окончательная сортировка вставкими    
}
 
////////////////////////Функция сортировки вставками////////////////
void InSort(double *Array, int n)
 {
      int i,j,h=1;
      double t;
      for (i=h;i<n;i+=h)
      {
          j = i;
          t = Array[i];
          while(j>0 && menshe(t,Array[j-h]))
          {
                    Array[j] = Array[j-h];
                    j-=h;
          }
          Array[j] = t;
      }
 }
 ////////// Функция пирамидальной сортировки   //////////////////////
 void piramida(double* Array,int size)
{
     int k;
     int n = size-1;//индекс последнего элемента
     for( k = n/2;k>=0;k--)
        pros(Array,k,size);//просеиваем весь массив, a[0] - max
     while (n > 0)
     {     
           obm(Array[0], Array[n]);//ставим максимальный элемент в конец массива
           n--;//и больше его не трогаем
           pros(Array, 0, n+1);//просеиваем первый элемент
     }
}
 
/////  Функция просеивания элемента сквозь пирамиду   /////////////////
void pros (double* Array, int k, int size)
{
   int l, n = size - 1;
   while (2*k+1 <= n)
   {
         l = 2*k+1;
         if(l<n && menshe(Array[l], Array[l+1]))
         l++;                        // l - наибольший из сыновей k
         if (!(menshe(Array[k], Array[l])))//если родитель >= сын, то выходим из цикла
         break;
         obm(Array[k], Array[l]);//иначе меняем их местами
         k = l;
   }
}
 
 
 ////////// Функция тестирует и выводит на экран время выполнения функций сортировки и количество сравнений///////
void wTime (void SortFunction(double*, int), void Generate(double*, double, double, int), double* Array)
{
     SYSTEMTIME st1,st2;
     int size2[] = { 10000, 25000400005000075000100000, 150000, 200000, 250000};//массив размеров
     for(int j=0;j<9;j++)
   { 
     Generate(Array,-100000,100000,size2[j]);//генерируем последовательность
     z = 0;
     GetLocalTime(&st1);
       SortFunction(Array, size2[j]);  //сортируем
     GetLocalTime(&st2);
     double T1 = (double)(st1.wMinute*60*1000 + st1.wSecond*1000 + st1.wMilliseconds); //вычисляем время
     double T2 = (double)(st2.wMinute*60*1000 + st2.wSecond*1000 + st2.wMilliseconds);
     cout << endl << RUS("Для size = ") << size2[j] << "   \n" ;
     cout << RUS("время выполнения функции: ");
     cout << (T2 - T1) << RUS("   Миллисекунд") << endl;
     cout.setf(ios::fixed);
     cout << setprecision(0) << RUS("Количество операций сравнения: ") << z;
    if(prov(Array,size2[j]))
      cout << RUS("\nУпорядоченная") << endl;
    else
      cout << RUS("\nНеупорядоченная") << endl;
      cout << "-----------------------------------------------------------\n";
   }
}
//////// Функция "Больше" с инкрементом//////////////
bool bolshe(double a, double b)
 {
      z++;
      if (a>b)
       return true;
      else
       return false;
}
 
/////////Функция "Меньше" с инкрементом ////////////////
bool menshe(double a, double b)
 {
      z++;
      if (a<b)
       return true;
      else
       return false;
}
Yandex
Объявления
15.11.2010, 22:30     Сортировки
Ответ Создать тему
Опции темы

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