• C

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

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
*/
tjn92Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

x4uCommented:
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.
0
fridomCEO/ProgrammerCommented:
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
0
DineshJolaniaCommented:
You can use qsort from stdlib.h  file
Use  "scmp" function defined by "Friedrich"
qsort((void *)AddressBook,10,20,scmp);
0
Making Bulk Changes to Active Directory

Watch this video to see how easy it is to make mass changes to Active Directory from an external text file without using complicated scripts.

Siva Prasanna KumarPrincipal Solutions ArchitectCommented:
Yes even i prefer you using qsort from stdlib,h as its efficent & fast.
0
Siva Prasanna KumarPrincipal Solutions ArchitectCommented:
else try out this link it will  be use ful.

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
PaulCaswellCommented:
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
0
tjn92Author Commented:
Wow, thank you very much shivaspk.  That website worked perfectly. I found the exact code I needed for my program.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.