С: quicksort в следующей книге "Шаум говорится"


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

Мой код основан на примере, приведенном в этой книге.

#include <stdio.h>
#include <conio.h>
#include <math.h>

#define SIZE 12

struct StackItem
{
    int StartIndex;
    int EndIndex;
};
struct StackItem myStack[SIZE * SIZE];
int stackPointer = 0;

int myArray[SIZE] = {11,44,33,55,77,90,40,60,99,22,88,66};

void Push(struct StackItem item)
{
    myStack[stackPointer] = item;
    stackPointer++;
}

struct StackItem Pop()
{
    stackPointer--;
    return myStack[stackPointer];
}

int StackHasItem()
{
    if(stackPointer>0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

void ShowStack()
{
    int i =0;

    printf("\n");

    for(i=0; i<stackPointer ; i++)
    {
        printf("(%d, %d), ", myStack[i].StartIndex, myStack[i].EndIndex);
    }

    printf("\n");
}

void ShowArray()
{
    int i=0;

    printf("\n");

    for(i=0 ; i<SIZE ; i++)
    {
        printf("%d, ", myArray[i]);
    }

    printf("\n");
}

void Swap(int * a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int Scan(int *startIndex, int *endIndex)
{
    int partition = 0;
    int i = 0;

    if(*startIndex > *endIndex)
    {
        for(i=*startIndex ; i>=*endIndex ; i--)
        {
            if(myArray[i]<myArray[*endIndex])
            {
                Swap(&myArray[i], &myArray[*endIndex]);
                *startIndex = *endIndex;
                *endIndex = i;
                partition = i;
                break;
            }
            if(i==*endIndex)
            {
                *startIndex = *endIndex;
                *endIndex = i;
                partition = i;
            }
        }
    }
    else if(*startIndex < *endIndex)
    {
        for(i=*startIndex ; i<=*endIndex ; i++)
        {
            if(myArray[i]>myArray[*endIndex])
            {
                Swap(&myArray[i], &myArray[*endIndex]);
                *startIndex = *endIndex;
                *endIndex = i;
                partition = i;
                break;
            }
            if(i==*endIndex)
            {
                *startIndex = *endIndex;
                *endIndex = i;
                partition = i;
            }
        }
    }

    return partition;
}

int GetFinalPosition(struct StackItem item1)
{
    struct StackItem item = {0};
    int StartIndex = item1.StartIndex ;
    int EndIndex = item1.EndIndex;
    int PivotIndex = -99;

    while(StartIndex != EndIndex)
    {
        PivotIndex = Scan(&EndIndex, &StartIndex);

        printf("\n");
    }

    return PivotIndex;
}

void QuickSort()
{
    int splitPoint = 0; 
    struct StackItem item;  
    struct StackItem item1={0};
    struct StackItem item2={0};

    item.StartIndex = 0;
    item.EndIndex = SIZE-1;

    Push(item);

    while(StackHasItem())
    {
        item = Pop();

        splitPoint = GetFinalPosition(item);

        if(splitPoint>=0 && splitPoint<=(SIZE-1))
        {
            if(item.StartIndex <= (splitPoint-1))
            {
                item1.StartIndex = item.StartIndex;
                item1.EndIndex = splitPoint-1;
                Push(item1);
            }       
            if((splitPoint+1) <= item.EndIndex)
            {
                item2.StartIndex = splitPoint+1;
                item2.EndIndex = item.EndIndex;
                Push(item2);
            }
        }
    }
}

main()
{
    ShowArray();
    QuickSort();
    ShowArray();
}


392
1
задан 6 июня 2011 в 04:06 Источник Поделиться
Комментарии
5 ответов

Вы реализовали свой собственный стек. C имеет вполне хороший стек, так что не сделать свой собственный. Использовать рекурсивные функции.

"Сканирование" означает что-то искать, но вы измените список при сканировании. Его не хорошее имя для функции

"GetFinalPosition" начинается с get, который обычно указывает на функцию, ничего не изменить.

4
ответ дан 7 июня 2011 в 02:06 Источник Поделиться

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

Я бы предложил выполнении этого упражнения в рекурсивной моды сначала, так как это обычно легче, чем его итерационный аналог.

Как Уинстон уже упоминалось, имена функций-вы выбрали не правильно отражать то, что эта функция на самом деле делает. Пройти через каждый из ваших функций и постарайтесь придумать описание, которое точно описывает то, что он пытается сделать. Если вы должны использовать связке " и " в этом описании то, что функция, вероятно, имеет слишком много обязанностей.

Вот некоторые наводящие вопросы, чтобы помочь вам критиковать собственный код:


  • Есть ли дубликат настоящего Кодекса? Это включает в себя скопировать-и-вставить код с особой хитрости, чтобы получить желаемое поведение.

  • Какие предусловия, постусловия и инварианты предположить для каждой из вышеперечисленных функций?

  • Сколько каждый из ваших функций делаешь? Список и перечислить их.

  • Те вещи, связанные или не связанные друг с другом?

  • Имя функции отражают что?

  • Ваш метод push() и Pop()за манипулирует число элементов в статически выделенный стек. Что произойдет, если вы push и Pop за минимальное/максимальное диапазон допустимых?(Это относится к пункту № 2)

Наконец, книга, которую вы связаны довольно старый, если отзывы каких-либо указаний(опубликован в 1986). TCPL - обычный рекомендуемый источник для изучения программирования Си.

4
ответ дан 7 июня 2011 в 03:06 Источник Поделиться

В дополнение к тому, что другие говорили: я выбрасывал #включать как это не зависит от платформы и не нужны (как и математика.ч).

4
ответ дан 7 июня 2011 в 03:06 Источник Поделиться

Вы хотите, чтобы мы делать замечания по поводу вашего кода, но я думаю, что ваш код-это комментарии.

/* comment */

1
ответ дан 12 июня 2011 в 08:06 Источник Поделиться

Вашей тестовой программы (функции main(), ShowArray(), и т. д.) должны находиться в отдельном модуле.

В функции quicksort() функция должна быть в отдельном .файл C с интерфейсом, определенным в соответствующем .H-файл.

0
ответ дан 11 июня 2011 в 04:06 Источник Поделиться