CODEWITHSUNDEEP
calgorithm
Emil11
Emil11

Reputation: 199

Sorting algorithm not correctly sorting

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?

Upvotes: 0

Views: 101

Answers (2)

user20895764
user20895764

Reputation:

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--;
        };

Upvotes: 0

chux
chux

Reputation: 153458

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.

Upvotes: 1

Related Questions