I implemented quuicksort for practice and have a subtle bug

Hello,

I have run my program with GDB and when I enter

Code:

---

my_quicksort(array)

---

in

Code:

---

main()

---

I have high set to -7575 consistently and low set to 0. I do not understand how this can happen, I have run it 3 times now and it is always -7575. It should be 8 right?

Code:

---

#include <stdio.h>




void swap(int arr[], int i, int j){
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}


void qs(int arr[], int low, int high){
  int mid = (low + high)/2;
  swap(arr, mid, high);
  int k = high - 1;
  for (int i = low; i < high-1; i++){
    if (arr[i] > arr[high])
      swap(arr,i,k--);
  }
  swap(arr, k, high);
  qs(arr, low, k-1);
  qs(arr, k+1, high);
}


void my_quicksort(int arr[]){
  int low = 0;
  int high = 8;
  int mid = (high + low)/2;
  swap(arr, mid, high);
  int k = high - 1;
  for (int i = 0; i < high - 1; i++){
    if (arr[i] > arr[high])
      swap(arr, i, k--);
  }
  swap(arr, k, high);
  qs(arr, low, k - 1);
  qs(arr, k + 1, high);


}


void print_array(int arr[]){
  for (int i = 0; i < 9; i++){
    printf("%d,%d\t", i, arr[i]);
  }
}






int main(){
  int array[9] = {3,7,5,0,3,5,2,8,1};


  my_quicksort(array);


  print_array(array);


  return 0;
}

---

You have no trap for the trivial case.

Code:

---

Breakpoint 1, swap (arr=0x7fffffffdda0, i=-1, j=0) at foo.c:7
7          int temp = arr[i];
(gdb) bt
#0  swap (arr=0x7fffffffdda0, i=-1, j=0) at foo.c:7
#1  0x00005555555554d6 in qs (arr=0x7fffffffdda0, low=0, high=0) at foo.c:21
#2  0x00005555555554ed in qs (arr=0x7fffffffdda0, low=0, high=2) at foo.c:22
#3  0x000055555555565b in my_quicksort (arr=0x7fffffffdda0) at foo.c:38
#4  0x00005555555559dd in main () at foo.c:60

---

So you end up wandering off the end of the array.

thanks, I did not see this and some other bugs. I have it working with the test array now:

Code:

---

#include <stdio.h>




void swap(int arr[], int i, int j){
  if (i == j)
    return;
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}


void qs(int arr[], int low, int high){
  if (high - low <= 0)
    return;
  int mid = (low + high)/2;
  swap(arr, mid, high);
  int k = high - 1;
  for (int i = k; i > 0; i--){
    if (arr[i] > arr[high])
      swap(arr, i, k--);
  }
  swap(arr, ++k, high);
  qs(arr, low, mid);
  qs(arr, mid + 1, high);
}


void my_quicksort(int arr[]){
  int low = 0;
  int high = 8;
  int mid = (high + low)/2;
  if (high - low <= 1)
    return;
  swap(arr, mid, high);
  int k = high - 1;
  for (int i = k; i > 0; i--){
    if (arr[i] > arr[high])
      swap(arr, i, k--);
  }
  swap(arr, ++k, high);
  qs(arr, low, mid);
  qs(arr, mid + 1, high);


}


void print_array(int arr[]){
  for (int i = 0; i < 9; i++){
    printf("%d,%d\t", i, arr[i]);
  }
  printf("%s\n","");
}






int main(){
  int array[9] = {3,7,5,0,3,5,2,8,1};


  my_quicksort(array);


  print_array(array);


  return 0;
}

---

It seems to me you have wrongly hard-coded this:

Code:

---

void my_quicksort(int arr[]){
  int low = 0;
  int high = 8;

[...]

---

Read one implementation from here:

rosettacode

Code:

---

void quicksort(int *A, int len);

---