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

Merge sort - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Подскажите пожалуйста, существует ли какие либо ограничения на тип информационного поля списка? http://www.cyberforum.ru/cpp-beginners/thread972633.html
существует ли какие либо ограничения на тип информационного поля списка?
C++ Выкидывает при вводе double #include <iostream> #include <string> using namespace std; class swapall { private: int *a; double *b; string slovo; http://www.cyberforum.ru/cpp-beginners/thread972620.html
C++ Проблемы с std
Раньше работал в Вс 2005 и таких ошибок небыло.Вот перешёл на ВС 2012 и штук 40 таких ошибок выбило: d:\vs\vc\include\istream(1060): см. объявление "std::operator >>" Во код: #include <iostream> #include <conio.h> using namespace std; void main() { int i,j,a,n,x,t;
C++ Сортировка массива символов используя алгоритм сортировки "вставками" и "быструю" сортировку
Доброго времени суток! Задача ставилась следующая : заполнить массив из 3000 элементов символами, отсортировать используя алгоритмы сортировки вставками и быстрой сортировки, и замерять время выполнения программы. Я попытался реализовать следующим образом: Для сортировки вставками #include <iostream> #include <time.h> using namespace std; #define _rand(min, max) ( rand() % ((max) - (min) +...
C++ упаковка по ящикам http://www.cyberforum.ru/cpp-beginners/thread972594.html
здравствуйте, помогите пожалуйста с программой, которая будет упаковывать элементы в ящики (определенного размера) с минимальным занимаемым местом. например, последовательность элементов: 5,7,3,9,6,8,1,4,2,5 (например хранится в массиве а) Объем ящиков = 10 шаг 1. в 1 ящик кладется 5 (a)
C++ Подсчет символов в файле Дан текстовый файл, где в первой строке введено некоторое число N. Во второй строке находятся N элементов(чисел), введенных через пробелы. Помогите плиз написать прогу, которая может вывести номер символа, с которого начинается какой-нибудь m-тый элемент из этого введенного ряда. Помогите пожалуйста :) подробнее

Показать сообщение отдельно
TrueBit
95 / 95 / 12
Регистрация: 19.11.2012
Сообщений: 195
09.10.2013, 01:09     Merge sort
Почитайте Т. Кормен, Ч. Лейзер "Алгоритмы" 2005г Москва. страници 72-78. Там понятно описано.
Вообще вот код:
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
#include <iostream>
 
void merge(int * AP,int p,int q,int r) {
    int n1=q-p+1;
    int n2=r-q;
    int * L; int * R;
    L=new int[n1+1];
    R=new int[n2+1];
    for(int i=1;i<=n1; i++) {
        L[i-1]=AP[p+i-1];
    }
    for(int j=1;j<=n2; j++) {
        R[j-1]=AP[q+j];
    }
    for(int i=0,j=0,k=p; k<=r; k++) {
        if(i<n1 && j<n2) {
            if(L[i]<=R[j]) {
                AP[k]=L[i];
                i++;
            } else {
                AP[k]=R[j];
                j++;
            }
        } else if(i<n1) {
            AP[k]=L[i];
            i++;
        } else {
            AP[k]=R[j];
            j++;
        }
    }
    delete [] L; delete [] R;
}
void merge_sort(int * AP,int p,int r) {
    int q;
    if(p<r) {
        q=(p+r)/2;
        merge_sort(AP,p,q);
        merge_sort(AP,q+1,r);
        merge(AP,p,q,r);
    }
}
 
 
void print(int * A,int size) {
    for(int i=0; i<size; i++)
        printf("%d ",A[i]);
    printf("\n");
}
 
int main() {
    //int arr[] = { 4,2,7,1,23,1,23,1 };
    int arr[] = { 3,6,4,1,5,7,2,9,8,10,3,11,14,12,15,19,18,20,17,13,11 };
 
    print(arr,sizeof(arr)/sizeof(int));
    merge_sort(arr,0,sizeof(arr)/sizeof(int)-1); printf("\n");
    print(arr,sizeof(arr)/sizeof(int));
 
    getchar();
}
 
Текущее время: 10:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru