How to implement the following algorithm to sort a dynamic array in c?

Question

I was trying to write a simple sort function to sort int arrays, and I looked into some simple algorithms like bubble sort. I have written the following code, and it does an OK job to sort int arrays, in an ascending order:

void bubble_sort(float *scores, int size) {
    int i = 0,j = 0;
    float container = 0;
    for(i = 0; i < size - 1; i++) {
        for(j = 0; j < size - i - 1; j++) {
            if(scores[j] > scores[j + 1]) {
                container = scores[j];
                scores[j] = scores[j + 1];
                scores[j + 1] = container;
            }
        }
    }
}

Then I thought of how I would usually sort a set of integers on a piece of paper, and I thought why not write a code that would do the same thing. But it turns out it is not as simple as I thought it would be at first glance. I noticed that I usually use a simple algorithm to sort a set of integers in an ascending order, using the following method:

assume the set {4, 8, 1, 9, 0}

first I create an empty set that has five empty places. { , , , , }
I look for the minimum in the set, which is 0 in this case.
and then I add it to the first empty place in my new set: {0, , , , }
finally I delete the element I used from the original set: {4, 8, 1, 9}
I repeat the above process until there are no more elements left in my original set.
Now I have an ordered set.

So I went ahead and wrote a small function that can find the minimum in an array:

int minimum(int *array, int size) {
    int i, min = array[0];
    for(i = 1; i < size; i++) {
        if(array[i] < min) {
            min = array[i];
        }
    }
    return min;
}

I was going to write a function that would take an array and sort it, until I realized I can't delete items from an array. I’m at a loss here, what should I do next?

Copy the later elements of the array down one step, while remembering to change the size. If you "remove" the last element, just decrease the size. — Some programmer dude
– Some programmer dude, Commented Jan 17, 2015 at 17:53
The algorithm you invented is called selection sort. Usual thing to do is to just swap minimum with place where you want to put it. — zch
– zch, Commented Jan 17, 2015 at 17:54
c arrays are just bytes in memory, not objects, so you can not modify them simply — maxpovver
– maxpovver, Commented Jan 17, 2015 at 17:54

mrk · Accepted Answer · 2015-01-17 17:55:58Z

1

What you are describing is a sorting algorithm called selection sort. Repeatedly select the minimum element and yield it. You don't have to perform a deletion, just maintain a index NEXT that tells you the next position to which you should write the number (initially set to 0).

So essentially you simulate a deletion of an item at position POS by swapping it with the number at position NEXT.

The naive implementation takes O(n*n) time because you go over the list to find the minimum. A faster selection algorithm would use a heap structure to get the minimum in O(lg n) time.

answered Jan 17, 2015 at 17:55

mrk

3,1811 gold badge32 silver badges39 bronze badges

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

Collectives™ on Stack Overflow

How to implement the following algorithm to sort a dynamic array in c?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related