#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
void countingsort(char *str)
{
int count[256];
int i;
char output[20];
memset(count,0,256);
for(i=0;str[i];i++)
++count[str[i]];
for(i=1;i<256;i++)
count[i]+=count[i-1];
for(i=0;str[i];i++)
output[--count[str[i]]]=str[i];
for(i=0;str[i];i++)
str[i]=output[i];
}
int main()
{
char str[]="123ab78bj45ui";
countingsort(str);
printf("%s",str);
getch();
return 0;
}
I dont know where the problem is. I think i am doing right but on runtime it is giving this error "Unhandled exception at 0x013814f5 in countingsort.exe: 0xC0000005: Access violation writing location 0x33562813.". Can anyone suggest where i am going wrong.
Even when the code is cleaned up in presentation:
#include <stdio.h>
#include <string.h>
void countingsort(char *str);
void countingsort(char *str)
{
int count[256];
int i;
char output[20];
memset(count, 0, 256);
for (i = 0; str[i]; i++)
++count[str[i]];
for (i = 1; i < 256; i++)
count[i] += count[i-1];
for (i = 0; str[i]; i++)
output[--count[str[i]]] = str[i];
for (i = 0; str[i]; i++)
str[i] = output[i];
}
int main(void)
{
char str[] = "123ab78bj45ui";
countingsort(str);
printf("%s\n", str);
return 0;
}
GCC 4.8.1 gives warnings which the -Werror option turns into errors:
$ gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition -Werror cs.c -o cs
cs.c: In function ‘countingsort’:
cs.c:13:9: error: array subscript has type ‘char’ [-Werror=char-subscripts]
++count[str[i]];
^
cs.c:17:9: error: array subscript has type ‘char’ [-Werror=char-subscripts]
output[--count[str[i]]] = str[i];
^
cc1: all warnings being treated as errors
$
However that only begins to cover the problems:
The memset() zeroes a quarter of the array, leaving the rest containing garbage.
memset(count, '\0', sizeof(count));
The indexing by possibly signed characters means you could be accessing elements -128..-1 of the array. That's why the compiler warns about character subscripts. Given your data, that isn't your problem,
The second for loop is adding up all sorts of garbage (because of the memset() problem).
The third loop scares me witless; I have no idea what it is trying to do, but it is guaranteed not to be doing what you think because of the memset() problems.
With debug code in situ as shown and the primary problems fixed, the code looks like:
#include <stdio.h>
#include <string.h>
void countingsort(char *str);
void countingsort(char *str)
{
int count[256];
int i;
char output[20];
memset(count, '\0', sizeof(count));
for (i = 0; str[i]; i++)
++count[(unsigned char)str[i]];
for (i = 1; i < 256; i++)
count[i] += count[i-1];
/* Debug */
for (i = 0; i < 256; i++)
{
printf(" %3d: %2d", i, count[i]);
if (i % 8 == 7)
putchar('\n');
}
for (i = 0; str[i]; i++)
output[--count[(unsigned char)str[i]]] = str[i];
for (i = 0; str[i]; i++)
str[i] = output[i];
}
int main(void)
{
char str[] = "123ab78bj45ui";
printf("Before: <<%s>>\n", str);
countingsort(str);
printf("%s\n", str);
return 0;
}
And the output, apparently under full control, is:
Before: <<123ab78bj45ui>>
0: 0 1: 0 2: 0 3: 0 4: 0 5: 0 6: 0 7: 0
8: 0 9: 0 10: 0 11: 0 12: 0 13: 0 14: 0 15: 0
16: 0 17: 0 18: 0 19: 0 20: 0 21: 0 22: 0 23: 0
24: 0 25: 0 26: 0 27: 0 28: 0 29: 0 30: 0 31: 0
32: 0 33: 0 34: 0 35: 0 36: 0 37: 0 38: 0 39: 0
40: 0 41: 0 42: 0 43: 0 44: 0 45: 0 46: 0 47: 0
48: 0 49: 1 50: 2 51: 3 52: 4 53: 5 54: 5 55: 6
56: 7 57: 7 58: 7 59: 7 60: 7 61: 7 62: 7 63: 7
64: 7 65: 7 66: 7 67: 7 68: 7 69: 7 70: 7 71: 7
72: 7 73: 7 74: 7 75: 7 76: 7 77: 7 78: 7 79: 7
80: 7 81: 7 82: 7 83: 7 84: 7 85: 7 86: 7 87: 7
88: 7 89: 7 90: 7 91: 7 92: 7 93: 7 94: 7 95: 7
96: 7 97: 8 98: 10 99: 10 100: 10 101: 10 102: 10 103: 10
104: 10 105: 11 106: 12 107: 12 108: 12 109: 12 110: 12 111: 12
112: 12 113: 12 114: 12 115: 12 116: 12 117: 13 118: 13 119: 13
120: 13 121: 13 122: 13 123: 13 124: 13 125: 13 126: 13 127: 13
128: 13 129: 13 130: 13 131: 13 132: 13 133: 13 134: 13 135: 13
136: 13 137: 13 138: 13 139: 13 140: 13 141: 13 142: 13 143: 13
144: 13 145: 13 146: 13 147: 13 148: 13 149: 13 150: 13 151: 13
152: 13 153: 13 154: 13 155: 13 156: 13 157: 13 158: 13 159: 13
160: 13 161: 13 162: 13 163: 13 164: 13 165: 13 166: 13 167: 13
168: 13 169: 13 170: 13 171: 13 172: 13 173: 13 174: 13 175: 13
176: 13 177: 13 178: 13 179: 13 180: 13 181: 13 182: 13 183: 13
184: 13 185: 13 186: 13 187: 13 188: 13 189: 13 190: 13 191: 13
192: 13 193: 13 194: 13 195: 13 196: 13 197: 13 198: 13 199: 13
200: 13 201: 13 202: 13 203: 13 204: 13 205: 13 206: 13 207: 13
208: 13 209: 13 210: 13 211: 13 212: 13 213: 13 214: 13 215: 13
216: 13 217: 13 218: 13 219: 13 220: 13 221: 13 222: 13 223: 13
224: 13 225: 13 226: 13 227: 13 228: 13 229: 13 230: 13 231: 13
232: 13 233: 13 234: 13 235: 13 236: 13 237: 13 238: 13 239: 13
240: 13 241: 13 242: 13 243: 13 244: 13 245: 13 246: 13 247: 13
248: 13 249: 13 250: 13 251: 13 252: 13 253: 13 254: 13 255: 13
1234578abbiju
Note how I added debug printing. If you'd done that with the original code, you might have seen the problem with the numbers:
Before: <<123ab78bj45ui>>
0: 0 1: 0 2: 0 3: 0 4: 0 5: 0 6: 0 7: 0
8: 0 9: 0 10: 0 11: 0 12: 0 13: 0 14: 0 15: 0
16: 0 17: 0 18: 0 19: 0 20: 0 21: 0 22: 0 23: 0
24: 0 25: 0 26: 0 27: 0 28: 0 29: 0 30: 0 31: 0
32: 0 33: 0 34: 0 35: 0 36: 0 37: 0 38: 0 39: 0
40: 0 41: 0 42: 0 43: 0 44: 0 45: 0 46: 0 47: 0
48: 0 49: 1 50: 2 51: 3 52: 4 53: 5 54: 5 55: 6
56: 7 57: 7 58: 7 59: 7 60: 7 61: 7 62: 7 63: 7
64: 8 65: 8 66: 176754732 67: 176754733 68: 1606423245 69: 1606456012 70: -843336874 71: -843304107
72: 586364677 73: 586364678 74: -1863248202 75: -1863215435 76: -17897627 77: -17864860 78: 1827489556 79: 1827522323
80: -622127165 81: -622094398 82: -622094397 83: -622094397 84: 1223223411 85: 1223256178 86: -1226364830 87: -1226332063
88: 203336529 89: 203369296 90: 2048543985 91: 2048576752 92: -401072736 93: -401039969 94: 1444306319 95: 1444339086
96: -1005310402 97: -1005277634 98: -1005277631 99: -1005277631 100: -828522907 101: -828522906 102: 601145878 103: 601178645
104: 2030847317 105: 2030880085 106: -418887751 107: -418854984 108: 1010813800 109: 1010846567 110: 1010846567 111: 1010846567
112: 1010846567 113: 1010846568 114: 1010846569 115: 1010846569 116: 1187601337 117: 1187601339 118: 1364356072 119: 1364356073
120: 1541106681 121: 1541106682 122: -908514326 123: -908481559 124: 521187273 125: 521220040 126: -1508757392 127: -1508724625
128: -658678769 129: -658678769 130: -658678747 131: -658678747 132: 770990005 133: 771022772 134: -1258953635 135: -1258920868
136: -1258920868 137: -1258920868 138: 170748016 139: 170780783 140: 1600449663 141: 1600482430 142: 1600482430 143: 1600482430
144: -1264815990 145: -1264783223 146: 655242917 147: 655275684 148: 659367534 149: 659367534 150: 659367534 151: 659367790
152: -1715573370 153: -1715540603 154: -1699052283 155: -1699043995 156: 220982117 157: 221014884 158: 2141040460 159: 2141073227
160: -233871253 161: -233838486 162: -233838486 163: -233838486 164: 1686187626 165: 1686220393 166: 1686220393 167: 1686220393
168: -1179077991 169: -1179045224 170: 1085946763 171: 1085979530 172: 970946174 173: 215978496 174: 2136004072 175: 2136012360
176: 2136012616 177: 2136012872 178: -238928848 179: -238896081 180: -238896055 181: -238896055 182: -62145647 183: -62145646
184: 1367523314 185: 1367556081 186: -580781114 187: -580748347 188: 1339277229 189: 1339309996 190: 1339309996 191: 1339309996
192: 1516060404 193: 1516060405 194: -858852619 195: -858819852 196: 570849364 197: 570882131 198: -1377463709 199: -1377430942
200: -1377430942 201: -1377430942 202: 52238290 203: 52271057 204: 1481940361 205: 1481973128 206: -1383324432 207: -1383291665
208: -1383291665 209: -1383291665 210: 46373871 211: 46406638 212: 46406638 213: 46406638 214: 46406638 215: 46406638
216: 871518564 217: 1663205276 218: -1651447554 219: 268721709 220: 268721709 221: 268721709 222: 268721709 223: 268721709
224: 1936968284 225: -710723907 226: 81634598 227: 877664411 228: 877664411 229: 877664411 230: 877664411 231: 877664411
232: -1649260597 233: 316768825 234: 2131817644 235: -344827877 236: -344827877 237: -344827877 238: -344827877 239: -344827877
240: 1507572298 241: -850335356 242: 917706998 243: -1729997980 244: -1729997964 245: -1729997916 246: -300328684 247: -300295917
248: 1129373059 249: 1129405826 250: 1925630953 251: -1389021877 252: -1504055233 253: 2035944385 254: 2035944385 255: 2035944385
Segmentation fault: 11