C Basic Sort Algorithm

Question

I'm not really understanding the process behind this basic sorting algorithm using nested For loops:

for(i=0; i<MAX; i++){
        for(j=i; j<MAX; j++){
            if(data[i] > data[j]){
                tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
        }
    }

If j=i then wouldn't it just be looping and comparing the same numbers seeing as i and j both start at 0 in the loops?

I've tried googling for an explanation on this particular bit of code and can't find anything useful.

Full program:

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

#define MAX 10

int main()
{
    int data[MAX];
    int i, j, tmp;

    for(i=0;i<MAX;i++){
        printf("Enter number %d: ", i);
        scanf("%d", &data[i]);
    }

    for(i=0; i<MAX; i++){
        for(j=i; j<MAX; j++){
            if(data[i] > data[j]){
                tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
        }
    }

    printf("\nSorted List:\n");
    for(i=0;i<MAX;i++){
        printf("Item %d: %d\n", i, data[i]);
    }
}

Out of curiosity, where did you get this code? It appears as though someone couldn't decide between selection sort and bubble sort, then ended up with a bastardized version that is worse than both. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented Mar 1, 2017 at 6:44
I've been following C tutorials on Youtube and this particular code was from this video: youtu.be/Dtbqs0M-B-s?t=19m9s — GordanAndrews
– GordanAndrews, Commented Mar 1, 2017 at 7:17
Yeah, it is an OK algorithm in the context of that exercise, but please do not use it elsewhere ;-) — Antti Haapala
– Antti Haapala, Commented Mar 1, 2017 at 7:25

Antti Haapala · Accepted Answer · 2017-03-01 07:29:11Z

2

This algorithm is a dummified selection sort - it matches the description of selection sort on Wikipedia:

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

But indeed not the pseudo algorithm in that it does some unnecessary swaps.

In the first inner round, with i being equal to j, the comparison data[i] > data[j] will be false, and the swap will not be executed.

Then, j will be incremented, and now it is comparing ith value with i + 1th value.

To avoid one futile comparison, initialize j with i + 1:

for (i = 0; i < MAX; i++) {
    for (j = i + 1; j < MAX; j++) {
        if (data[i] > data[j]) {
            tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }
    }
}

What it does different from ordinary selection sort is that it makes unnecessary swaps back and forth from the ith place. The ordinary selection sort finds the minimum index and does only one swap for each element:

for (i = 0; i < MAX; i++) {
    int min = i;
    for (j = i + 1; j < MAX; j++) {
        if (data[min] > data[j]) {
            min = j;
        }
    }

    tmp = data[min];
    data[min] = data[i];
    data[i] = tmp;
}

Nevertheless, the original matches the description of selection sort (and the running time is the same, though constants are worse due to unnecessary swapping) in that:

The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order)

is realized as the algorithm finds the smallest element in the unsorted sublist, exchanging the current smallest item with the leftmost unsorted item as it goes over the list.

The C standard library already contains qsort which can be used instead of reinventing the wheel - we just need to write the comparison function:

#include <stdlib.h>

int compare_ints(const void *a, const void *b) 
{
    return (*(const int*)a - *(const int*)b);
}

int main(void) {
    ...
    qsort(data, MAX, sizeof(int), compare_ints);
    ...
}

edited Mar 1, 2017 at 7:29

answered Mar 1, 2017 at 5:48

Antti Haapala

135k23 gold badges297 silver badges349 bronze badges

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

3 Comments

StoryTeller - Unslander Monica Over a year ago

It's not selection sort. The OPs code doesn't match the pseudo on wikipedia, for one

Antti Haapala Over a year ago

@StoryTeller true, but it isn't bubblesort either. This is a selectionsort with unnecessary swapping, so the i value is swapped back and forth - if one keeps track of the smallest value instead then this will have much less swaps.

StoryTeller - Unslander Monica Over a year ago

Better. Much better.

Lrrr · Accepted Answer · 2017-03-01 05:31:03Z

1

No it wouldn't loop because you'll just swap the data[i] with data[i] twice although it is better to rewrite this piece of code like this :

for(i=0; i<MAX-1; i++){
    for(j=i+1; j<MAX; j++){
        if(data[i] > data[j]){
            tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }
    }
}

but this two code are same.

the algorithm that this codes are using is bubble sort. If you want to have better understanding of what it does take a look at the wikipedia article.

answered Mar 1, 2017 at 5:31

Lrrr

4,8055 gold badges44 silver badges65 bronze badges

Comments

Nick Frost · Accepted Answer · 2017-03-01 05:29:09Z

0

This is a Bubble Sort. The gist of it is that it swaps any two adjacent values that it finds out of order, until all of the values are in order.

answered Mar 1, 2017 at 5:29

Nick Frost

4902 silver badges12 bronze badges

7 Comments

Antti Haapala Over a year ago

this isn't bubble sort.

StoryTeller - Unslander Monica Over a year ago

@AnttiHaapala - It is bubble sort, as evident by swapping immediately.

Antti Haapala Over a year ago

@StoryTeller It is selection sort with unnecessary swapping, but not bubblesort. Bubblesort always compares adjacent elements only.

StoryTeller - Unslander Monica Over a year ago

@AnttiHaapala - It's a bubblesort without an early halting flag. Inefficient, but bubblesort nonetheless.

Antti Haapala Over a year ago

@StoryTeller Bubblesort: "compares each pair of adjacent items and swaps them if they are in the wrong order". No, it is not. These facts are not up for discussion. I am right, you are wrong.

|

Adeetya Kulkarni · Accepted Answer · 2018-05-30 17:59:59Z

0

The code

for(i=0; i<MAX; i++){
        for(j=i; j<MAX; j++){
            if(data[i] > data[j]){
                tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
        }
    }

Will clearly not work as it is supposed to. It basically needs to compare each and every element of the array and sorts them. Basically a bubble sort with time complexity O(n^2).

Rather than j=i

It should be j=i+1

answered May 30, 2018 at 17:59

Adeetya Kulkarni

72 bronze badges

Collectives™ on Stack Overflow

C Basic Sort Algorithm

4 Answers 4

3 Comments

Comments

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related