-
problem with sorting
Code:
#include<stdio.h>
#include<stdlib.h>
#define ARY_SIZE 500
#define RANGE 1000
#define TRUE 1
#define FALSE 0
int bldPerm (int randNos[]);
void printData(int data[], int size);
int insertionSort (int list[], int last);
int bubbleSort(int list[], int last);
int bubbleUp(int list[], int first, int last);
int selectionSort(int list[], int last);
int exchangeSmallest(int list[], int first, int last);
int main(void)
{
int randNos [RANGE];
bldPerm(randNos);
printData(randNos, ARY_SIZE);
return(0);
}
int bldPerm(int randNos[])
{
int i;
int randNo;
int haveRand[RANGE] = {0};
for(i = 0; i < RANGE; i++)
{
do
{
randNo = rand() % RANGE;
} while(haveRand[randNo]==1);
haveRand[randNo] = 1;
randNos[i] = randNo;
}
return(randNos[i]);
}
void printData(int data[], int size)
{
int i;
int ins;
int bbs;
int ss;
int ns;
for(i = 0; i < size; i++)
{
data[i];
ins = insertionSort(data, size - 1);
bbs = bubbleSort(data, size);
ss = selectionSort(data, size);
}
printf(" BUBBLE SELECTION INSERTION\n");
printf("FIRST SORT RANDOM NUMBERS %d %d %d\n", bbs, ss,
ins);
return;
}
int insertionSort(int list[], int last)
{
int current;
int walker;
int located;
int temp;
int counter = 0;
int A;
for(current = 1; current <= last; current++)
{
located = FALSE;
temp = list[current];
for(walker = current -1; walker >0 && !located;)
{
if(temp < list[walker])
{
list[walker +1] = list[walker];
walker--;
A = counter++;
}
else
{
located = TRUE;
}
list[walker+1] = temp;
}
}
return(A);
}
int bubbleSort(int list[], int last)
{
int current;
int B;
for(current = 0; current < last; current++)
{
B = bubbleUp(list, current, last);
}
return(B);
}
int bubbleUp(int list[], int current, int last)
{
int walker;
int temp;
int counterB = 0;
int B;
for(walker = last; walker > current; walker--)
{
if(list[walker] < list[walker -1])
{
B = counterB++;
temp = list[walker];
list[walker] = list[walker -1];
list[walker -1] = temp;
}
}
return(B);
}
int selectionSort(int list[], int last)
{
int current;
int C;
for(current = 0; current < last; current++)
{
C = exchangeSmallest(list, current, last);
}
return(C);
}
int exchangeSmallest(int list[], int current, int last)
{
int walker;
int smallest;
int tempData;
int counterS = 0;
int C;
for(walker = current + 1; walker <= last; walker++)
{
if(list[walker] < list[smallest])
{
C = counterS++;
smallest = walker;
}
tempData = list[current];
list[current] = list[smallest];
list[smallest] = tempData;
}
return(C);
}
This is my code and the random array is to go through three different sorts and the end results is the number of time the array went through the sort. The only problem is I am not getting a number for the bubble sort. Can anyone help.
thanks.
-
A couple of potential problems in your code...
In the bubleUp function, B is declared but under certain conditions it may not be defined. Thus, the possibility exists that bubbleUp may return garbage. In the exchangesmallest function, the smallest variable is declared but not defined before using it in the loop. Also, there exists conditions where C may not be defined prior to returning it to the calling function.
Code:
int bubbleUp(int list[], int current, int last)
{
int walker;
int temp;
int counterB = 0;
int B;
for(walker = last; walker > current; walker--)
{
if(list[walker] < list[walker -1])
{
B = counterB++;
temp = list[walker];
list[walker] = list[walker -1];
list[walker -1] = temp;
}
}
return(B);
}
int exchangeSmallest(int list[], int current, int last)
{
int walker;
int smallest;
int tempData;
int counterS = 0;
int C;
for(walker = current + 1; walker <= last; walker++)
{
if(list[walker] < list[smallest])
{
C = counterS++;
smallest = walker;
}
tempData = list[current];
list[current] = list[smallest];
list[smallest] = tempData;
}
return(C);
}
-
Just an afterthought... Shouldn't your bubbleUp look something like this....
Code:
int bubbleUp(int list[],int current, int last)
{
int counterB = 0;
int B =0 ;
int walker, j, temp;
for (walker = (last - 1); walker >= current; walker--)
{
for (j = 1; j <= walker; j++)
{
if (list[j-1] > list[j])
{
B = counterB++;
temp = list[j-1];
list[j-1] = list[j];
list[j] = temp;
}
}
}
return(B);
}
Also, why do you repeatedly call the bubbleSort?
Code:
for(i = 0; i < size; i++)
{
data[i];
ins = insertionSort(data, size - 1);
bbs = bubbleSort(data, size);
ss = selectionSort(data, size);
}
The array should be sorted in ascending order (bubble up) during the first call and the number of swaps will be returned in B. Any additional calls to the bubble sort will not sort anything since the first call sorted the array in ascending order. Thus, B will alway be equal to zero on subsequent calls.