Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

sorting strings

hani_hijhani_hij Posts: 7Member
how can i input strings through a file, and then sort them to a link list using insertion sort& quick sort, and then output the result to another file.
thanks for any one who helps ??

i really need it

Comments

  • HK_MP5KPDWHK_MP5KPDW Posts: 767Member ✭✭✭
    : how can i input strings through a file, and then sort them to a link
    : list using insertion sort& quick sort, and then output the result to
    : another file.
    : thanks for any one who helps ??
    :
    : i really need it
    :

    You are asking about three things: file i/o, linked lists, and sorting. Is there one in particular you need help with or all three? Note that linked lists are not really a suitable data structure for sorting using quick sort as it typically operates on a contiguous array. You could implement an insertion sort rather easily using linked lists. Does this need to be C or C++? Are you sure you wouldn't want to just use a C++ set container which could do what you wanted with just a few lines of code?
  • hani_hijhani_hij Posts: 7Member
    : : how can i input strings through a file, and then sort them to a link
    : : list using insertion sort& quick sort, and then output the result to
    : : another file.
    : : thanks for any one who helps ??
    : :
    : : i really need it
    : :
    :
    : You are asking about three things: file i/o, linked lists, and
    : sorting. Is there one in particular you need help with or all
    : three? Note that linked lists are not really a suitable data
    : structure for sorting using quick sort as it typically operates on a
    : contiguous array. You could implement an insertion sort rather
    : easily using linked lists. Does this need to be C or C++? Are you
    : sure you wouldn't want to just use a C++ set container which
    : could do what you wanted with just a few lines of code?


    i want to insert the input file componants to the link list and then sort it using the insertion sort, and put the componants of the input file into the quick sort without using link list, this is done using C++ language,and i don't want to use a C++ set container .
    thanks for help.


  • hani_hijhani_hij Posts: 7Member
    : : how can i input strings through a file, and then sort them to a link
    : : list using insertion sort& quick sort, and then output the result to
    : : another file.
    : : thanks for any one who helps ??
    : :
    : : i really need it
    : :
    :
    : You are asking about three things: file i/o, linked lists, and
    : sorting. Is there one in particular you need help with or all
    : three? Note that linked lists are not really a suitable data
    : structure for sorting using quick sort as it typically operates on a
    : contiguous array. You could implement an insertion sort rather
    : easily using linked lists. Does this need to be C or C++? Are you
    : sure you wouldn't want to just use a C++ set container which
    : could do what you wanted with just a few lines of code?


    why you didn't answer me?? is there any problem??????


  • bilderbikkelbilderbikkel Posts: 754Member
    : i want to insert the input file componants to the link list and then
    : sort it using the insertion sort, and put the componants of the
    : input file into the quick sort without using link list, this is done
    : using C++ language,and i don't want to use a C++ set
    : container .
    : thanks for help.
    :
    Check http://www.codepedia.com/1/CppInsertionSort for insertion sort and http://www.codepedia.com/1/CppFileIo for file I/O. I look forward to the more detailed questions this will generate :-).

    See ya,



    bilderbikkel
  • HK_MP5KPDWHK_MP5KPDW Posts: 767Member ✭✭✭
    : why you didn't answer me?? is there any problem??????
    :

    No problem, just trying to relax and enjoy my long holiday weekend by doing as little as possible.

    Are you at least able to use an STL [italic]list[/italic] container to store your information or are you hand coding your own list? What does the format of the input file look like? The best way to do this would be to keep your list sorted as you go along and not wait till the end to do it. Each string read from the file should be inserted into the list such that the list always remains sorted. This would involve finding the appropriate insertion point for each string. (The [italic]list[/italic] container also supports its own [italic]sort[/italic] member function.) What code do you have thus far?
  • hani_hijhani_hij Posts: 7Member
    : : why you didn't answer me?? is there any problem??????
    : :
    :
    : No problem, just trying to relax and enjoy my long holiday weekend
    : by doing as little as possible.
    :
    : Are you at least able to use an STL [italic]list[/italic] container
    : to store your information or are you hand coding your own list?
    : What does the format of the input file look like? The best way to
    : do this would be to keep your list sorted as you go along and not
    : wait till the end to do it. Each string read from the file should
    : be inserted into the list such that the list always remains sorted.
    : This would involve finding the appropriate insertion point for each
    : string. (The [italic]list[/italic] container also supports its own
    : [italic]sort[/italic] member function.) What code do you have thus
    : far?
    :




    This is my code, can you told me why it doesn't sort 100% correct?
    [color=Red]My input is:
    dubai
    abu dhabi
    sharjah
    ajman
    oman[/color]

    the code:
    #include
    #include
    #include
    #include

    const int names=30;const int lenght=100;
    char tmp [names][lenght];
    void QuickSort(char Arr[][100], int LowerIndex, int UpperIndex);
    int Divide(char Arr[][100], int LowerIndex, int UpperIndex);
    void insertionSort(char data[][100],int);


    int main(){
    //========================Input&Output=========================
    FILE * pFile;
    char string [100];

    pFile = fopen ("myInput.txt" , "r");

    if (pFile == NULL)
    cout<<"Error opening file"<<endl;
    else {
    for(int i=0;i<5;i++){
    fgets (string , 100 , pFile);
    strcpy(tmp[i],string);
    puts (string);

    }

    pFile = fopen ("myOutput.txt","w");
    fputs (string,pFile);

    fclose (pFile);
    }
    //=================Quick sort====================================
    cout<<"Sorting using Quick Sort "<<endl;
    QuickSort(tmp,0,6);
    for( int i=0;i<10;i++){
    cout<<tmp[i]<<endl;
    }
    cout<<"
    Sort Successfully Done!"<<endl;
    //================Insertion sort================================
    cout<<" Sorting by insertion sort"<<endl;
    insertionSort(tmp,20);
    for ( i = 0; i <100; i++){
    cout<<tmp[i];
    }


    return 0;
    }

    void QuickSort(char Arr[][100], int LowerIndex, int UpperIndex)
    {
    int Divider;

    if(LowerIndex < UpperIndex)
    {
    Divider = Divide(Arr, LowerIndex, UpperIndex);
    QuickSort(Arr, LowerIndex, Divider - 1); // left half
    QuickSort(Arr, Divider + 1, UpperIndex); // right half
    }
    else
    return;
    }
    /*---------------------------------------------------------*/
    int Divide(char Arr[][100], int LowerIndex, int UpperIndex)
    {
    char hold[100];
    int Divider;
    int Pivot = LowerIndex,First = LowerIndex + 1, Last = UpperIndex;
    while(First <= Last)
    {
    while((Arr[Pivot] >= Arr[First]) && (First <= UpperIndex) )
    First++;
    while((Arr[Last] >= Arr[Pivot]) && (Last >= First))
    Last--;

    if (strcmp(Arr[Last],Arr[First])==1)
    // if( First < Last)
    { strcpy(hold , Arr[Last]);
    strcpy(Arr[Last] , Arr[First]);
    strcpy(Arr[First] , hold);
    }

    } // end while


    if (strcmp(Arr[First],Arr[Last])==-1)
    { //if(Last < First)
    strcpy(hold , Arr[Last]);
    strcpy(Arr[Last] , Arr[Pivot]);
    strcpy(Arr[Pivot] , hold);
    }

    Divider = Last;
    return Divider;
    }
    /*---------------------------------------------------------*/
    void insertionSort(char data[][100],int n)
    {
    int i,j;
    char tmp[30];
    for(i=0;i0) && (strcmp(tmp,data[j-1])==-1)){
    strcpy(data[j],data[j-1]);
    --j;
    }
    data[j][30]=tmp[30];
    }

    }



  • bilderbikkelbilderbikkel Posts: 754Member
    I have been trying to help you, by first transforming the code to C++ so the problem might get more clear. The code does look strange when you look at it. Perhaps it does inspire you to find the error, if not, too bad.

    [code]
    #include
    #include
    #include
    //---------------------------------------------------------------------------
    int Divide(
    std::vector& v,
    const int lowerIndex,
    const int upperIndex)
    {
    const int pivot = lowerIndex;
    int first = lowerIndex + 1;
    int last = upperIndex;

    while(first <= last)
    {
    while(v[pivot] >= v[first] && first <= upperIndex ) ++first;
    while(v[last ] >= v[pivot] && last >= first ) --last;
    if (v[last] > v[first]) std::swap(v[first],v[first]);
    }
    if (v[first] < v[last]) std::swap(v[first],v[first]);

    const int divider = last;
    return divider;
    }
    //---------------------------------------------------------------------------
    void QuickSort(
    std::vector& v,
    const int lowerIndex,
    const int upperIndex)
    {
    if(lowerIndex < upperIndex)
    {
    const int divider = Divide(v, lowerIndex, upperIndex);
    QuickSort(v, lowerIndex, divider - 1); // left half
    QuickSort(v, divider + 1, upperIndex); // right half
    }
    }
    //---------------------------------------------------------------------------
    int main()
    {
    std::vector v;
    v.push_back("Richel");
    v.push_back("Bilderbeek");
    v.push_back("Pieter");
    v.push_back("Venema");
    v.push_back("Wietze");
    v.push_back("Brandsma");
    QuickSort(v,0,v.size());

    for (
    std::vector::const_iterator i = v.begin();
    i!=v.end();
    ++i)
    {
    std::cout << (*i) << std::endl;
    }
    std::cin.get();
    }
    //---------------------------------------------------------------------------
    [/code]

    See ya,
    bilderbikkel
Sign In or Register to comment.