0

I ambitiously decided to try the more comfortable version of this task, although I'm very much "less comfortable" with regard to any computer skills... Before I give up, I'd like to ask you what's wrong with my code.

Search:

bool search(int value, int values[], int n)
{
int first = 0;
int last = n-1;

while (first <= last)
{
    int middle = (first + last)/2;

    if (values[middle] > value) 
    {
        //if the middle value is bigger than the value we're looking for, search left half of array
        last = middle - 1;
    }
    else if (values[middle] < value) 
    {
        //if the middle value is smaller than the value we're looking for, search right half of array
        first = middle + 1;
    }  
    else 
    {
        //if the middle value = value we're looking for, return true
        return true;    
    }

}
return false;
}

Counting sort:

void sort(int values[], int n)
{

//new helper arrays
int count[65536];
int output[n];

//for every element in values increment the index in count equal to that element by 1
for (int i = 0; i < n; i++)
{
  count[values[i]]++;
}

//add up the values in count
for (int i = 0; i < 65536; i++)
{
  count[i+1] = count[i+1] + count[i];
}

//for every element in values, place it in the output index equal to the corresponding value in count
for (int i = 0; i < n; i++)
{
  output[i] = count[values[i]];
  count[values[i]]--;
}

//transfer the outcome to the initial array
for (int i = 0; i < n; i++)
{
  values[i] = output[i];
}

return;
}

Debug50 returned this:

child exited status 255

Check50 said this:

check50 results

0

count is not initialised, may contain any data. Use something like int count[65536] = {0}; to initialise the array.

I understand your initial counting loop. After that, it gets confusing.

Loop

for (int i = 0; i < 65536; i++)

is looping one too far if you're accessing count[i+1], use i < 65535 instead, otherwise you write to an element outside the array.

You don't need an extra array output that you later copy to values if you're just looping over count and write count's index a number of times back into values.

But I think I get what you meant, and that requires an extra copy.

Instead of

output[j] = count[values[i]];
count[values[i]]--;

which assigns a number of occurences of a value to an array meant to contain values instead, I'd try something like

output[--count[values[i]]] = values[i];

Note that I used --count[values[i]], which evaluates to the value after decrementing, while count[values[i]]-- evaluates to the value before decrementing. Both decrement, so if you're not using the value, they are about the same.

1
  • Thank you, it works now :) Mar 24 '17 at 16:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .