What do you think about my sort algorithm?

[48bpfSEw]

I look forward to your feedback!

/*====================================================
  Projekt   : Sort Algorithm
  Codename  : Pharao (of its pyramide formation)
  Programmer: Necip                         07.07.2016
  ====================================================
  Description
  ===========
  
  Given an array of n integers: 9 8 7 6 5 4 3 2 1 0
  
  Compare pairs starting with index 0, step 2
  
  9 8 7 6 5 4 3 2 1 0
  8 9 6 7 4 5 2 3 0 1
  
  Compare pairs starting with index 1
  
  8 9 6 7 4 5 2 3 0 1
    6 9 4 7 2 5 0 3

  Compare pairs starting with index 2

    6 9 4 7 2 5 0 3
      4 9 2 7 0 5

  and so on. 
  
  Then start again comparision with index 0.
  Sorting is finished if no swaping occured.


  This is the hole cyles of comparisons of this example:

  9 8 7 6 5 4 3 2 1 0
  8 9 6 7 4 5 2 3 0 1
    6 9 4 7 2 5 0 3  
      4 9 2 7 0 5    
        2 9 0 7      
          0 9        
                      
  new cyle
  
  8 6 4 2 0 9 7 5 3 1
  6 8 2 4 0 9 5 7 1 3
    2 8 0 4 5 9 1 7
      0 8 5 4 1 9 
        5 8 1 4
          1 8
          
  new cyle
  
  6 2 0 5 1 8 4 9 7 3
  2 6 0 5 1 8 4 9 3 7
    0 6 1 5 4 8 3 9
      1 6 4 5 3 8
        4 6 3 5
          3 6
          
  new cyle
  
  2 0 1 4 3 6 5 8 9 7
  0 2 1 4 3 6 5 8 7 9
    1 2 3 4 5 6 7 8
      2 3 4 5 6 7       finished
     
  result
  
  0 1 2 3 4 5 6 7 8 9
     
  ====================================================
  History log
  
  07.07.2016  - First concept
  
====================================================*/



#include <iostream>
#include <string>

/*
 * Sort algorithm, recursive
 */
void sort(
  int*  aValues, 
  int   iCount,  
  int   iCurrentStartIndex, 
  int   iCurrentEndIndex) {

  if (iCurrentStartIndex >= iCurrentEndIndex) {
    // Start next cyle
    sort (aValues, iCount, 0, iCount-1);
    return;
    }
    
  bool boSwap = false;
  for (int i=iCurrentStartIndex;i<=iCurrentEndIndex;i+=2) {
    if (aValues[i] > aValues[i+1]) {
      int iValueTmp = aValues[i];
      aValues[i  ] = aValues[i+1];
      aValues[i+1] = iValueTmp;
      boSwap = true;
      }
    }
  
  if (!boSwap)
    return;
  
  // sort next level
  sort (aValues, iCount, iCurrentStartIndex +1, iCurrentEndIndex -1);  
}

/*
 * dump array content
 */
void dump(int* aValues, int iCount) {
  for (int i=0;i<iCount;i++)
    std::cout << aValues[i];
  std::cout << std::endl;
}

/*
 * MAIN
 */
int main(void) {
  
  int  MAX          = 10;
  int  aValues[MAX] = {9,8,7,6,5,4,3,2,1,0};
  
  dump (aValues, MAX);
  sort (aValues, MAX, 0, MAX-1);
  dump (aValues, MAX);
  
  return 0;
}

[48bpfSEw]

My next task is to visualize the sorting like on this video: https://www.youtube.com/watch?v=kPRA0W1kECg

[48T7M4Gy]

Looking good and the video is something to look forward to, maybe a spiral instead of linear output?. However I think your program needs a little more work:

1111211111
1111111211

1101211111
1011111211

And this one which might be a bit unfair on you:
1-1012111-11
-1011-111211

:)

[48bpfSEw]

Hi Kemort, thank you for the review! ^^

debugging...

[48T7M4Gy]

OK :)

[48bpfSEw]

2 test cases successfull

dump: 1111211111
dump: 1111111112

dump: 1-1012111-11
dump: -1-101111112

/*====================================================
  Projekt   : Sort Algorithm
  Codename  : Pharao (of its pyramide formation)
  Programmer: Necip                         07.07.2016
  ====================================================
  Description:
  
  Given an array of n bytes 9 8 7 6 5 4 3 2 1 0
  
  Compare pairs starting with index 0, step 2
  
  9 8 7 6 5 4 3 2 1 0
  8 9 6 7 4 5 2 3 0 1
  
  Compare pairs starting with index 1
  
  8 9 6 7 4 5 2 3 0 1
    6 9 4 7 2 5 0 3

  Compare pairs starting with index 2

    6 9 4 7 2 5 0 3
      4 9 2 7 0 5

  and so on. 
  
  Then start again comparision with index 0.
  Sorting is finished if no swaping occured.

  This is the hole cyles of comparisons of this example:

  9 8 7 6 5 4 3 2 1 0
  8 9 6 7 4 5 2 3 0 1
    6 9 4 7 2 5 0 3  
      4 9 2 7 0 5    
        2 9 0 7      
          0 9        
                      
  new cyle
  
  8 6 4 2 0 9 7 5 3 1
  6 8 2 4 0 9 5 7 1 3
    2 8 0 4 5 9 1 7
      0 8 5 4 1 9 
        5 8 1 4
          1 8
          
  new cyle
  
  6 2 0 5 1 8 4 9 7 3
  2 6 0 5 1 8 4 9 3 7
    0 6 1 5 4 8 3 9
      1 6 4 5 3 8
        4 6 3 5
          3 6
          
  new cyle
  
  2 0 1 4 3 6 5 8 9 7
  0 2 1 4 3 6 5 8 7 9
    1 2 3 4 5 6 7 8
      2 3 4 5 6 7       finished, Ticket #1 : it may not be finished!
                                              all levels has to be run down!
     
  result
  
  0 1 2 3 4 5 6 7 8 9
     
  ====================================================
  History log
  
  07.07.2016  - First concept
  07.07.2016  - #Ticket 1
                Sorting failed for sequence 1111211111
                                    result  1111111211
                                    correct 1111111112
                                    
====================================================*/
// #define DEBUG_MODE 


#include <iostream>
#include <string>

/*
 * dump array content
 */
void dump(int* aValues, int iCount) {
  std::cout << "dump: ";
  for (int i=0;i<iCount;i++)
    std::cout << aValues[i];
  std::cout << std::endl;
}

/*
 * Sort algorithm, recursive
 */
void _sort(
  int*  aValues, 
  int   iCount,  
  int   iCurrentStartIndex, 
  int   iCurrentEndIndex,
  bool& boSwap) {

#ifdef DEBUG_MODE 
  std::cout << "sort entered" << std::endl;
  
  std::cout << "iCount: " << iCount << std::endl
            << "iCurrentStartIndex: " << iCurrentStartIndex << std::endl
            << "iCurrentEndIndex: " << iCurrentEndIndex << std::endl;
#endif
  
  // break criteria of the recursion
  if (iCurrentStartIndex >= iCurrentEndIndex)
    return;
    
  for (int i=iCurrentStartIndex;i<=iCurrentEndIndex;i+=2) {
    if (aValues[i] > aValues[i+1]) {
      int iValueTmp = aValues[i];
      aValues[i  ] = aValues[i+1];
      aValues[i+1] = iValueTmp;
      boSwap = true;
      }
    }
  
#ifdef DEBUG_MODE   
  dump (aValues, iCount);  
  std::cout << "start next level" << std::endl;
#endif

  // sort next level
  _sort (aValues, iCount, iCurrentStartIndex +1, iCurrentEndIndex -1, boSwap);  
}

  
/*
 * sort main entry
 */
void sort(
  int*  aValues, 
  int   iCount,  
  int   iCurrentStartIndex, 
  int   iCurrentEndIndex) {

  bool boSwap;
  do {
    _sort (aValues, iCount, iCurrentStartIndex, iCurrentEndIndex, boSwap=false);
    } while (boSwap);
  }
  
/*
 * MAIN
 */
int main(void) {
  
  const int MAX          = 10;
  int  aValues[MAX];
    
  // #Ticket 1: Test 1 successfull
  // aValues[0] = 1;
  // aValues[1] = 1;   
  // aValues[2] = 1; 
  // aValues[3] = 1;
  // aValues[4] = 2;
  // aValues[5] = 1;
  // aValues[6] = 1;
  // aValues[7] = 1;
  // aValues[8] = 1;
  // aValues[9] = 1;  
 
  // #Ticket 1 : Test 2 successfull
  aValues[0] = 1;
  aValues[1] = -1;   
  aValues[2] = 0; 
  aValues[3] = 1;
  aValues[4] = 2;
  aValues[5] = 1;
  aValues[6] = 1;
  aValues[7] = 1;
  aValues[8] = -1;
  aValues[9] = 1;  

 
  dump (aValues, MAX);
  sort (aValues, MAX, 0, MAX-1);
  dump (aValues, MAX);
  
  return 0;
}

[48T7M4Gy]

LOL, excellent now where's the next stop? Merge sort maybe?

PS keep all the test data sets and make sure all the various sorts get a going over with them. :)

Maybe make up a test data file and read them in. A bit of time to setup but fast in the long run. And easy to edit as you build up more tricky cases. OR design a data generator. Up to you of course.

[48bpfSEw]

Hi, I was focused on how to visualize the sorting history. This is what I get with LibreOffice Excel:

https://dl.dropboxusercontent.com/u/13592949/cpp/Pharao%20Sort%20Algorithm/Pharao%20Sort%20Pattern.ods

