'Insertion sort error occurring in a C program
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?
Solution 1:[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.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|---|
Solution 1 | Bernhard Barker |