Thread: Using quicksort and radix sort for an anagram program

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    28

    Question Using quicksort and radix sort for an anagram program

    I've been working on a program that takes a file of words (anagrams) and reads the words into a structure array. The structure contains two char arrays. A word that is read will be copied into both char arrays. Then the idea is to use quicksort on one of the char arrays (the one called signature) to sort each word's letters into alphabetical order, so each element of the structure array will have a word in one of it's char arrays, and the word's letters sorted in alphabetical order in the other. I am working up to using a radix sort on the entire structure array to sort the array by the corresponding signatures. To risk getting too far ahead of myself, the idea is that after everything is sorted, I will sort and print the words that share the same letters in the list of words in the file.

    My problem right now is implementing a quicksort algorithm. The program compiles, but when I run it, the output is on three lines when it should be on two, and the quicksort doesn't work quite that well. If I check a word toward the middle or the end of the structure array, the word array is sort of sorted when it shouldn't even be touched. I have no idea what I'm doing wrong. Please help me. The code is:
    Code:
    #include<stdio.h>
    #define key(A) (A)
    #define less(A, B) (key(A) < key(B))
    #define exch(A, B) {char t = A; A = B; B = t; }
    
    typedef struct {
    	char word[7];
    	char signature[6];
    } analg;
    
    void populate(analg *g);
    int partition(char a[], int l, int r);
    void quicksort(char a[], int l, int r);
    
    int main() {
    	analg h[106];
    	int i, j;
    	
    	populate(h);
    	for(i=0; i<106; i++)
    		quicksort(h[i].signature, 0, 5);
    	
    	
    	scanf("%d", &j);
    	printf("%s", h[j].word);
    	for(i=0; i<6; i++)
    		printf("%c", h[j].signature[i]);
    
    	return 0;
    }
    
    /* This function reads the words from list.dat and 
       stores them into an array.                       */
    void populate(analg *g) {
    	FILE *fp;
    	int i, j;
    	fp = fopen("list.dat", "r");
    	if(fp == NULL) {
    		printf("CANNOT OPEN FILE.");
    		return;
    	}
    	else {
    		for(i=0; fgets(g[i].word, 7, fp) && i<106; i++) {
    			for(j=0; j<6; j++) 
    				g[i].signature[j] = g[i].word[j];
    		}		
    	}
    
    	fclose(fp);
    	
    	return;
    }
    
    /*This function is used by quicksort.  It partitions 
      the array so quicksort can sort the array         */
    int partition(char a[], int l, int r) {
    	int i = l-1, j = r; char v = a[r];
    	for(;;) {
    		while(less(a[++i], v));
    		while(less(v, a[--j])) if (j==1) break;
    		if (i>=j) break;
    		exch(a[i], a[j]);
    	}
    	exch(a[i], a[r]);
    	return i;
    }
    
    /* This algorithm sorts the signature array in the 
       structure so the words' letters are sorted in 
       alphabetical order                               */
    void quicksort(char a[], int l, int r) {
    	int i;
    	if (r<=l) return;
    	i = partition(a, l, r);
    	quicksort(a, l, i-1);
    	quicksort(a, i+1, r);
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > My problem right now is implementing a quicksort algorithm.
    Do you know there is qsort() in stdlib.h
    Or do you have to write your own in this instance?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    28
    I have to write my own in this instance.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. the fastest algorthm to order?
    By ^DJ_Link^ in forum C Programming
    Replies: 20
    Last Post: 03-18-2004, 08:00 AM
  2. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 12:24 PM