Thread: 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;
}

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);