Insertion sort error occurring in a C program

Question

I am probably missing something simple here, but I was looking over some simple algorithms in C and have not been able to get the insertion sort in the code below to work. The bubblesort seems to work.

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


void bubbleSort(char *pStringPointers[], int size);
void insertionSort(char *pStringPointers[], int size);
void ArrayTest(char string[][100],int size);

void swap(char **pString1, char**pString2);

int main (int argc, const char *args[]){
    char *pStrings[]={"jeff", "bob","kelli","bill","joe"};
    char testArray[][100]={"jeff", "bob","kelli","bill","joe"};
    ArrayTest(testArray,5);
    
    insertionSort(pStrings, 5);
    
    
    return 0;
}


//Start Algorithms

void ArrayTest(char string[][100], int size){
    printf("\n\nIteration Start:\n");

    for (int i=0;i<size;i++){
        printf(":%s\n",string[i]);   
    }
    
}


//  Bubble Sort Start

void bubbleSort(char *pStringPointers[], int size){
    
    char unsorted=1;
    
    while(unsorted){
        unsorted=0;
        for(int i=1;i<size;i++){
            if(strcmp(pStringPointers[i-1],pStringPointers[i])>0)
            {
                swap(&(pStringPointers[i-1]), &(pStringPointers[i]));
                unsorted=1;
            }
        }
    }
    
}

//  Bubble Sort End


//  Insertion Sort Start

void insertionSort(char *pS[], int size){
    int i,j;
    
    for(i=1;i<size;i++){
        printf("\n\nIteration Start:\n");
        for (int i=0;i<size;i++){
            printf(":%s\n",pS[i]);   
        }
        char *temp2=pS[i];
        j=i-1;
        while(j>=0&&strcmp(pS[j],temp2)>0){
           
            swap(&(pS[i]),&(pS[j]));
            j--;
        }
        pS[j+1]=pS[i];
      
    }
}



//  Insertion Sort End


//End Algorithms

void swap(char **pString1, char **pString2){
    char *temp=*pString1;
    *pString1=*pString2;
    *pString2=temp;
}

What can I do to debug this?

Answer 1

You're not supposed to compare pS[i] and pS[j], but rather pS[j] and pS[j+1], since you're shifting up the old elements as you go to make room - the element to insert will always be next to the j-th one.

And pS[j+1] = pS[i]; shouldn't be there - you've already done the swapping.

That gives us something like this:

for(i = 1; i < size; i++){
    printf("\n\nIteration Start:\n");
    for (int j = 0; j < size; j++){
        printf(":%s\n", pS[j]);   
    }
    j = i-1;
    while(j >= 0 && strcmp(pS[j], pS[j+1]) > 0){
        swap(&(pS[j+1]), &(pS[j]));
        j--;
    }
}

Test.