Sorting algorithm not correctly sorting

Question

I am following the provided sorting algorithm:

INSERTION-SORT(A)
1 for j <- 2 to length[A]
2   do key <-A[j]
3     Insert A[j] into the sorted sequence A[1..j — 1].
4     i <- j — 1
5     while i > 0 and A[i] > key
6       do A[i + 1] <- A[i]
7           i <- i — 1
8     A[i + 1] <— key

Provided by Introduction to Algorithms by Cormen, I have attempted with the following:

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

#define MAXSIZE 6
void sorting(int (*A)[MAXSIZE]){
    int key;
    int i;
    size_t size = sizeof(*A)/sizeof((*A)[0]);
    for (int j = 1; j < size; j++){
        key = (*A)[j];
        i = j-1;
        do {
            (*A)[i+1] = (*A)[i];
            i--;
        }while(i > 0 && (*A)[i] > key);
        (*A)[i+1] = key;
    }
    for(int k = 0; k < size; k++){
        printf("\n%d", (*A)[k]);
    }
}

int main(void){
    int B[MAXSIZE] = {5, 2, 4, 6, 1, 3};
    int result;
    sorting(&B);
    return 0;
}

However, the output is not sorting correctly. Did I miss something with these steps?

Textbooks typically start array numeration from 1, not 0, like C. Also, you've used post-condition loop do { ... } while (...) instead of pre-condition loop used in the pseudocode. — yeputons
– yeputons, Commented Jan 3, 2023 at 23:06
@yeputons That would make sense, whats the difference in pre/post condition, would these produce separate results? — Emil11
– Emil11, Commented Jan 3, 2023 at 23:23
do { X } while (Y); means "do X while Y is held", and Y is checked after each iteration. In particular, at least one iteration is executed. while (Y) {X} means "while Y, do X", and Y is checked before each iteration. In particular, it's possible to have zero iterations. — yeputons
– yeputons, Commented Jan 3, 2023 at 23:34

chux · Accepted Answer · 2023-01-03 23:28:21Z

1

Code is errantly doing a do {} while when a while {} is needed.

Consider if the array was initially sorted. The first (*A)[i+1] = (*A)[i];messes up the array.

answered Jan 3, 2023 at 23:28

community wiki

chux

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

Comments

user20895764 · Accepted Answer · 2023-01-03 23:36:07Z

0

Arrays in C start with index 0 and elements are stored in positions 0 to n-1

for (int j = 1; j < size; j++){

You changed "while {}" which check before loop to "{} while", which check after loop, moving element without comparison.

        while(i >= 0 && (*A)[i] > key) {
            (*A)[i+1] = (*A)[i];
            i--;
        };

answered Jan 3, 2023 at 23:36

user20895764

1 Comment

Emil11 Over a year ago

i >= 0 seems to make everything sorted whereas i > 0 will skip the fist element in the array.

Collectives™ on Stack Overflow

Sorting algorithm not correctly sorting

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related