Форум программистов, компьютерный форум, киберфорум
Наши страницы

C для начинающих

Войти
Регистрация
Восстановить пароль
 
ivanbelousov
0 / 0 / 0
Регистрация: 20.11.2014
Сообщений: 34
#1

Сортировка слиянием работает некорректно - C (СИ)

12.02.2015, 13:02. Просмотров 486. Ответов 1
Метки нет (Все метки)

Здравствуйте! Читаю Алгоритмы. Построение и анализ. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Попытался реализовать на си, но не верно. Помогите, пожалуйста!
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
#define COUNT 9
 
void merge(int *arr, int p, int q, int r)
{
    int i,j,k;
    int n1 = q - p;
    int n2 = r - q;
 
    int *larr = malloc(sizeof(int)*(n1+1));
    int *rarr = malloc(sizeof(int)*(n2+1));
    
    for( i = 0; i < n1; i++ ) 
        larr[i] = arr[p+i];
    for( j = 0; j < n2; j++ )  
        rarr[j] = arr[q+j];
    
    larr[n1] = 999999;
    rarr[n2] = 999999;
    i = 0;
    j = 0;
    
    for( k = p; k < r; k++ ) {
        if( larr[i] <= rarr[j] && i < n1 )
            arr[k] = larr[i++];
        else
            arr[k] = rarr[j++];
    }
    free(larr);
    free(rarr);
}
 
void merge_sort( int *arr, int p, int r )
{
    if( p < r ) {
        int q = (p+r)/2;
        merge_sort( arr, p, q );
        merge_sort( arr, q+1, r);
        merge(arr,p,q,r);
    }
}
 
int main( int argc, char ** argv )
{
    int i,j;
    int array[COUNT];
 
    // заполнение случайными числами
    srand(time(NULL));
 
    for( i = 0; i < COUNT; i++ ) 
        array[i] = rand()%255;
        
    // вывод массива перед сортировкой
    for( i = 0; i < COUNT; i++ )
        printf("%d ", array[i]);
    
    // сортировка
    merge_sort( array, 0, COUNT );
    
    // вывод массива после сортировки
    printf("%c",'\n');
    for( i = 0; i < COUNT; i++ )
        printf("%d ", array[i]);    
    
    return EXIT_SUCCESS;
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.02.2015, 13:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка слиянием работает некорректно (C (СИ)):

Пузырьковая сортировка работает некорректно - C (СИ)
Первая моя лаба)) Задан массив положительных чисел A. Для каждого А среди элементов массива, следующих ( по порядку) за А и больших чем...

Сортировка данных двух текстовых файлов. Счетчик количества строк работает некорректно - C (СИ)
Задача:имеется 2 файла с данными на игроков 2 команд каждая строка состоит из имени,голов,пасов,отсортировать данные этих 2 файлов так...

Сортировка слиянием - C (СИ)
Восходящая сортировка слиянием массива. Метод слияния прямой.

Сортировка слиянием - C (СИ)
Здравствуйте, у меня есть функция выполняющая сортировку слиянием. void mergesort(long num, float a) { int rght, rend; int i, j,...

Сортировка естественным слиянием - C (СИ)
Нету не у кого на примете решенной задачки? Отсортировать бинарный файл, содержащий целые числа, в порядке убывания методом естественного...

Сортировка слиянием массива из вещественных псевдослучайных чисел - C (СИ)
Подскажите, пожалуйста, почему при запуске такой программы (она сортирует слиянием массив из вещественных псевдослучайных чисел) ...

1
KolodeznyDiver
1908 / 1485 / 170
Регистрация: 01.06.2013
Сообщений: 3,096
12.02.2015, 13:41 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Исправил по быстрому, проверяйте дальше. Вроде, работает.
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
#define COUNT 9
 
void merge(int *arr, int p, int q, int r)
{
    int i,j,k;
    int n1 = q - p;
    int n2 = r - q;
    int *larr,*rarr;
 
    if(n1==0 || n2==0)
        return;
 
    larr = (int*)malloc(sizeof(int)*n1);
    rarr = (int*)malloc(sizeof(int)*n2);
 
    for( i = 0; i < n1; i++ ) 
        larr[i] = arr[p+i];
    for( j = 0; j < n2; j++ ) 
        rarr[j] = arr[q+j];
 
    i = 0;
    j = 0;
 
    for( k = p; k < r; k++ ) {
        if(j==n2 || ( i < n1 && larr[i] <= rarr[j]) )
            arr[k] = larr[i++];
        else
            arr[k] = rarr[j++];
    }
    free(larr);
    free(rarr);
}
 
void merge_sort( int *arr, int p, int r )
{
    int q;
    if( r-p > 1 ) {
        q = (p+r)/2;
        merge_sort( arr, p, q );
        merge_sort( arr, q, r);
        merge(arr,p,q,r);
    }
}
 
int main( int argc, char ** argv )
{
    int i;
    int array[COUNT];
 
    // заполнение случайными числами
    srand((unsigned)time(NULL));
 
    for( i = 0; i < COUNT; i++ ) 
        array[i] = rand()%255;
 
    // вывод массива перед сортировкой
    for( i = 0; i < COUNT; i++ )
        printf("%d ", array[i]);
 
    // сортировка
    merge_sort( array, 0, COUNT );
 
    // вывод массива после сортировки
    printf("\n");
    for( i = 0; i < COUNT; i++ )
        printf("%d ", array[i]);    
        return EXIT_SUCCESS;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2015, 13:41
Привет! Вот еще темы с ответами:

Сортировка слиянием (merge sort), ошибка в динамической аллокации - C (СИ)
Уважаемые форумчане, помогите, пожалуйста, разобраться. Задача 1 заключается в реализации сортировки слиянием (рекурсия). Тест...

Сортировка информации заданного вида сбалансированным N-ленточным слиянием - C (СИ)
задание: Осуществить программную реализацию сортировки информации заданного вида сбалансированным N-ленточным слиянием (в оперативной...

Merge sort (Сортировка слиянием) - исправить ошибки в коде - C (СИ)
Privet dami i gospoda. Ne poluchaetsa realisovat' Merge sort. Proga kompiliruetsa no sorting ne rabotaet. Help please. #include...

Сортировка информации заданного вида сбалансированным N-ленточным слиянием - C (СИ)
помогите с задачкой Осуществить программную реализацию сортировки информации заданного вида сбалансированным N-ленточным слиянием (в...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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