Quicksorting code doesnt work for more than about ten strings

Question

My code doesn't sort more than ten words and I need it to sort about 2000 strings of alfabet. and string length is less than 20 characters. I made sure that the file read and write is correct. the file have a list of words less than 20 characters and each line contains one word. the problem is that the quick sort function is not sorting for large amount of strings.

#include <stdio.h>
#include <string.h>

void quickSortMain(char items[][20], int count);
void quickSort(char items[][20], int left, int right);

int main(void)
{
  int i=0, n=0;
  char str[2000][20];
  memset(str, 0 , sizeof(str[0][0])*20*1000);
  FILE *fil;
  fil=fopen("text.txt","r");
  if (fil!=NULL)
  {
      while (!feof(fil))
      {
          fgets(str[i], 20, fil);
          i++;
      }

      fclose(fil);
  }
  else
  {
      printf("can not open");
      scanf("\n");
  }


  fil=fopen("text.txt","w");
  if (fil!=NULL)
  {
      fclose(fil);
  }
  else
  {
      printf("can not open");
      scanf("\n");
  }

    quickSortMain(str, i);

    fil=fopen("text.txt","a");
  if (fil!=NULL)
  {
      while(n<i)
      {
          fprintf(fil,"%s", str[n]);
          n++;
      }
      fclose(fil);
  }
  else
  {
      printf("can not open");
      scanf("\n");
  }
  return 0;
}
void quickSortMain(char items[][20], int count)
{
  quickSort(items, 0, count-1);
}

void quickSort(char items[][20], int left, int right)
{
  int i=left;
  int j=right;
  char *x=items[(left+right)/2];
  char temp[right+1];

  while(i <= j)
    {
    while((strcmp(items[i],x) < 0) && (i < right)) {
       i++;
    }
    while((strcmp(items[j],x) > 0) && (j > left)) {
        j--;
    }
    if(i <= j) {
      strcpy(temp, items[i]);
      strcpy(items[i], items[j]);
      strcpy(items[j], temp);
      i++;
      j--;
   }
  }

  if(left < j) {
     quickSort(items, left, j);
  }
  if(i < right) {
     quickSort(items, i, right);
  }
}

Did you tried using a debugger? How do you know it is not sorting correctly? — Martin Zabel, Mar 13 '16 at 16:52
Unrelated, once this is fixed and you wonder why your last file entry appears twice in your output, [you may want to read this](https://stackoverflow.com/questions/5431941/why-is-while-feof-file-always-wrong?) — WhozCraig, Mar 13 '16 at 17:40

2501 · Accepted Answer · 2016-03-13T17:04:04.177

The problem is the pivot. When you swap the two elements in the innermost loop:

if(i <= j) {
    strcpy(temp, items[i]);
    strcpy(items[i], items[j]);
    strcpy(items[j], temp);
    i++;
    j--;
}

one of those two elements, items[i], items[j], might be the pivot. In other words x might be pointing to one of them. After the swap, x isn't pointing to the correct pivot anymore, because the values in the elements to which x is pointing to were changed.

The simplest solution is to allocate additional space for the pivot:

...
char *x=items[(left+right)/2];
char pivot[20];
strcpy(pivot, x);
x = pivot;
...

score 0 · Answer 2 · answered Mar 13 '16 at 16:57

I have other things to add to 2501's answer.

You should exit program when you detect you cannot read or write the file.

I would use strcpy() rather than memset() to initialize:

for (int n = 0; n < 2000; n++)
{
    strcpy(str[n], "");
}

You poorly process newline characters. You should remove them from read lines in your array, and if you don't have one, you should write a warning and skip end of line, and after that add a newline after each word when you write your file. I tested your program and having 20 length lines or a last line with no newline at the end gives bad surprises.

score -1 · Answer 3 · answered Mar 13 '16 at 16:40

your Quick sort implementation is wrong !!!

Here is a Quicksort for array in C-Programme

#include <stdio.h>
#include <stdlib.h>

int * quickSort(int *A,int pivotIndex, int N);
int partition(int *A, int pivotIndex, int N);

int main(){
    int N;
    printf("Enter Number of Elements : ");
    scanf("%d",&N);
    int A[N];
    printf("\nEnter Data : ");
    int i=0;
    for(i=0; i<N; i++)
        scanf("%d",&A[i]);

    int *p;
    p = quickSort(A,0,(N-1));

    printf("\nSorted Data : ");
    for(i=0; i<N; i++)
        printf("%d ",p[i]);
    return 0;
}

int * quickSort(int *A, int pivotIndex, int N){

    if(pivotIndex < 0 || pivotIndex > N)
        return ;

    int q = partition(A,pivotIndex, N);
    quickSort(A, 0, (q-1));
    quickSort(A, (q+1), N);

    return A;
}

int partition(int *A, int pivotIndex, int N){

    int i = pivotIndex;
    int flag = 0;

    while(flag == 0){

        flag = 1;
        int j = N;
        int rightFlag = 0, leftFlag = 0;
        while(j > i && rightFlag == 0){

            if(A[i]>A[j]){
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                i = j;
                rightFlag = 1;
                flag = 0;
            }
            j--;
        }
        if(flag == 1)
            break;

        flag = 1;
        j = pivotIndex;
        while(j < i && leftFlag == 0){

            if(A[i]<A[j]){
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                leftFlag = 1;
                flag = 0;
                i = j;
            }
            j++;
        }
    }

    return i;
}

Quicksorting code doesnt work for more than about ten strings

3 Answers3