Sorting one array into another- C

Question

So I am trying to write this function where the input parameter array will be taken and copied into another array but in a sorted way. For example: an input parameter of 3, 1, 9, 8 will copy into the target array 1, 3, 8, 9.

This is what I have so far but it only copies the smallest element in every time. I'm looking for a way to "blacklist" smallest values that are discovered in each pass.

void sort_another_array(int *param, int *target, int size){
    int i, j, lowest = param[0];
    for(i = 0; i < size; i++){
        for(j = 0; j < size; j++){
            if(param[j] < lowest){
                lowest = param[j]
            }
        }
        target[i] = lowest;
    }
}

Of course I could have another array of already found lowest values but that's more unnecessary looping and checking and adds to the already terrible n^2 complexity. Is there an easier way to do this?

I'm completely new to C, so please do restrict it to simple programming concepts of logic statements, using some flag variables etc..

Why don't you copy the array and then sort the new array in-place with the algorithm of your choice: en.wikipedia.org/wiki/… ? — Fredrik Savje
– Fredrik Savje, Commented Feb 13, 2016 at 6:18
I thought about it but then I kept going with my original idea and wanted to see if I could crack it open. It's like an itch now and I'd like to see a solution to this if only for my sanity's sake. — move_slow_break_things
– move_slow_break_things, Commented Feb 13, 2016 at 6:25
Looks like you are trying to implement selection sort. As it turns out, selection sort is actually easier to implement in place as that article shows. — kaylum
– kaylum, Commented Feb 13, 2016 at 6:29
@kaylum I can't change the data of the array I'm passing in. I have done in place sorting before. Which is what made this so annoying to me when I realized I couldn't change the param array. I thought it would be relatively simple. — move_slow_break_things
– move_slow_break_things, Commented Feb 13, 2016 at 6:32
Copy the array into the target and then do in place sort of the target? — kaylum
– kaylum, Commented Feb 13, 2016 at 6:33

Fredrik Savje · Accepted Answer · 2016-02-13 07:24:28Z

3

The probably most straight-forward way to do this is to first copy the whole array and then sort the new array in-place using a standard sorting algorithm.

However, if you want to keep the current structure, the following would be an alternative when all elements are unique:

void sort_another_array(int *param, int *target, int size) {
    int i, j, past_min = INT_MAX, current_min = INT_MAX;
    for (i = 0; i < size; ++i) {
        for (j = 0; j < size; ++j) {
            if (i == 0 || param[j] > past_min) {
                if (past_min == current_min || param[j] < current_min) {
                    current_min = param[j];
                }
            }
        }
        target[i] = current_min;
        past_min = current_min;
    }
}

What this does is keeping track of the previously lowest element found (past_min). The next element to find is lowest among all elements greater than past_min. I.e., we want both param[j] > past_min and param[j] < current_min to be true. However, the first element to add to target (i.e., when i == 0) will not have a lower element before it, so we add an exception for that. Similar, the first element satisfying param[j] > past_min in a pass will not have any element to compare with so we add another exception using past_min == current_min (this is true only for the first element found in a pass).

If you have duplicates in the array, this might work:

void sort_another_array(int *param, int *target, int size) {
    int j, past_min, current_min, write = 0, round_write = 0;
    while (round_write != size) {
        for (j = 0; j < size; ++j) {
            if (round_write == 0 || param[j] > past_min) {
                if (write == round_write || param[j] < current_min) {
                    current_min = param[j];
                    write = round_write;
                    target[write] = current_min;
                    ++write;
                } else if (param[j] == current_min) {
                    target[write] = current_min;
                    ++write;
                }
            }
        }
        round_write = write;
        past_min = current_min;
    }
}

Basically it's the same idea, but it writes all elements of the minimum value in the same pass.

edited Feb 13, 2016 at 7:24

answered Feb 13, 2016 at 7:03

Fredrik Savje

5652 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

nalzok Over a year ago

In your first code, if I write past_min = INT_MIN;, can I simply use param[j] > past_min && param[j] < current_min as the condition?

Fredrik Savje Over a year ago

@sunqingyao It will not work without additional changes unfortunately. After the first pass, it sets past_min = current_min. Thus, for all subsequent elements param[j] > past_min && param[j] < current_min will always be false.

Fredrik Savje Over a year ago

Note that the use of INT_MAX is a bit misleading in this case. It's not, as one first would expect, to make param[j] < current_min true in the first pass. In most cases, any initial value of past_min and current_min would work as long as they are the same. The one exception is when the smallest element in the whole array is that initial value, in which case it will be skipped for the second smallest. However, the only time INT_MAX is the smallest value is when it's the only value, so we are safe to initialize with that.

move_slow_break_things Over a year ago

@FredrikSavje Would it be easier to store the sorted indices and not the physical elements of the array in the new array and use that as a map later on? For example, the param array of 3, 1, 9, 8 would result in the sorted array being filled with 1, 0, 3, 2 (which are the indices of the elements appearing in sorted order).

Fredrik Savje Over a year ago

@samz_manu In a way it would be easier when there are duplicate elements. It is then straight-forward to make all elements unique by doing a two-level sort: first sort on value and when ties on index (the sorting would also be stable). I.e., one could use the structure of the first example even if there is duplicate elements. However, I wouldn't delve too deep into this; if you want to learn more about sorting, I suggest you read up on existing algorithms.

Rabbid76 · Accepted Answer · 2016-02-13 06:37:07Z

You can use a modified insertion sort algorithm to solve this problem:

#include <stdio.h>

void sort_another_array(int *param, int *target, int size)
{
    for ( int i = 0; i < size; i ++ )            // do for all elements in param
    {
        int j = i - 1;
        while ( j >= 0 && target[j] > param[i] ) // find index of element in target which is samler or equal than param[i]
        {
            target[j+1] = target[j];             // shift forward element of target which is greater than param[i]
            j --;
        }
        target[j+1] = param[i];                  // insert param[i] into target
    }
}

#define SIZE 10

int main( void )
{
    int a[SIZE] = { 9, 8, 0, 2, 1, 3, 4, 5, 7, 6 };
    int b[SIZE];

    sort_another_array( a, b, SIZE );
    for ( int i = 0; i < SIZE; i ++ )
        printf( "%2d", b[i] );

    return 0;
}

Ahmed Akhtar · Accepted Answer · 2016-02-13 06:50:59Z

The solution I am providing, has a limitation that: If there are no duplicates in the array, then this will work:

void sort_another_array(int *param, int *target, int size)
{
 int i, j, lowest;

 for(i = 0; i < size; i++)
 {
    int k = 0;
    if( i > 0) // for all except first iteration
    {
     while(param[k] <= target[i-1]) // find the one greater than the last one added
      k++;
    }
    lowest = param[k];

    for(j = 1; j < size; j++)
    {
        if( ( i==0 && param[j] < lowest ) || ( i > 0 && param[j] < lowest && param[j] > target[i-1])) // for all except first iteration the min found should be greater than the last one found
        {
          lowest = param[j];
        }
     }
     target[i] = lowest;
 }
}

Collectives™ on Stack Overflow

Sorting one array into another- C

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related