Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

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

Posted on 2006-03-30
7
Medium Priority
?
256 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
*/
0
Comment
Question by:tjn92
7 Comments
 
LVL 11

Expert Comment

by:x4u
ID: 16339976
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
 
LVL 24

Expert Comment

by:fridom
ID: 16340099
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
 
LVL 3

Expert Comment

by:DineshJolania
ID: 16340864
You can use qsort from stdlib.h  file
Use  "scmp" function defined by "Friedrich"
qsort((void *)AddressBook,10,20,scmp);
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 23

Expert Comment

by:Siva Prasanna Kumar
ID: 16348942
Yes even i prefer you using qsort from stdlib,h as its efficent & fast.
0
 
LVL 23

Accepted Solution

by:
Siva Prasanna Kumar earned 2000 total points
ID: 16348955
else try out this link it will  be use ful.

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

Expert Comment

by:PaulCaswell
ID: 16350680
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
 

Author Comment

by:tjn92
ID: 16351872
Wow, thank you very much shivaspk.  That website worked perfectly. I found the exact code I needed for my program.
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

564 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question