0

I am creating four functions:

  1. Allocate memory to an array
  2. Generate random chars an fill the array
  3. Sort the array into ascending order
  4. Print the sorted array

Like you will see in the code, I use a printf to see the generated chars.
The problem is, that the sorting function is not working right and I can't understand where is the problem (I get an output where the characters aren't sorted like they should be).

Can someone please tell me what I'm doing wrong? Any other tips on how I can improve all the code would be welcome as well.

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

int size = 20;
char* pArrChar1;
void allocate(char**);
void fill(char*);
void sort(char*);
void printArr(char*);

void main() {

    allocate(&pArrChar1);
    fill(pArrChar1);
    sort(pArrChar1);
    printArr(pArrChar1);

   system("pause");
}

void allocate(char** p_char) {
    *p_char = (char*)malloc(size*sizeof(char));
}

void fill(char* p_char) {
    int max = 90 ;
    int min = 65;
    for (int i = 0; i < size; i++) {
        p_char[i]= (char)(rand() % (min + 1 - max) + min);
        printf("%c ", p_char[i]);
    }
    printf("\n\n");
}

void sort(char* p_char) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - 1; j++) {
            if (*(p_char + j) > *(p_char + j + 1)) {
                char tmp = *(p_char + j);
                *(p_char + j) = *(p_char + j + 1);
                *(p_char + j + 1) = tmp;
            }
        }
    }
}

void printArr(char* p_char) {
    for (int i = 0; i < size; i++)
        printf("%c ", p_char[i]);
   printf("\n\n");
}
5
  • 1
    You should be a bit more specific in your description of the problem. What was the order you expected, and what was the order you saw? Commented Nov 10, 2015 at 0:09
  • 2
    You might also explain how your sort routine is supposed to work, and why you think that should actually sort the array. In particular, why it does not do anything with j. Commented Nov 10, 2015 at 0:12
  • this is the generated: R L W E R E G G K I R R B D B L T O D M and sorted: L R E R E G G K I R R B D B L T O D M . expected was : B, B, E, E, ..., R, T Commented Nov 10, 2015 at 0:22
  • Any particular reason why you use *(p_char + i + 1) instead of p_char[i + 1]? The latter is simpler to read, if nothing else. Commented Nov 10, 2015 at 0:27
  • found the error it was because of j. some ideas how I can do this code better? Commented Nov 10, 2015 at 0:30

4 Answers 4

1

You have an implementation error on line 38. This verbose output below shows what line it faulted on. The "ASan" tool claims you have a heap buffer overflow.

When i is 19, you dereference p_char[20], this is beyond the end of the allocation.

$ clang -fsanitize=address -g -Wall sorter.c 
sorter.c:11:1: warning: return type of 'main' is not 'int' [-Wmain-return-type]
void main() {
^
sorter.c:11:1: note: change return type to 'int'
void main() {
^~~~
int
1 warning generated.
$ ./a.out 
H W J T R H K M J N C T C T L W M S E Q 

=================================================================
==7176==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60300000eff4 at pc 0x0000004cd8af bp 0x7fff8db88420 sp 0x7fff8db88418
READ of size 1 at 0x60300000eff4 thread T0
    #0 0x4cd8ae in sort /home/brian/src/so/sorter.c:38:33
    #1 0x4cd5e4 in main /home/brian/src/so/sorter.c:15:5
    #2 0x7fbeb021da3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x20a3f)
    #3 0x417508 in _start (/home/brian/src/so/a.out+0x417508)

0x60300000eff4 is located 0 bytes to the right of 20-byte region [0x60300000efe0,0x60300000eff4)
allocated by thread T0 here:
    #0 0x4a626b in __interceptor_malloc /home/development/llvm/3.7.0/final/llvm.src/projects/compiler-rt/lib/asan/asan_malloc_linux.cc:40:3
    #1 0x4cd65c in allocate /home/brian/src/so/sorter.c:22:22
    #2 0x4cd576 in main /home/brian/src/so/sorter.c:13:5
    #3 0x7fbeb021da3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x20a3f)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/brian/src/so/sorter.c:38:33 in sort
Shadow bytes around the buggy address:
  0x0c067fff9da0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9db0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9dc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9dd0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9de0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c067fff9df0: fa fa fa fa fa fa fa fa fa fa fa fa 00 00[04]fa
  0x0c067fff9e00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9e10: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9e20: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9e30: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9e40: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==7176==ABORTING
Sign up to request clarification or add additional context in comments.

Comments

1

Here I updated the sort function with the following one;

/* new sort */
void sort2(char* p_char) {
    counter = 0;
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (*(p_char + i) > *(p_char + j)) {
                char tmp = *(p_char + i);
                *(p_char + i) = *(p_char + j);
                *(p_char + j) = tmp;

                counter++;
            }
        }
    }
    printf("Sort2 process # : %d\n", counter);
}

