Aamir Yousafi Ответов: 2

Алгоритм быстрой сортировки грохот &амп; отладка помочь

Дорогие все,

Я застрял на коде ниже и, кажется,не могу понять, почему он продолжает падать. Предполагается, что это простой алгоритм быстрой сортировки на языке Си, но он дает мне ошибку сегментации и сбой после ввода входных данных. Я отладил его с помощью Dev C++, и он показывает, что он терпит крах при рекурсивных вызовах quicksort. Кто-нибудь может указать, где?

Кроме того, для такой программы, как эта, может ли кто-нибудь указать отладчик или метод, который поможет мне исправить это самостоятельно? У меня есть и другие подобные программы, которые мне нужно будет тестировать / практиковать, и я не хочу продолжать публиковать подобные сообщения. Заранее всем спасибо.

/* includes and macros */
// required for input / output with minGW GCC
#include <stdio.h>
#define printf __mingw_printf

// required for the random integer generator functions
#include <stdlib.h>
#include <time.h>


/* global declarations */
static unsigned short n;

/* function prototypes */
void swapSort(int *, int *);
void quickSortMid(int [], unsigned short, unsigned short);


int main()
{
    /* variable array declaration */
    printf("How many integers do you want sorted by Quick Sort? ");
    scanf("%hu", &n);
    int arrayInput[n];

    /* for rand() */
    srand(time(NULL));

    /* array input */
    printf("\n");
    for(register unsigned short i = 0; i <= n-1; i++)
        arrayInput[i] = rand();

    /* sort using the Quick Sort Medium algorithm */
    quickSortMid(arrayInput, 0, n-1);

    /* print the sorted array */
    printf("\n");
    for(register unsigned short i = 0; i <= n-1; i++)
        printf("[%d] ", arrayInput[i]);
    printf("\n");

    return 0;
}


/* function definitions */
void swapSort(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


void quickSortMid(int intArray[], unsigned short low, unsigned short high)
{
    unsigned short e = high / 2, hole = e, ul = high;
    int temp = intArray[e];
    while(low < high)
    {
        if(hole >= e)
        {
            if(intArray[low] > temp)
            {
                swapSort(&intArray[low], &intArray[hole]);
                hole = low;
            }
            else low++;
        }
        else
        {
            if(intArray[high] < temp)
            {
                swapSort(&intArray[high], &intArray[hole]);
                hole = high;
            }
            else high--;
        }
    }
    intArray[hole] = temp;

    // recursive calls of Quick Sort to completely sort the array
    if(e >= 2 && (ul-e) >= 2)
    {
        quickSortMid(intArray, 0, e-1);
        quickSortMid(intArray, e+1, ul);
    }
}


Что я уже пробовал:

Я пробовал отлаживать с помощью Dev C++ и сузил проблему до рекурсивных вызовов функции, но, похоже, не могу понять, что не так с логикой.

Скачал много разных отладчиков и много читал об отладке, но ничего такого, что помогло бы мне научиться правильно отлаживать мои собственные программы. Если бы это была простая логическая проблема, то я мог бы использовать printf, чтобы увидеть, где сортировка была неправильной и почему, но программа терпит крах.

2 Ответов

Рейтинг:
2

KarstenK

Вы можете выделить arrayinput таким образом, потому что для этого n должно быть константой.

Сделайте его динамичным, как этот код:

int *arrayInput = new int[n];
//do your stuff

//cleanup
delete arrayInput;


Совет: не смешивайте ushort и int. Это не быстрее, но приводит к странным ошибкам.

Aamir Yousafi

Спасибо. Я включу это в свою программу(программы).

Рейтинг:
15

Patrice T

Цитата:
Кроме того, для такой программы, как эта, может ли кто-нибудь указать отладчик или метод, который поможет мне исправить это самостоятельно?

Подойдет любой отладчик.
Вы знаете, что должна делать ваша программа и как должны вести себя переменные.

Вам нужно выполнить свою программу построчно на отладчике.
Проверяя переменные во время выполнения программы, вы увидите, ведут ли они себя так, как ожидалось, или нет.
там, где вы обнаружите, что программа перестает вести себя так, как ожидалось, вы близки к ошибке.
Когда у вас есть сложное выражение, которое дает неправильные результаты, рекомендуется добавить фиктивные строки, которые берут части выражения только для того, чтобы выставить промежуточный calc.

[Обновление]
когда вы запускаете программу в отладчике, вы можете запустить ее как обычно (как вы это делаете) или сказать отладчику (в меню), что вы хотите сделать один шаг в программе.
Я не знаю названия в вашем меню отладчика.
обычно у вас есть " такие имена, как step или trace
отладчик позволяет вам установить breakpoints это остановит программу каждый раз, когда она достигнет этой точки.

Aamir Yousafi

Что значит "строчка за строчкой"? Отладчик только указывает, где происходит ошибка сегментации. Как вы выполняете программу построчно с помощью отладчика?

Aamir Yousafi

спасибо