We help IT Professionals succeed at work.

I have a program that I need to correctly implement quicksort in to sort last names in ascending order.

tjn92
tjn92 asked
on
Medium Priority
270 Views
Last Modified: 2010-08-05
Hi this is the code I have so far.  I have the commands 1, 2, and 3 completely done, but I can not seem to write a quicksort/partition set of functions to sort by last name in ascending order.  There is and example input/output sequence at the bottom.

 This program provides an address book with the following functionality
        1.      Add an entry
      2.      Import entries from a file
      3.      Print entry given index
      4.      Sort using Quicksort

       Assumption - All names are of at most 20 characters.
*/

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include "stdafx.h"

#define ADDRESS_BOOK_SIZE 10
char AddressBook[10][20];

int Count = 0;

void printAddressBook();
void print(int index);

int main()
{
      int command = 0;
      printf("Welcome to your electronic address book!\n\n");
      
      while(command != 5)
      {
            printf("\t1. Add an entry\n");
            printf("\t2. Import entries from a file\n");
            printf("\t3. Print entry given index\n");
            printf("\t4. Sort using Quicksort\n");
            printf("Select a command: ");
            scanf("%d", &command);
            
            switch (command)
            {
                  case 1: // Adding an entry
                  {
                        if (Count < ADDRESS_BOOK_SIZE)
                        {
                              printf("Enter name (Last, First): ");
                              getchar();
                              fgets(AddressBook[Count++], 20, stdin);
                              strtok(AddressBook[Count - 1],"\n");
                              printf("\n");
                        }
                        else
                              printf("Address Book full!\n\n");
                        break;
                  }
                  
                  
                  case 2: // Importing from a file
                  {
                        char filename[20] = "";
                        FILE *fp = NULL;
                        printf("\nEnter the filename to import: ");
                        scanf("%s", filename);
                        fp = fopen(filename, "r");
                        if (fp != NULL)
                        {
                              while (!feof(fp) && Count < ADDRESS_BOOK_SIZE)
                              {
                                    char tempName[20] = "";
                                    fgets(tempName, 20, fp);
                                    if (strcmp(tempName,"") != 0)
                                    {
                                          strcpy(AddressBook[Count++],tempName);
                                          strtok(AddressBook[Count - 1],"\n");
                                    }
                              }
                              printAddressBook();
                        }
                        else
                        {
                              printf("Unable to open file\n\n");
                        }
                        break;
                  }
                  case 3: // Printing given index
                  {
                        int indexToPrint = 0;
                        printf("\nEnter index to print: ");
                        scanf("%d",&indexToPrint);
                        print(indexToPrint);
                        break;
                  }
                  case 4: // Sorting using Quicksort
                  {
                  
                  }
      
                  default:
                  {
                        printf("Invalid choice\n");
                  }
            }
      }

      return 0;
}

/* Helper functions */

/* prints a given index */
void print(int index)
{
      if (index > 0 && index <= Count)
      {
            printf("\n[%d] %s\n\n", index, AddressBook[index - 1]);
      }
      else
      {
            printf("Index not found!\n\n");
      }

}

void quicksort

int partition


/* Debugging function - print entire address book */

void printAddressBook()
{
      int i;
      for (i = 0; i < Count; i++)
      {
            printf("[%d] %s\n", i + 1, AddressBook[i]);
      }
      printf("\n");
}

/*
Welcome to your electronic address book!

1.      Add an entry
2.      Import entries from a file
3.      Print entry given index
4.      Sort using Quicksort
Select a command: 2

Enter the filename to import: addresses.csv

[1] Smart, Suzie
[2] Student, John
[3] Zimmerman, Betty
[4] Al, Bert
[5] Bean, Joe

1.      Add an entry
2.      Import entries from a file
3.      Print entry given index
4.      Sort using Quicksort
Select a command: 4

[1] Al, Bert
[2] Bean, Joe
[3] Smart, Suzie
[4] Student, John
[5] Zimmerman, Betty

1.      Add an entry
2.      Import entries from a file
3.      Print entry given index
4.      Sort using Quicksort
Select a command: 3

Enter index to print: 7
Index not found!

1.      Add an entry
2.      Import entries from a file
3.      Print entry given index
4.      Sort using Quicksort
Select a command: 3

Enter index to print: 2

[2] Bean, Joe
*/
Comment
Watch Question

x4u

Commented:
As far as I can see you haven't implemented any Quicksort function yet.
You can find some information about quicksort and how to implement it in Wikipedia: http://en.wikipedia.org/wiki/Quicksort
There is also a example implemenation for C at the end of the page that only needs to be adapted for strings in your case.
fridomCEO/Programmer
CERTIFIED EXPERT

Commented:
you don't have to implement Quicksort you have to use it. So the only thing one has to write is an implementation of the compare functions simply using strcmp would be enough in this case.

the only problem would be the filtering out of the last name. There is not direct access on it if you have something like. And the other proble is that have to sort on an array of elements. so you have to be careful about the number of indirections.

Here is a a suggestion for the compare function:
int scmp (const void* s1, const void* s2){
  char **v1 = s1; // *(char**) s1;
  char **v2 = s2; //*(char**) s2;

  return strcmp(*v1,*v2);
}


Foo Bar
and
Foo Baz then the later would be placed after Bar.



Regards
Friedrich
You can use qsort from stdlib.h  file
Use  "scmp" function defined by "Friedrich"
qsort((void *)AddressBook,10,20,scmp);
Siva Prasanna KumarPrincipal Solutions Architect
CERTIFIED EXPERT
Top Expert 2006

Commented:
Yes even i prefer you using qsort from stdlib,h as its efficent & fast.
Principal Solutions Architect
CERTIFIED EXPERT
Top Expert 2006
Commented:
else try out this link it will  be use ful.

http://www.java2s.com/Code/C/Data-Structure-Algorithm/Quick-sort.htm

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
Hi tjn92,

We cant help you a lot without your input. Are you supposed to implement quicksort yourself? Does it work now? Are we on the right track?

Paul

Author

Commented:
Wow, thank you very much shivaspk.  That website worked perfectly. I found the exact code I needed for my program.
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.