https://dl.dropboxusercontent.com/u/13592949/cpp/Pharao%20Sort%20Algorithm/DataVisualisationSortPharao.png

I test a lot in the office, so I am a little bit tired about test scenarios... ^^
In my spare time I like to be lazzy and like to debug-on-demand! ^^

One of the next steps is to globalify the comparison with lambda functions and metafy or abstraction of the fixed integer - array. The sort-algorithm should be able to sort any type of data... even pictures and sounds ... or thinking beyond the box : beliefs, considerations, decisions...

[48T7M4Gy]

I like the second graphic especially.

It's obviously your call how you go about testing. It would drive me up the wall producing test data sets because I would be more interested in the (graphic outcome) but there you go. The only purpose of the test scenarios is to make sure the program does what it is supposed to do as you know.

Go for the abstract items sort. All you have to do is work out a comparator algorithm for each I suppose. Beliefs will be a challenge I suspect. Decisions comparison technology is well established and pictures smacks of face recognition. But who knows, your's might be a new idea altogether. :)

[doug4]

Does the algorithm work with an odd number of elements? It looks like the last element will never be checked.

Also, I would not use name in the global namespace that is preceded with a single underscore. These names are reserved for the compiler. (http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier)

[48bpfSEw]

@kemort: comparing beliefs is a challenge. for example christs belief in one god, but buddhist beliefs in many gods. which belief is "greater" or "less" or "equal"? In this case we need a special compare-algorithm I think which merges both beliefs ... *thinkig* ... but this would be not a comparison, it would be a fusion. ok, forget it. beliefs can not be compared. *throw exception!* ^^

@doug4: there is a bigger problem with my logic: stack overflow! It works only for a little amount of numbers. This just an experiment.

[48T7M4Gy]

@Necip Well, it's probably outside the scope of a C++ forum but I think it is safe to say there is a broader perspective and philosophy (et al) deals with comparative beliefs, moral and ethics as a major cornerstone of its daily deliberations and for at least the last 100,000 years or so. ( On a sombre note we kill each other by the thousand on the 'comparisons' as we speak, on the basis that person A claims their beliefs are sufficiently better to justify killing Person B. ) Possibly more interesting and definitely more complex than int main() etc

http://www.buddhanet.net/ans73.htm

[48bpfSEw]

@Kemort, programming has to do something with life and life contents such discussions too. We have to think about special things and things out of the scope to reach full understanding.

“Know the rules well, so you can break them effectively.” (Dalai Lama)

I have to withdraw my conclusion that it is not possible to compare beliefs. It is possible. Look at this scale http://www.universalconsciouspractice.bravepages.com/UCP_Chart.htm
Every individuum has an aproximately constant emotion and each emotion has a specific thought (belief). It is e.g. better to be angry than in fear. It is better to be bored than angry. and so on.

And the best of all : there is a spiritual technique to rise up on this scales. The technique is called UCP: www.universalconsciouspractice.bravepages.com/

Beliefing in "god" or which is the same a s"looking for a source out of owns responsibility" is found on the bottom of this scale. If one rises up he/she understands it's own nature... that he/she is the only one god in his/her universe.

The UCP technique is also very usefull to find bugs and for approvment:
what does the function now? what should the function do really? compare!
what could the function do in future or what sort of problems could occure in future? compare!

[48T7M4Gy]

@Necip
I'll have a look at your attachments and possibly get back to you, especially UCP.
You raise some interesting points about the relationship with software debugging.

I'm off for a while to see why I'm at the bottom of the scale and see no need to go higher.

Meanwhile if you get to compare philosophical thought I might suggest Kant vs Bentham as a start.

Cheers :)

[48bpfSEw]

This is the final sorting animation of my algo.:

https://necips8.files.wordpress.com/2016/07/pharaosort.gif

[48T7M4Gy]

I assume you ironed out all the bugs. Whatever, it looks good. What's next? :)

( PS: I looked at UCP, I'm aware of the ideas from elsewhere. Not for me but there you go. )

[doug4]

By the way, the word is spelled Pharaoh.

[48T7M4Gy]

It's the German spelling. :)

[48bpfSEw]

thank you!


A last word about UCP:

"The constant discipline of comparing builds the ability to view
two viewpoints, pictures, etc., at the same time. This forces
them OUT of the picture they have been IN, and gets them to
adopt the viewpoint of the being who is looking AT the pictures.
This DIFFERENTIATES them from the pictures they have been
compulsively dramatizing, and are now self-determinedly viewing.

If their attention is on only one item, they can interiorize into it
and BE it. When they confront two pictures and compare, it is
very clear that they are neither one, but the viewer of pictures."


That means to me: I AM the problem if I focused myself to much into the problem and solving it is hardly possible. I have to distanciate myself from the problem to get a overview then I become the solver! This process keeps my mind calm... This remembers me to the poem of Kippling: http://www.poetryfoundation.org/poems-and-poets/poems/detail/46473


happy coding! ^^