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

`for(i=1;i<=n;i++)` writing to address which you do not own. — babon, Jul 15 '17 at 06:46
@babon I did not get it. Are you saying that something is wrong in deceleration of the array? — nikunj_r, Jul 15 '17 at 06:55
@nikunj_r Array indexes in C start from 0 and can go up to one less than the size of the array. You should loop from `0` to `n - 1`. — babon, Jul 15 '17 at 06:59
`else if(a[i] < pivot) i++;` : first time `a[i] == pivot` So This loop is an infinite loop and does not end. Also your logic does not basically consider that the same value exists. — BLUEPIXY, Jul 15 '17 at 07:08
@BLUEPIXY But what if we consider that all the elements of the array are distinct. And sorry for not mentioning it. — nikunj_r, Jul 15 '17 at 07:22
Even if everything is separate, you need a case of equal because you choose `pivot` from among them. In general there is no guarantee that all of the sequences are distinct. If all is the same as an example(`{5,5,5,5,5}`), none of `if` in your logic will execute the body. — BLUEPIXY, Jul 15 '17 at 07:28
`int a[n];` is wrong. size of array must be const if declared as auto — duong_dajgja, Jul 15 '17 at 07:30
@duong_dajgja you have missed last 20 years. Some kind of hibernation? — 0___________, Jul 15 '17 at 07:56

score 1 · Answer 1 · answered Jul 15 '17 at 08:12

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

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

Your first point is correct, but not the others, if the pivot is a scalar value, its value can be copied to a local variable `pivot` and you can include it in the partitioning logic and there is no need to swap it back in at the end. Hoare's original algorithm does just that: https://en.wikipedia.org/wiki/Quicksort — chqrlie, Jul 15 '17 at 14:10
@chqrlie: ah, Nice catch. I didn't know about this. Thanks for your nitpick ;) . Will give it a read for sure. — Rohan Kumar, Jul 15 '17 at 14:54

amrender singh · Answer 2 · 2017-07-15T08:15:12.840

0

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

edited Jul 15 '17 at 08:15

answered Jul 15 '17 at 07:36

amrender singh

7,949
3
22
28

@nikunj_r please check your quick sort logic. – amrender singh Jul 15 '17 at 08:15
I checked that. Thanks for your help :-) . – nikunj_r Jul 15 '17 at 14:49

score 0 · Answer 3 · answered Jul 15 '17 at 08:23

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

In the stop condition of recursive function when i use if(lo>hi){ return; } then also it runs correctly. I want to know whether it is correct or not. — nikunj_r, Jul 15 '17 at 13:55

score 0 · Answer 4 · edited Jul 15 '17 at 10:21

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

score 0 · Answer 5 · answered Jul 15 '17 at 14:20

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

Is it necessary to check return value of `scanf()`? Because generally the code runs correctly without it. — nikunj_r, Jul 15 '17 at 15:13
@nikunj_r: The code run correctly as long as the input is correct. Testing the return value is the only way to detect incorrect input, such as a letter when expecting a number. Invalid input will cause the program to have undefined behavior. — chqrlie, Jul 15 '17 at 15:15
Okay. And your suggestion about avoiding the naming of variable like `l` was helpful. :-) . — nikunj_r, Jul 15 '17 at 15:25

C program not responding after scanf statement

5 Answers5