none
Sorting in descending order

    Question

  • Any thoughts to sort some chars in a string. Given a string s, sort from s[1]..s[4] as an example, or s[4]..s[6] or some idea like that.

    What I trying to do is sort the sting, characters l to r only leaving the rest untouched. The sort is done by a special proxy that has been validated by rote. At present it does not do anything.

    // descending order bubble sort
    string fixname(string s, int l, int r) {
     bool flag = true;
     char t;
     int len = r - l + 1;
     int last = len - 2;
     while ((last >= 0) && flag) {
      flag = false;
      for (int j = 0; j <= last; j++) {
       if (gt(s[j+1],s[j])) {
        t = s[j]; // swap
        s[j] = s[j+1];
        s[j+1] = t;
        flag = true;
       }
      last--;
      }
     }
     return s;
    }



    Developer http://contract-developer.dyndns.biz
    Sunday, August 17, 2008 7:16 PM

Answers

  • What is wring with it, it works. This code uses a swap function, too much code for a class for my unorthodox sort order. Bubble sort is adequate considering the filenames lingths are short.

    void swap(char * x, char * y) {
     char t;
     t = *x;
     *x = *y;
     *y = t;
    }

    // special sort order for chess piece rank
    bool gt(char x, char y) { // Q > R > B > N > P
     if (x == y) return false; // test for equal first
     if (y == 'p') return true; // remaining always bigger
     switch (x) {
      case 'p': return false;
      case 'n': return false;
      case 'b': if (y == 'n') return true; else return false;
      case 'r': if (y == 'q' || y == 'k') return false; else return true;
      case 'q': if (y == 'k') return false; else return true;
      case 'k': return true;
     }
     return false;
    };

    // descending order bubble sort
    string fixname(string s, int l, int r) {
     char t;
     int len = r - l + 1;
     if (len == 1) return s;
     if (len == 2) {
      if (gt(s[r],s[l])) swap(s[l],s[r]);
      return s;
     }
     for (int i = l; i <= r; i++) {
      for (int j = l; j < r; j++)
       if (gt(s[j+1], s[j])) {
        swap(s[j],s[j+1]);
       }
     }
     return s;
    }



    The coments are clear enough to see what is going on. To reuse the bubble sort replace the gt(...) with > descending or > for ascending. If you overload the < and > operators you can use the STL sort. My sort is simple, no point using the overhead and complexity of a class.





    Developer http://contract-developer.dyndns.biz
    Tuesday, August 19, 2008 5:07 PM

