C program not responding after scanf statement

Question

My code compiles and also it runs. But after taking input it does not execute the next statement of the program.

It takes all input elements of the array then it does not do anything. I think there is problem after second scanf statement which is inside the for loop.

I am not sure that the code is correct but after compiling and running, I am expecting that it should give the final output even if it is not as expected (or incorrect).

I am using Code::Blocks(16.01) as IDE. My operating system is Windows 8.1(64-bit).

My code:

#include <stdio.h>

void quick(int *, int, int);

int main() {
    int n, i, pivot, j, k, l, u;

    printf("Give size\n");
    scanf("%d", &n);

    int a[n];
    printf("Enter the list\n");
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    quick(a, 1, n - 1);
    printf("\nSorted numbers are\n");
    for (i = 1; i <=n; i++)
        printf("%d ", a[i]);
    printf("\n");

    return 0;
}

void quick(int a[], int l, int u) {
    int pivot, j, temp, i;
    pivot = a[l];
    i = l;
    j = u;

    while (i <= j) {
        if (a[i] > pivot && a[j] < pivot) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        } 
        else if (a[i] < pivot)
            i++;
        else if (a[j] > pivot)
            j--;
    }
    quick(a, l, j - 1);
    quick(a, j + 1, u);
}

Output of the program

Answer 1

There are problems in your code:

• you do not check the return values of scanf().

• arrays are 0 based in C. The loop logic should read

  for (i = 0; i < n; i++) {
      ...
  }
  

• similarly, if the bounds are included in the function quick, which is not the classic way to do things in C, the function call should read:

  quick(a, 0, n - 1);
  

• avoid naming a variable l, it look confusingly similar to 1.

• The QuickSort algorithm in function quick seems incorrect. Here is an extensive reference: http://en.wikipedia.org/wiki/Quicksort

Here is a modified version:

#include <stdio.h>

void quick(int *, int, int);

int main(void) {
    int n, i;

    printf("Give size\n");
    if (scanf("%d", &n) != 1)
        return 1;

    int a[n];
    printf("Enter the list\n");
    for (i = 0; i < n; i++) {
        if (scanf("%d", &a[i]) != 1)
            return 1;
    }
    quick(a, 0, n - 1);
    printf("\nSorted numbers are\n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");

    return 0;
}

void quick(int a[], int lo, int hi) {
    if (lo < hi) {
        int pivot = a[lo];
        int i = lo - 1;
        int j = hi + 1;
        int temp;

        for (;;) {
            while (a[++i] < pivot)
                continue;
            while (a[--j] > pivot)
                continue;
            if (i >= j)
                break;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        quick(a, lo, j);
        quick(a, j + 1, hi);
    }
}

Answer 2

Try this and you can even modify as per your choice:

#include<stdio.h>
#include<conio.h>

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1); 

    for (int j = low; j <= high- 1; j++)
    {
        if (arr[j] <= pivot)
        {
            i++; // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
/*
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);

}

void main()
{
    clrscr();
    int arr[100], n,i;
    printf("Enter the size of array:\n");
    scanf("%d",&n);

    printf("Enter your Array List:\n");
    for (i=0;i<n;i++)
    scanf("%d",&arr[i]);

    quickSort(arr, 0, n-1);
    printf("Sorted array: ");
    printArray(arr, n);
    getch();
}

Answer 3

This is a working version of your program with some small modifications:

1) The first element is chosen as pivot

2) Check stop condition of the recursive function, that is if (lo >= hi) { return; }

3) Swap the pivot element with element at index i-1 after the while loop

4) Include equality in else if (a[i] <= pivot) and else if (a[j] >= pivot) to prevent infinitive loop when an element has the same value as pivot, for example 1 1 3 5

#include <stdio.h>


void quick(int a[], int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }

    int pivot, j, temp, i;
    pivot = a[lo];
    i = lo + 1;
    j = hi;

    while (i <= j)
    {
        if (a[i] > pivot && a[j] < pivot)
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
        else if (a[i] <= pivot)
            i++;
        else if (a[j] >= pivot)
            j--;
    }

    int l = i - 1;
    temp = a[l];
    a[l] = a[lo];
    a[lo] = temp;

    quick(a, lo, l-1);
    quick(a, l+1, hi);
}

int main()
{
    const int MAX_NUM = 100;
    int arr[MAX_NUM];

    int n = 0;
    printf("How many numbers? n = ");
    scanf("%d", &n);

    if (n < 1 || n > 100)
    {
        printf("Invalid input. Nothing to do\n");
        return 0;
    }

    for (int i = 0; i < n; i++)
    {
        printf("a[%d] = ", i);
        scanf("%d", &arr[i]);
    }

    printf("Sorting...\n");
    quick(arr, 0, n-1);

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

Answer 4

Correct your for loop,begin from 0 since C is 0 origin.

for(i=0;i<n;i++){ 
  scanf("%d",&a[i]);
}

C function parameters are always "pass-by-value", which means that the function scanf only sees a copy of the current value of whatever you specify as the argument expression.

Array name returns the pointer of the first element of a array (memory location where array is stored), and name of the scalar variable returns the value of the scalar, so you need to use & operator to get the memory location of scalar in which you need to write the value.

And kindly check your Quick sort logic and calling

Answer 5

As other people pointed out in comments, you're doing some mistakes:

1. You've declared your array as int a[n]; and array indexing starts from 0, then why are you passing the array like it's indexing starts from 1 ? You need to change those for loops to : for(i=0;i<n;i++) and you quicksort call like this: quick(a,0,n-1);.
2. You quicksort logic seems flawed. You choose a[l] as your pivot but you include that in your partitioning logic. You're also not checking for the base condition of your recursion, i.e l < u.
3. After partiioning the array you're supposed to swap the pivot with the mid element of your partition (i.e last element of first half or the first element of second half, depending upon your choice). I changed your quicksort function like this. And i was able to see the desired output.

I hope this helps.