Quicksort and Binary Search Algorithms in C/C++


Being able to sort and search efficiently is one of the most important and most studied aspects of computer science. In my opinion any programmer worth his salt should be able to, in a matter of 10 minutes or so, be able to write the algorithms of binary search as well as those of the most important sorts (e.g., insertion sort, selection sort, bubble sort, merge sort, heap sort, and quicksort).

Once you master those, though, you might wanna use a template to speed up development. Below are the templates I use for binary search and quicksort.

Notice that start and end in the bSearch function below refer to the first and last element, so end is the size of the array minus one. I use this approach because I think it makes easier to figure the limits you need to work with inside the function.

int bSearch(int n,int array[], int start, int end){
    int middle = (start+end)/2;

    if (start>end)
        return 0;

    if (n==array[middle])
        return 1;

    if (n>array[middle])
        return bSearch(n,array,middle+1, end);
    else
        return bSearch(n,array,start,middle-1);
}

And now the quicksort algorithm, where end is actually the size of the array.

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

int partition(int v[], int start, int end){
  int x,l,j;

  x = v[end-1];
  l = start-1;

  for (j=start;j<end-1;j++){
    if (v[j]<x){
      l++;
      swap(v,j,l);
    }
  }
  l++;
  swap(v,l,end-1);
  return l;
}

void quickSort(int v[],int start, int end){
  int q;

  if (end>start){
    q = partition(v,start,end;
    quickSort(v,start,q);
    quickSort(v,q+1,end);
  }    
  return;
}

One thought on “Quicksort and Binary Search Algorithms in C/C++

Leave a Reply

Your email address will not be published. Required fields are marked *