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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.71
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
#1

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

15.11.2010, 13:33. Просмотров 2126. Ответов 27
Метки нет (Все метки)

Есть динамичный массив:
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
Уважаемые оставляйте комментарии в коде. В заранее благодарю.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2010, 13:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировки (C++):

Составить блок – схемы для шейкер- сортировки и сортировки Шелла - C++
Доброго времени суток, очень нужна ваша помощь в решении данной проблемы, буду бесконечно благодарен. Составить блок – схемы для шейкер-...

Пример быстрой сортировки массива строк и сортировки методом выбора - C++
Добрый вечер. Скиньте пожалуйста пример быстрой сортировки массива строк и сортировки массива строк методом выбора. Очень срочно надо,...

Составить программы для пузырьковой сортировки и сортировки посредством выбора с применением оператора while - C++
Доброго времени суток, очень нужна ваша помощь в решении данной проблемы, буду бесконечно благодарен. Составить программы для пузырьковой...

Сделать так, чтобы после сортировки вектора указатель показывал на тот же элемент, что и до сортировки - C++
Есть вектор(STL) элементов. У меня есть указатель на определенный элемент. Я хочу сделать так, чтобы после сортировки этого вектора...

Напишите функцию сортировки, похожую на функцию которая использовалась для сортировки массивов, с той разницей, что ее а - C++
Напишите функцию сортировки, похожую на функцию которая использовалась для сортировки массивов, с той разницей, что ее аргументом должен...

Изменить метод "быстрой сортировки" на метод "сортировки вставками" - C++
Как изменить метод &quot;интеративной быстрой сортировки&quot; на метод &quot;сортировки вставками «с конца массива»&quot;? Нужно изменить только метод...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 13:57 #2
Алгоритмы сортировок
Тема разжована, пользуйтесь поиском
Temirlan90
132 / 132 / 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
132 / 132 / 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
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 17:07  [ТС] #7
panicwassano, спасибо, осталось ещё 4 алгоритма =)
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
132 / 132 / 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
132 / 132 / 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
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
132 / 132 / 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
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 19:24 #14
Занят был.
строка 33
C++
1
InsertionSort(arr, size)
Добавлено через 2 минуты
Все работает, я лабу по сортировкам сдавал. Пользоваться уметь надо!
Temirlan90
132 / 132 / 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");
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2010, 20:52
Привет! Вот еще темы с ответами:

Си++, Сортировки - C++
Написать программу, осуществляющую блочную сортировку одномерного массива

Сортировки С++ - C++
Всем доброго времени суток! Не могу понять в чем ошибка,прошу помочь. вот условие задачи: В текстовом файле содержатся записи о...

сортировки - C++
народ помогите нужны программки для 1)сортировки прямым выбором(по убыванию 5&gt;3&gt;1) 2)сортировка двоичной вставкой(по возрастанию 1&lt;3&lt;5)...

Сортировки? - C++
На экзамене нам дали такое задание &quot;Написать функцию сортировки вектора строк.&quot; Подскажите как можно решить эту программу если мы...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.11.2010, 20:52
Ответ Создать тему
Опции темы

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