quick Sort

[kendell]

hay i need some help here i am trying to do a quick sort this is the code i have and i am getting some errors i do not understand.
this is the definition

void quickSort(int numbers[], int first, int last)
{
int i, pivot, left, right, mid;
int passes = last - first;
if (passes > 0)
{
if (numbers[first] > numbers[last])
swap(&numbers[first], &numbers[last]);
if (passes > 1)
{
for (i = first + 1; i < last; i++)
{
if (numbers[i] < numbers[first])
swap(numbers[i], &numbers[first]);
else if (numbers[i] > numbers[last])
swap (&numbers[i], &numbers[last]);
}
if (passes > 2)
{
mid = (numbers[first] + numbers[last]) / 2;
pivot = numbers[first + 1];

for (i = first + 2; i < last; i++)
{
if (abs(numbers[i] - mid) < abs(pivot - mid))
pivot = numbers[i];
}
left = first + 1;
right = last - 1;
while (left < right)
{
while(numbers < pivot)
left++;
while (numbers > pivot)
right--;
if (left < right)
swap(&numbers, &numbers);
if (numbers == pivot && numbers == pivot)
left++;
}
quickSort(numbers, first + 1, right - 1);
quickSort(numbers, right + 1, last - 1);
}
}
}

[Ancient Dragon]

what are the errors?

[kendell]

can some one please help me? I am trying to find a best case, worst case and average case in a sorting function. I have no idea how to go about doing that, can some one please help me?

[Ancient Dragon]

I reformatted your code so that I could read it. Your compiler should have produced errors on lines 35 and 37 because variable numbers is an array, not a single integer. Correct all the compile errors before attempting to go on with the assignment.

#include<stdio.h> 
#include <stdlib.h>

void quickSort(int numbers[], int first, int last)
{
    int i, pivot, left, right, mid;
    int passes = last - first;
    if (passes > 0)
    {
        if (numbers[first] > numbers[last])
            swap(&numbers[first], &numbers[last]);
        if (passes > 1)
        {
            for (i = first + 1; i < last; i++)
            {
                if (numbers[i] < numbers[first])
                    swap(numbers[i], &numbers[first]);
                else if (numbers[i] > numbers[last])
                    swap (&numbers[i], &numbers[last]);
            }
            if (passes > 2)
            { 
                mid = (numbers[first] + numbers[last]) / 2;
                pivot = numbers[first + 1];

                for (i = first + 2; i < last; i++)
                {
                    if (abs(numbers[i] - mid) < abs(pivot - mid))
                        pivot = numbers[i];
                }
                left = first + 1;
                right = last - 1;
                while (left < right)
                {
                    while(numbers < pivot)
                        left++;
                    while (numbers > pivot)
                        right--;
                    if (left < right)
                        swap(&numbers, &numbers);
                    if (numbers == pivot && numbers == pivot)
                        left++;
                }
                quickSort(numbers, first + 1, right - 1);
                quickSort(numbers, right + 1, last - 1);
            }
        }
    }
}

[Ancient Dragon]

can some one please help me? I am trying to find a best case, worst case and average case in a sorting function. I have no idea how to go about doing that, can some one please help me?

I think you will need several different sort algorithms, such as compare bubble sort with quick sort and several others. You have to code each sort algorithm then run the same set of data through each sort method, placing timers before and after to get the amount of time it takes for the algorithm to sort the data. Because computers do their work so quickly you will have to run each sort algorithm 1,000 or more times and to get measurable amount of time. Here's an example

clock_t startTime, endTime, deltaTime;

// time the bubble sort algorithm
startTime = clock(); // start the timer
for(int i = 0; i < 10000; i++)
     DoBubbleSort( <parameters here> );
endTime = clock(); // end the timer
deltaTime = endTime - startTime;
printf("Bubble sort took %u time\n", deltaTime);

now do each of the other algorithms the same way

[iamthwee]

No, I think he/she wants a big 'O' explanation, running code proves nothing.

[Ancient Dragon]

Oh, then I'd suggest reading this I really don't know that much about it either, never had the occasion to use it.

[kendell]

hay thank you. another question, how can i test to see if a sort function is already sorted?

[Ancient Dragon]

you mean if the data is already sorted, not the sort function. :)

You have to iterate through the array and check if any element is not in order.