Denis
Denis

Reputation: 1229

C sorting changes the value in array

Hi I am using a sorting algorithm in one of my program. It is quick sort. I tested it with a sorted array as follow

int arr[7] = {1,2,3,4,5,6,7};

Code of sorting algorithm is

void sort(int arr[],int left,int right)
{
   int i= left, j= right;
   int pivot = arr[((left+right)/2)];
   int tmp=0;


/* partition */
   printf("%d\n",arr[0]);
   while(i<=j)
   {
      while(arr[i]<pivot)
          i++;

      while(arr[j]>pivot)
          j--;

      if(i<=j)
      {
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        i++;
        j--;
      }


   };

/* recursion */

   if(left<j)
      sort(arr,left,j);
   if(i<right)
      sort(arr,i,right);

 } 

When it return the result it gives arr[0] value as 0. which should be 1.

I am calling this function inside main. Below is the code for calling sort

int main()
{
  int i;
  int arr[7] = {1,2,3,4,5,6,7};int max=0,min=0;

  int len = (sizeof(arr)/sizeof(arr[0]));

  printf("%d\n",arr[0]);

  sort(arr,0,len);

  printf("%d\n",arr[0]);

  return 0;
}

Upvotes: 0

Views: 69

Answers (2)

dbush
dbush

Reputation: 225477

Here's your problem:

sort(arr,0,len);

You're passing the size as the rightmost array element. This results in you reading and writing off the end of the array, resulting in undefined behavior.

You need to pass in the index of the rightmost element, which is 1 less:

sort(arr,0,len-1);

Upvotes: 2

Zbynek Vyskovsky - kvr000
Zbynek Vyskovsky - kvr000

Reputation: 18865

The algorithm itself looks good, except I think it's better to have <= pivot and >= pivot in the while loops.

The only issue I can think about is that you call the sort function with arguments 0 and number of elements in the array. But note the right here means the index of the right position, not behind. So it should be 7 or sizeof(arr)/sizeof(arr[0])-1)

Upvotes: 1

Related Questions