sort array without conditional

Question

I need a program that sorts an array of integers without using conditional statements. Numbers are in the range from 0 to 100 and don't repeat.

#include <iostream>
using namespace std;

int main() {
    int arr[] = { 34, 12, 24, 65, 63, 22 };
    int arraySize = (sizeof(arr) / sizeof(*arr));
    unsigned char buf[101] = { 0 };

    for (int k = 0; k < arraySize; k++) {
        buf[arr[k]]++;
    }

    unsigned char i = 0;
    for (int k = 0; k <= 100; k++) {
        arr[i] = k;
        i += buf[k];
    }

    for (int a : arr) {
        cout << a << endl;
    }
    system("pause");
    return 0;
}

This program works but I get the error after closing of the command prompt:

Run-Time Check Failure #2 - Stack around the variable 'arr' was corrupted.

Is there a way to fix it?

You're writing out of bounds somewhere. Use a debugger and step through the code, line by line, while keeping an eye on the variables and their values. — Some programmer dude
– Some programmer dude, Commented Apr 23, 2016 at 11:34

Sergey Kalinichenko · Accepted Answer · 2016-04-23 11:40:30Z

3

The problem is that your code writes past the end of the array. It happens after you have encountered the last element in the counted sequence, but before the array buf has been exhausted, i.e.

for (int k = 0; k <= 100; k++) {
    arr[i] = k;
    i += buf[k];
}

When you add the highest element, which is 65, to the result, i reaches 6, so assigning a[i] becomes illegal. See what's going on by adding an extra element to your array, setting it to -1, and watching what happens to it (it gets set to 100; demo 1).

You can fix it by adding an early exit condition to stop as soon as you filled the array back, i.e.

for (int k = 0; i < arraySize && k <= 100; k++) {
    arr[i] = k;
    i += buf[k];
}

Now the -1 past the end of "active" part of our array remains -1 (demo).

answered Apr 23, 2016 at 11:40

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Some programmer dude · Accepted Answer · 2016-04-23 11:40:17Z

2

The logic of the second loop is wrong. You have six numbers in arr, no doubles, which means that a total of six elements in buf will be set to 1.

That means that after a while, the value of i will be 6, which you then use as an index into arr, but index 6 is the seventh element in an array, leading you to write out of bounds.

answered Apr 23, 2016 at 11:40

Some programmer dude

411k36 gold badges420 silver badges655 bronze badges

Collectives™ on Stack Overflow

sort array without conditional

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related