QuickSort Algorithm in C [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question appears to be off-topic because it lacks sufficient information to diagnose the problem. Describe your problem in more detail or include a minimal example in the question itself.

Closed 9 years ago.

Improve this question

I'm trying to write a recursive program for a QuickSort algorithm. Here's my code so far:

void QuickSort(int *array, int first, int last){
  int q;
  if (first<last){
    q = partition(array,first,last);
    QuickSort(array,first,q-1);
    QuickSort(array,q+1,last);
  }
}

void partition(int *A, int p, int r){
  int value = A[r];
  i = p-1;
  int tmp;
  for (j = p; j<=r; j++){
    if (A[j] <= value) {
      i++;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
return(i);
}

int main(){                                                                            
  int numArray[8] = {30,15,11,40,75,80,70,60};
  int i;

  printf("Before sorting: \n");
  for (i = 0; i<8; i++) printf("numArray[%d] = %d\n", i, numArray[i]);

  int first = 0;
  int last = sizeof(numArray)/sizeof(numArray[0]);
  QuickSort(numArray,first,last-1);

  printf("After sorting: \n");
  for (i = 0; i<8; i++) printf("numArray[%d] = %d\n", i, numArray[i]);
}

My problem is that when I run this, I get stuck in an infinite loop when I get to the first recursion call (just after partition). Also, what I've noticed is that the recursion call is ran on the array values of A[0] - A[5], even though it should be on A[0]-A[3]. I'm not expecting a complete answer, but maybe a hint on why the program is stuck in that infinite would be extremely helpful.

Answer 1

Here's what I did with your outline and it seems to be working and sorting fine. I replaced the void with an int, and declared int's as necessary

#include<iostream>
using namespace std;


int partition(int *A, int p, int r){
    int value = A[r];
    int i = p-1;
    int tmp;
    for (int j = p; j<=r; j++){
        if (A[j] <= value) {
        i++;
        tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
        }
   }
return(i);
}
void QuickSort(int *array, int first, int last){
    int q;
    if (first<last){
        q = partition(array,first,last);
        QuickSort(array,first,q-1);
        QuickSort(array,q+1,last);
    }
}



int main(){
    int numArray[8] = {30,15,11,40,75,80,70,60};

    printf("Before sorting: \n");
    for (int i = 0; i<8; i++) printf("numArray[%d] = %d\n", i, numArray[i]);

    int first = 0;
    int last = sizeof(numArray)/sizeof(numArray[0]);
    QuickSort(numArray,first,last-1);

    printf("After sorting: \n");
    for (int i = 0; i<8; i++) printf("numArray[%d] = %d\n", i, numArray[i]);
}