current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 2 down vote favorite

The program is supposed to take a file, say data.dat, filled with a list of up to 320 words all less than or equal to 29 characters (30 with the null character) and add each of those words to a global array. Then I want to sort that list alphabetically with a bubble sort. I did so with the following function in its own file sort.c

#include "set.h"
#include "sortAndSearch.h"
#include <stdio.h>
#include <ctype.h>
#include <string.h>

void bubbleSort(char A[][30], int num) {
int i, j;
char temp[30];

for(i = 0; i < num; i++)
    for(j = 0; j < num-1; j++)
        if(strcmp(A[i], A[i+1]) > 0){
            //swap the two array elements
            strcpy(temp, A[j]);
            strcpy(A[j], A[j+1]);
            strcpy(A[j+1], temp);
        }
}

I need a set of unsigned ints

unsigned int Set[10];

to act as an index for the names array. So each unsigned int has 32 bits and there are 10 unsigned ints for a total of 320 bits and each bit will reference a word. I am unsure how to approach this part.

The end goal is to create functions to manipulate the sets. I feel like I can attack that myself if I can get the sorting and index down, as I've done something similar but without using character arrays. The contents of the header file set.h that defines the functions to be used follows

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

// defining new type(s)
typedef unsigned int Set[10];

// declaring global variable(s)
extern char names[320][30];

extern void setUnion(Set set1, Set set2, Set result);
extern void setIntersection(Set set1, Set set2, Set result);
extern void clearSet(Set set);
extern void add2Set(Set set, int value);
extern void deleteFromSet(Set set, int value);
extern int isMember(Set set, int element);
extern void printSet(Set);
extern int nameIsMember(Set set, char *);
extern void addName2Set(Set set, char *);
extern void deleteNameFromSet(Set set, char *);

And here are the contents of the header file sortAndSearch.h

void bubbleSort(char A[][30], int num);

int binarySearch(char A[][30], char *, int, int );
share|improve this question
    
Could you summarize what you need help with? –  Brendan Long Mar 23 '12 at 20:17
    
first thing is figuring out why bubble sort isnt sorting, then getting the words from names[320][30] to the unsigned int Set[10] –  manalishi Mar 23 '12 at 20:22
    
okay, I created the outer loop and the function sorts fine now. Top issue now is creating index. –  manalishi Mar 23 '12 at 20:37
    
In production code, I would recommend using fgets over scanf, and strncpy over strcpy, since the functions I recommend are safe in case somebody accidentally (or maliciously) puts a 50-character string in the file. You probably won't be docked points for using the unsafe functions, but it's still good practice. –  Adam Mihalcin Mar 23 '12 at 20:40
    
Your problem with the 'index' part is not clear and the contents of your header file set.h that you pasted is useless for us as it gives no information required to fix your 'index' problem. –  Blue Moon Mar 23 '12 at 20:51

4 Answers 4

up vote 4 down vote accepted

Your bubble sort is in fact not a bubble sort. It only makes a single pass over the array. You need to repeatedly pass over the array until you make a pass that does not result in a swap. At that point you know that your array is ordered.

My preferred bubble sort implementation has an outer do loop. The inner loop is just as you currently have. The outer loop terminates when the latest inner loop execution failed to swap any items.

Of course, I'd recommend using a better sorting algorithm in the long run, but this is probably a homework assignment.

share|improve this answer
    
Yep, its an assignment. All the specifics were given from prof in the header file. I keep reading that bubble sort is lame, but that's what we were told to use. –  manalishi Mar 23 '12 at 20:24
    
It's a fine teaching vehicle. And it's not completely trivial to implement as you have discovered. –  David Heffernan Mar 23 '12 at 20:25
    
People have preferred bubble sort implementations? lol ... sorry! –  Kaz Mar 23 '12 at 23:21
    
@kaz I was using bubble sort this week as an interview question. –  David Heffernan Mar 23 '12 at 23:22
    
Can't we all just forget that bubble sort was ever invented? –  Jeremy West Apr 2 at 13:31
up vote 2 down vote

Problem is with this part:

for(i = 0; i < num-1; i++)
        if(strcmp(A[i], A[i+1]) > 0){
            //swap the two array elements
            strcpy(temp, A[i]);
            strcpy(A[i], A[i+1]);
            strcpy(A[i+1], temp);
        }

There's supposed to be two loops for bubble sort! ;-) See here for example with integers.

share|improve this answer
    
Thanks. So I need an outer for loop to cycle through whatever num equals? That makes sense and I'm going to try. –  manalishi Mar 23 '12 at 20:25
    
I guess your problem is solved, rite? –  Blue Moon Mar 23 '12 at 20:44
up vote 1 down vote

The bubblesort is not implemented correctly. There should be an inner loop and an outer loop.

I am unclear about the purpose of a 320 bit set: It can't be used for sorting, or for much of anything other than each bit indicating some attribute of the array is true, like whether it is present, or contains a verb or something.

share|improve this answer
    
You are right, it is quite confusing. The best explanation I've been able to get was the 320 bit set is to act as an index so I can implement other functions to do things like set union, set intersection, clear the set, add to set, etc. –  manalishi Mar 23 '12 at 20:28
up vote 0 down vote

Would it be fair to summarise that the sorting of names is independent of the set operations?

As long as the names don't change, the set operations will work?

The operations you listed fall into these groups:

Straight set operations, it doesn't matter what they are a set of. They operate on a whole set at a time:

extern void setUnion(Set set1, Set set2, Set result);
extern void setIntersection(Set set1, Set set2, Set result);
extern void clearSet(Set set);

You could tackle these without worrying about what the set might mean, but youu will need some values i there to be able to code them or use them.

Set element operations, these manipulate a single bit in the set, and again don't much care what the bits represent:

extern void add2Set(Set set, int value);
extern void deleteFromSet(Set set, int value);
extern int isMember(Set set, int element);

This is a good place to start.

These operations map between the names and the set so need more stuff to work:

extern int nameIsMember(Set set, char *);
extern void addName2Set(Set set, char *);
extern void deleteNameFromSet(Set set, char *);

I am not sure what extern void printSet(Set); means, does it print the names which are in the set?

Okay, a set is 

unsigned int s[10];

to test a bit, we need to convert an int value to the index of an int, and the bit within the int. The simplest way is array index = (value/32), bit offset is (value%32). The compiler should do a good job of making this efficient, so don't worry about efficiency.

To get at a bit value in s: (s[(value/32)] & (1<<(value%32))

So do you understand the bit operators?

~ not
& and
| or
^ xor
<< left shift
>> right shift

They are the operations you will use to set, clear and change bits in the set.

share|improve this answer
    
Thanks! Yes, the sorting of names is independent of the set operations. First I need to read all the possible elements for the sets and place those char strings in an array with up to 320 locations. Then I sort the array in ascending order. Then I need to be able to find the char string associated with int X, done by accessing array element at index X. To go from string to index you must implement a recursive binary search function which should return either index where string is stored or -1 for not there at all. –  manalishi Mar 24 '12 at 1:11
    
@manalishi - that sounds coherent. I'd be likely write a simple programs to test the basic add2Set/deleteFromSet/isMember. If the sets were a few words,, it would be straightforward to intialise them statically int bits[3] = {0x00000001, 0x00000002, 0x00000004}; then do some simple operations on it. –  gbulmer Mar 24 '12 at 1:22
    
Alright thanks for the input, I'll do some testing like that. –  manalishi Mar 24 '12 at 1:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.