All replies

  • Hi,
    I asume that you need to sort the data based on the positions. You are given an array and the positions and you need to sort the data only between the given positions. If this is what you are expecting i can proptotype it as given below,

        string SortedData = SortData(string s, int l, int r);
    ...
        string SortData(string s , const int l, const int r)
        {
            std::list RawList =  GetDataToBeSorted(string s, int l, int r)< better to pass this list by reference >
            RawList.sort()//This will sort the data, you can use reverse iterator to get the data in other order if required.
            return (UpdateData(RawList,string s);
        }

    Please note that there are two methods called "GetDataToBeSorted" that you need to write to load the std::list and UpdateData that will load the data to string.

    Its actually upto you how you do it but i wanted to stress the fact that its always better to use the inbuilt sort method to do the job for you rather that writing logic to sort the data.

    Also to add on we can make modifications to the above code to get it work but really does not look good if you have the option of using STL.
    Monday, August 18, 2008 12:27 PM
  • Well after a few hours grinding away, I now have sonthing that works as expected, ugly but it works.
    First my function for an arbitray sort order

    // Q > R > B > N > P
    bool gt(char x, char y) { // x > y
     if (x == y) return false; // test for equal first
     if (y == 'p') return true; // remaining always bigger
     switch (x) {
      case 'p': return false;
      case 'n': return false;
      case 'b': if (y == 'n') return true; else return false;
      case 'r': if (y == 'q' || y == 'k') return false; else return true;
      case 'q': if (y == 'k') return false; else return true;
      case 'k': return true;
     }
     return false;
    };

    Then I kludged an old bubble sort algorithm to sort in descending order

    // descending order bubble sort
    string fixname(string s, int l, int r) {
     char t;
     int len = r - l + 1;
     if (len == 1) return s;
     if (len == 2) {
      if (gt(s[l],s[r])) {
       return s;
      } else {
       t = s[l];
       s[l] = s[r];
       s[r] = t;
       return s;
      }
     } // bubblesort 3 or more 
     for (int i = l; i < len; i++){
      for (int j = l; j < len; j++) {
       if (gt(s[j+1], s[j])) {
        t = s[j];
        s[j] = s[j+1];
        s[j+1] = t;
       }
      }
     }
     return s;
    }

    Notice the kludge for the case of 1 or two items to be sorted. The <algoritnm: swao dont work either.

    Lots of fun. When data is this funky I have no choice as the STL does not seems to have much that can help. Running time is an issue too. As more chars are added the volume of data generated mushrooms by 5x. Love that exp time growth.

    Developer http://contract-developer.dyndns.biz
    Monday, August 18, 2008 1:34 PM
  • Not sure if I understand your problem, but try this.

    #include <iostream>  //cout
    #include <string>       //string
    #include <algorithm> //sort, advance

    //to sort a string base on char as number
      std::string name = "abcdefghiabe";
      std::sort(name.begin(), name .end());
      std::cout << name << std::endl;

    //to sort in a range, you could use std::partial_sort or
    //be sure that 1 & 10 are under name.size()
      std::string name = "abcdefghiabe";
      std::string::iterator begin = name.begin();
      std::advance(begin, 1);
      std::string::iterator end = name.begin();
      std::advance(end, 10);
      std::sort(begin, end);
      std::cout << name << std::endl;

    //then if want a descending order
    template <class T>
        struct descendingOrder
        {
            bool operator() (const T value1, const T value2) const
            {
                return value2 < value1;
            }
        };
      std::string name = "abcdefghiabe";
      std::string::iterator begin = name.begin();
      std::advance(begin, 0);
      std::string::iterator end = name.begin();
      std::advance(end, name.size());
      std::sort(begin, end, descendingOrder<std::string::value_type>());
      std::cout << name << std::endl;


    Monday, August 18, 2008 3:41 PM
  • My comparator is more complicated, I had to use a special function as my sort order is extremely unorthodox.

    // K > Q > R > B > N > P

    That is sort order that is enforced by the gt function. The code I have works, its general, the fixname can work with arbitrary length strings for tweaking the filenames to the specificed sort order.

    Notice the bubble comparitor calls my unorthodox comparitor. Like I said, its unorthodox. No way to change the sorting in the STL I could see. Its set in stone.
    Developer http://contract-developer.dyndns.biz
    Monday, August 18, 2008 5:15 PM
  • It's not really set in stone. The STL give you the option.
    Here, we use the predicate descendingOrder.

    std::sort(begin, end, descendingOrder<std::string::value_type>()); 


    If you have an unorthodox sorting method, use your unorthodox predicate.

    std::sort(begin, end, gt); // where gt is exactly your function above 



    Using std::sort, help other programmer understand your code, less code and error.

    Mathieu

    Tuesday, August 19, 2008 11:21 AM
  • examning your code, i modified my module, problem is I get a crash running it? Thoughts?

    bool gt(char x, char y) { // x > y
     if (x == y) return false; // test for equal first
     if (y == 'p') return true; // remaining always bigger
     //cout << "switch entered" << endl;
     switch (x) {
      case 'p': return false;
      case 'n': return false;
      case 'b': if (y == 'n') return true; else return false;
      case 'r': if (y == 'q' || y == 'k') return false; else return true;
      case 'q': if (y == 'k') return false; else return true;
      case 'k': return true;
     }
     return false;
    };

    string fixname(string s, int l, int r) {
     string::iterator begin = s.begin();
     advance(begin, l);
     string::iterator end = s.end();
     advance(end, r);
     sort(begin,end,gt);
     return s;
    }








    Developer http://contract-developer.dyndns.biz
    Tuesday, August 19, 2008 3:01 PM
  • > string::iterator end = s.end();
    > advance(end, r);

    This is bogus.

    Also, to simplify your comparator, I suggest mapping P to 1, N to 2, B to 3, R to 4, Q to 5, and K to 6, and then comparing the mapped integers by greater-than.  Such logic will be far more robust and easier to understand than your complicated switch statement.
    Tuesday, August 19, 2008 5:04 PM
  • What is wring with it, it works. This code uses a swap function, too much code for a class for my unorthodox sort order. Bubble sort is adequate considering the filenames lingths are short.

    void swap(char * x, char * y) {
     char t;
     t = *x;
     *x = *y;
     *y = t;
    }

    // special sort order for chess piece rank
    bool gt(char x, char y) { // Q > R > B > N > P
     if (x == y) return false; // test for equal first
     if (y == 'p') return true; // remaining always bigger
     switch (x) {
      case 'p': return false;
      case 'n': return false;
      case 'b': if (y == 'n') return true; else return false;
      case 'r': if (y == 'q' || y == 'k') return false; else return true;
      case 'q': if (y == 'k') return false; else return true;
      case 'k': return true;
     }
     return false;
    };

    // descending order bubble sort
    string fixname(string s, int l, int r) {
     char t;
     int len = r - l + 1;
     if (len == 1) return s;
     if (len == 2) {
      if (gt(s[r],s[l])) swap(s[l],s[r]);
      return s;
     }
     for (int i = l; i <= r; i++) {
      for (int j = l; j < r; j++)
       if (gt(s[j+1], s[j])) {
        swap(s[j],s[j+1]);
       }
     }
     return s;
    }



    The coments are clear enough to see what is going on. To reuse the bubble sort replace the gt(...) with > descending or > for ascending. If you overload the < and > operators you can use the STL sort. My sort is simple, no point using the overhead and complexity of a class.





    Developer http://contract-developer.dyndns.biz
    Tuesday, August 19, 2008 5:07 PM