Sorting 1st k elements of an array in increasing order and rest in decreasing order in C

Question

This is the code for arranging the array in increasing order:

for(i=0; i<k-1; i++)
    {
        xchanges = 0;
        for(j=0; j<k-1-i; j++)
        {
            if(arr[j] > arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                xchanges++;
            }
        }
        if(xchanges == 0)
            break;
    }

This is the code for arranging the array in decreasing order:

for(i=k; i<n-1; i++)
    {
        xchanges = 0;
        for(j=k; j<n-1-i; j++)
        {
            if(arr[j] < arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                xchanges++;
            }
        }
        if(xchanges == 0)
            break;
    }

Both parts are working fine individually on the whole array. But when the code is placed one after another ,then the second part of the code is not working. These two fragments are in sort_array(). That's called from a main function like this:

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

int main(void)
{
    int *arr, n, i, k;
    scanf("%d %d", &n, &k);
    arr = (int*)malloc(n*sizeof(int));
    for(i=0; i<n; i++)
    {
        scanf("%d", &arr[i]);
    }
    int* res = sort_array(arr,n,k);
    for(i=0; i<n; i++)
    {
        printf("%d ", res[i]);
    }
    return 0;
}

Please create a [Minimal, **Complete**, and Verifiable Example](http://stackoverflow.com/help/mcve) to show us. What is`sort_array` and what does it return? Also take some time to [read about how to ask good questions](http://stackoverflow.com/help/how-to-ask), and edit your question to tell us *how* your code "is not working" (including your input, and your expected and actual output). Lastly, please [learn how to debug your programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). — Some programmer dude, Dec 19 '17 at 08:40
[Don't cast the result of `malloc` in C](http://stackoverflow.com/q/605845/995714) — phuclv, Dec 19 '17 at 09:27

score 1 · Answer 1 · answered Dec 19 '17 at 09:16

The problem is in the limit on the second (sort decreasing) loop when k is neither 0 nor n.

This code takes the material in the question and creates an instrumented version of the code.

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

static void sort_array(int *arr, int n, int k)
{
    int i;
    int j;
    int xchanges;
    int temp;
    printf("n = %d; k = %d\n", n, k);

    for (i = 0; i < k; i++)
    {
        printf("Loop 1: i = %d (L = %d)\n", i, k - 1 - i);
        xchanges = 0;
        for (j = 0; j < k - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                xchanges++;
            }
        }
        if (xchanges == 0)
            break;
    }

    printf("n = %d; k = %d\n", n, k);
    for (i = k; i < n; i++)
    {
        printf("Loop 2: i = %d (L = %d)\n", i, n - 1 - i);
        xchanges = 0;
        // for (j = k; j < n - 1 - i; j++)      // Buggy!
        for (j = k; j < n - 1 - i + k; j++)     // Fixed!
        {
            if (arr[j] < arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                xchanges++;
            }
        }
        if (xchanges == 0)
            break;
    }
    printf("n = %d; k = %d\n", n, k);
}

static void dump_array(const char *tag, int n, int *arr)
{
    printf("%s:\n", tag);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    putchar('\n');
}

int main(void)
{
    int *arr, n, i, k;
    scanf("%d %d", &n, &k);
    arr = (int *)malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    dump_array("Before", n, arr);
    sort_array(arr, n, k);
    dump_array("After", n, arr);

    return 0;
}

The bug fix is clearly marked. I tested with a random number generator but using a fixed seed, on a set of 20 double-digit values between 10 and 99.

Buggy trace

Before:
15 31 62 60 42 24 38 73 52 13 23 47 36 28 54 62 19 99 68 73 
n = 20; k = 10
Loop 1: i = 0 (L = 9)
Loop 1: i = 1 (L = 8)
Loop 1: i = 2 (L = 7)
Loop 1: i = 3 (L = 6)
Loop 1: i = 4 (L = 5)
Loop 1: i = 5 (L = 4)
Loop 1: i = 6 (L = 3)
Loop 1: i = 7 (L = 2)
Loop 1: i = 8 (L = 1)
Loop 1: i = 9 (L = 0)
n = 20; k = 10
Loop 2: i = 10 (L = 9)
n = 20; k = 10
After:
13 15 24 31 38 42 52 60 62 73 23 47 36 28 54 62 19 99 68 73

Fixed trace

Before:
15 31 62 60 42 24 38 73 52 13 23 47 36 28 54 62 19 99 68 73 
n = 20; k = 10
Loop 1: i = 0 (L = 9)
Loop 1: i = 1 (L = 8)
Loop 1: i = 2 (L = 7)
Loop 1: i = 3 (L = 6)
Loop 1: i = 4 (L = 5)
Loop 1: i = 5 (L = 4)
Loop 1: i = 6 (L = 3)
Loop 1: i = 7 (L = 2)
Loop 1: i = 8 (L = 1)
Loop 1: i = 9 (L = 0)
n = 20; k = 10
Loop 2: i = 10 (L = 9)
Loop 2: i = 11 (L = 8)
Loop 2: i = 12 (L = 7)
Loop 2: i = 13 (L = 6)
Loop 2: i = 14 (L = 5)
Loop 2: i = 15 (L = 4)
Loop 2: i = 16 (L = 3)
Loop 2: i = 17 (L = 2)
Loop 2: i = 18 (L = 1)
n = 20; k = 10
After:
13 15 24 31 38 42 52 60 62 73 99 73 68 62 54 47 36 28 23 19

Note how judicious printing made it easy to spot the problem, and that the fix was working.

Extreme cases (k = 0, k = 20)

Both the fixed and the unfixed versions produced the same output on the extreme cases where k = 0 and k = 20 (aka n).

Before:
15 31 62 60 42 24 38 73 52 13 23 47 36 28 54 62 19 99 68 73 
n = 20; k = 20
Loop 1: i = 0 (L = 19)
Loop 1: i = 1 (L = 18)
Loop 1: i = 2 (L = 17)
Loop 1: i = 3 (L = 16)
Loop 1: i = 4 (L = 15)
Loop 1: i = 5 (L = 14)
Loop 1: i = 6 (L = 13)
Loop 1: i = 7 (L = 12)
Loop 1: i = 8 (L = 11)
Loop 1: i = 9 (L = 10)
Loop 1: i = 10 (L = 9)
Loop 1: i = 11 (L = 8)
Loop 1: i = 12 (L = 7)
Loop 1: i = 13 (L = 6)
Loop 1: i = 14 (L = 5)
n = 20; k = 20
n = 20; k = 20
After:
13 15 19 23 24 28 31 36 38 42 47 52 54 60 62 62 68 73 73 99 

Before:
15 31 62 60 42 24 38 73 52 13 23 47 36 28 54 62 19 99 68 73 
n = 20; k = 0
n = 20; k = 0
Loop 2: i = 0 (L = 19)
Loop 2: i = 1 (L = 18)
Loop 2: i = 2 (L = 17)
Loop 2: i = 3 (L = 16)
Loop 2: i = 4 (L = 15)
Loop 2: i = 5 (L = 14)
Loop 2: i = 6 (L = 13)
Loop 2: i = 7 (L = 12)
Loop 2: i = 8 (L = 11)
Loop 2: i = 9 (L = 10)
Loop 2: i = 10 (L = 9)
Loop 2: i = 11 (L = 8)
Loop 2: i = 12 (L = 7)
Loop 2: i = 13 (L = 6)
Loop 2: i = 14 (L = 5)
Loop 2: i = 15 (L = 4)
Loop 2: i = 16 (L = 3)
Loop 2: i = 17 (L = 2)
n = 20; k = 0
After:
99 73 73 68 62 62 60 54 52 47 42 38 36 31 28 24 23 19 15 13

Sorting 1st k elements of an array in increasing order and rest in decreasing order in C

1 Answers1

Buggy trace

Fixed trace

Extreme cases (k = 0, k = 20)