And using this updated sort, improves the process number for finding the solution, the output as below for 50,000 random chars;

D:\SOF>gcc main.c -Wall -Wextra -pedantic -std=c11 -o main

D:\SOF>main
Sort  process # : 598810451
Sort2 process # : 574789

Please checkout the test code down below;

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

#define MAX_SIZE 50000

int counter = 0;
int size = MAX_SIZE;
char* pArrChar1;
void allocate(char**);
void fill(char*);
void sort(char*);
void sort2(char* p_char); /* updated sort */
void printArr(char*);

int main() {

    allocate(&pArrChar1);
    fill(pArrChar1);
    sort(pArrChar1);
    //printArr(pArrChar1);

    allocate(&pArrChar1);
    fill(pArrChar1);
    sort2(pArrChar1);

    system("pause");

    return 0;
}

void allocate(char** p_char) {
    *p_char = (char*)malloc(size*sizeof(char));
}

void fill(char* p_char) {
    int max = 90 ;
    int min = 65;
    for (int i = 0; i < size; i++) {
        p_char[i]= (char)(rand() % (min + 1 - max) + min);
        //printf("%c ", p_char[i]);
    }
    //printf("\n\n");
}

void sort(char* p_char) {
    counter = 0;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - 1; j++) {
            if (*(p_char + j) > *(p_char + j + 1)) {
                char tmp = *(p_char + j);
                *(p_char + j) = *(p_char + j + 1);
                *(p_char + j + 1) = tmp;

                counter++;
            }
        }
    }
    printf("Sort  process # : %d\n", counter);
}

/* new sort */
void sort2(char* p_char) {
    counter = 0;
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (*(p_char + i) > *(p_char + j)) {
                char tmp = *(p_char + i);
                *(p_char + i) = *(p_char + j);
                *(p_char + j) = tmp;

                counter++;
            }
        }
    }
    printf("Sort2 process # : %d\n", counter);
}

void printArr(char* p_char) {
    for (int i = 0; i < size; i++)
        printf("%c ", p_char[i]);
    printf("\n\n");
}

Hope that it helps!

Comments

0

In your code, you have:

for (int i = 0; i < size; i++) {
    for (int j = 0; j < size - 1; j++) {
        if (*(p_char + i) > *(p_char + i + 1)) {

When i is equal to size - 1, you're accessing out of bounds.

Change the loop limits:

for (int i = 0; i < size - 1; i++) {
    for (int j = 0; j < size; j++) {
        if (*(p_char + i) > *(p_char + i + 1)) {

This at least avoids the out of bounds array access. It is surprising that you aren't using i and j as subscripts; you seem to repeat the same comparison a lot as written.

Comments

0

the sort function had an error, this is the correct one

void sort(char* p_char) {
for (int i = 0; i < size; i++) {
    for (int j = 0; j < size - 1; j++) {
        if (*(p_char+j) > *(p_char + j + 1)) {
            char tmp = *(p_char + j);
            *(p_char + j) = *(p_char + j + 1);
            *(p_char + j + 1) = tmp;
        }
      }
   }
}

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.