C - Bubble sort array of character strings, then apply to unsigned int array

Question

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

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
– manalishi, Commented Mar 23, 2012 at 20:22
okay, I created the outer loop and the function sorts fine now. Top issue now is creating index. — manalishi
– manalishi, Commented Mar 23, 2012 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
– Adam Mihalcin, Commented Mar 23, 2012 at 20:40
The idea is to take the array names[320][30] and create an index of unsigned ints in an array Set[10]. Since there are 32 bits in each unsigned int, and 10 unsigned ints makes for 320 bits. 320 bits, 320 words. I need to setup a recursive binary search as defined in header file sortAndSearch.h. int binarySearch(char A[][30], char *, int ???, int ???); — manalishi
– manalishi, Commented Mar 23, 2012 at 20:56

David Heffernan · Accepted Answer · 2012-03-23 20:30:09Z

4

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.

edited Mar 23, 2012 at 20:30

answered Mar 23, 2012 at 20:16

David Heffernan

616k46 gold badges1.1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

manalishi Over a year ago

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.

David Heffernan Over a year ago

It's a fine teaching vehicle. And it's not completely trivial to implement as you have discovered.

Kaz Over a year ago

People have preferred bubble sort implementations? lol ... sorry!

David Heffernan Over a year ago

@kaz I was using bubble sort this week as an interview question.

Jeremy West Over a year ago

Can't we all just forget that bubble sort was ever invented?

|

P.P · Accepted Answer · 2012-03-23 20:17:04Z

2

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.

answered Mar 23, 2012 at 20:17

P.P

122k20 gold badges193 silver badges251 bronze badges

1 Comment

manalishi Over a year ago

Thanks. So I need an outer for loop to cycle through whatever num equals? That makes sense and I'm going to try.

wallyk · Accepted Answer · 2012-03-23 20:15:21Z

1

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.

answered Mar 23, 2012 at 20:15

wallyk

58.1k17 gold badges92 silver badges155 bronze badges

1 Comment

manalishi Over a year ago

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.

gbulmer · Accepted Answer · 2012-03-23 21:56:08Z

0

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.

answered Mar 23, 2012 at 21:56

gbulmer

4,30820 silver badges20 bronze badges

3 Comments

manalishi Over a year ago

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.

gbulmer Over a year ago

@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.

manalishi Over a year ago

Alright thanks for the input, I'll do some testing like that.

Collectives™ on Stack Overflow

C - Bubble sort array of character strings, then apply to unsigned int array

4 Answers 4

9 Comments

1 Comment

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

9 Comments

1 Comment

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related