function readOnly(count){ }
Sign Up ›
Starting November 20, the site will be set to read-only. On December 4, 2023,
forum discussions will move to the Trailblazer Community.
Learn More

Browse by Topic
ShowAll Questionssorted byDate Posted
+ Start a Discussion
CRMfusion - GWCRMfusion - GW 

Sorting arrays

Any ideas on how to sort an array?

My plan is to build a bubble sort method but I'm not sure if it will eat up too many "script statements" on a large array.

GlennW
CRMfusion - GWCRMfusion - GW
FYI... I just build a quick bubble sort function and it works like a charm.  If anyone needs the code just drop me a line.

This should be a method of the array objects as the number of script statements needed for larger arrays could blow past the script before DML govenor.

glenn.wilson@crmfusion.com

FYI. Here is the code

/*************************************************************/
/*                                                           */
/* Method to sort a string array using a bubble sort         */
/*                                                           */
/*                                                           */
/*************************************************************/
public void BubbleSort(String[] inArray) {
    Boolean swapped = false;
   
    do {
        swapped = false;
        for (Integer i = 0; i < (inArray.size() - 1); i++){
            if (inArray[i] > inArray[i + 1]) {
                swap(inArray, i, i+1);
                swapped = true;
            } // if
        } // for
       
    } while (swapped == true);
} // method

/*************************************************************/
/*                                                           */
/* Method to swap 2 string array elements                    */
/*                                                           */
/*                                                           */
/*************************************************************/
private void swap(String[] inArray, Integer idx, Integer jdx) {
    String tempStr;
   
    tempStr = inArray[idx];
    inArray[idx] = inArray[jdx];
    inArray[jdx] = tempStr;
}

Message Edited by CRMfusion - GW on 03-07-2007 08:15 AM
Execute EZSAASExecute EZSAAS
To sort array of strings alphabetically, you could use JavaScript built-in sort() method on Array object.
 
Or, for other objects, e.g. numbers or custom objects etc.... write your own function that serves as "comparator" and pass this function to Array.sort() method as argument
sfdcfoxsfdcfox
GW... I like your BubbleSort method. However, it uses a lot of processing time. Let's take a look:

Code:
<<code for sort, as above>>
string[] s = new string[21];
s[0]='zieafa';
s[1]='ifeapi';
s[2]='uzpaea';
s[3]='azeaca';
s[4]='japwaa';
s[5]='qiufae';
s[6]='lpaife';
s[7]='ziefa';
s[8]='ifepi';
s[9]='uzpea';
s[10]='azeca';
s[11]='japaa';
s[12]='qiuae';
s[13]='lpafe';
s[14]='iefa';
s[15]='fepi';
s[16]='zpea';
s[17]='zeca';
s[18]='apaa';
s[19]='iuae';
s[20]='pafe';
BubbleSort(s);

When you run using this example data, you end up with the following runtime results:
Results:
INFO  - Cumulative resource usage:
INFO  - Number of SOQL queries: 0 out of 100
INFO  - Number of query rows: 0 out of 10000
INFO  - Number of DML statements: 0 out of 100
INFO  - Number of DML rows: 0 out of 10000
INFO  - Number of transaction control statements: 0 out of 20
INFO  - Number of script statements: 747
INFO  - Maximum heap size: 0 out of 1000000

 

This is a lot of code coverage for a 21-indice array. I sought to bring that number down so it can be used with larger arrays:

Code:
public void qsort(string[] inarray)
{ for(integer i1 = 0; i1 < inarray.size(); i1++)
  { // check for alphabetical
    while(i1 < inarray.size()-1 && inarray[i1] < inarray[i1+1])
    { i1++;
    }
    for(integer i2 = i1; i2 < inarray.size(); i2++)
    { if(inarray[i1] > inarray[i2])
      { swap(inarray, i1, i2);
      }
    }
  }
}

private void swap(String[] inArray, Integer i1, Integer i2) {
    String tmp;
  
    tmp = inarray[i1];
    inarray[i1] = inArray[i2];
    inArray[i2] = tmp;
}

 
This code checks each indice and locates the lowest value, then swaps it out over each pass, instead of moving it one indice down. However, it sometimes performs unnecessary swaps. The overall results of my sample were still fairly impressive.

Results:
INFO  - Cumulative resource usage:
INFO  - Number of SOQL queries: 0 out of 100
INFO  - Number of query rows: 0 out of 10000
INFO  - Number of DML statements: 0 out of 100
INFO  - Number of DML rows: 0 out of 10000
INFO  - Number of transaction control statements: 0 out of 20
INFO  - Number of script statements: 438
INFO  - Maximum heap size: 0 out of 1000000

 

As you can see, from the original 747 lines, it's now down to 438 lines. That's 58% of the original footprint, which is impressive. However, it's still very inefficient. Imagine running a list of 1000 items-- it would run to be extremely large, and might not complete successfully. So, I optimized a bit more and came up with the following code.

Code:
public void dsort(string[] inarray)
{ integer y = 0, z = inarray.size()-1;
  while(y < z)
  { integer min = y;
    integer max = z;
    for(integer i = y; i <= z; i++)
    { if(inarray[i] < inarray[min])
      { min = i;
      }
      if(inarray[i] > inarray[max])
      { max = i;
      }
    }
    triswap(inarray, y, z, min, max);
    y++;
    z--;
  }
}

private void triswap(string[] inarray, integer low, integer high, integer min, integer max)
{ string tmp = inarray[high];
  inarray[high] = inarray[max];
  inarray[max] = inarray[low];
  inarray[low] = inarray[min];
  inarray[min] = tmp;
}

 

I looked at it for a while and made sure it worked correctly, since it looks almost too good to be true. Then, I ran the code and tested it, and came up with some amazing results. After getting these results, I even had to doublecheck to see if the sort was finishing correctly. Here's why...

Results:
INFO  - Cumulative resource usage:
INFO  - Number of SOQL queries: 0 out of 100
INFO  - Number of query rows: 0 out of 10000
INFO  - Number of DML statements: 0 out of 100
INFO  - Number of DML rows: 0 out of 10000
INFO  - Number of transaction control statements: 0 out of 20
INFO  - Number of script statements: 167
INFO  - Maximum heap size: 0 out of 1000000

 

Amazing! I just went from 438 lines to only 167 lines, just by doubling up one loop... So, for the record, that translates to 22% of the original posted code, and 38% of my first attempt at a sorting algorithm. I hope someone finds this algorithm interesting and even useful. This algorithm does have dependencies on the order of the values (most algorithms do); even in a worst case scenario, it still uses less cycles than a brute-force method such as bubble sorting.

~ sfdcfox ~
CRMfusion - GWCRMfusion - GW
Very cool.

The greatest challenge we'll have in the development of APEC Code apps is managing the govenors and figuring out ways to cut the script calls to a minimum.  This will help cut that down significantly.

Cheers;
GlennW
mtbclimbermtbclimber
Can't recall when it was added but please use the standard sort() method on Lists for primitives.
TehNrdTehNrd
So I've been doing some testing on this and I either messed up my implementation of the code or there there is a bug with this sort algorithm.  I'm thinking bug because I just copied and pasted and then changed the data types to Integers.

With the algorithm above, here are the results I get:
Code:
Before:
844
3
14
37
51
51
123
340
14

After
3
340
123
51
51
37
14
14
844

Rather than dig through this code to find the error I decided to focus my time an creating a new, potentially better, sorting algorithm. After doing some research it seems like the quicksort algorithm is one of the better algorithms that isn't overly complicated. I have taken this algorithm and converted it to Apex. I must give credit where credit is due as I didn't come up with this all on my own but used this site ( http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html ) and don't worry the author has given permission to use this code in commercial and non-commercial applications so feel free to use it.

You can test the two algorithms by creating the class below and then entering these lines in the system log.
sortTest testing = new sortTESt('quick');
sortTest testing = new sortTESt('dsort');

The quick sort method seems pretty efficient but I plan to do more testing and will report back.


Code:
public class sortTEST{

    public sortTest(String sortType){
        if(sortType == 'quick'){
            doQuickSort();
        }else{
            doSort();
        }
    }
 
    public void doQuickSort(){
        List<Integer> numbers = new List<Integer>();
            
        numbers.add(844);
        numbers.add(3);
        numbers.add(14); 
        numbers.add(37); 
        numbers.add(51);
        numbers.add(51);
        numbers.add(123);
        numbers.add(340);  
        numbers.add(14); 
        
        for(Integer d : numbers){
            system.debug(d);
        }
        
        quicksort(numbers,0,numbers.size()-1);
               
        for(Integer d : numbers){
            system.debug(d);
        }
    }         
    
    public void quicksort(Integer[] a, Integer lo0, Integer hi0){
        Integer lo = lo0;
        Integer hi = hi0;
        
        if (lo >= hi) {
            return;
        }else if( lo == hi - 1 ) {
            if (a[lo] > a[hi]) {
                Integer T = a[lo];
                a[lo] = a[hi];
                a[hi] = T;
            }
            return;
        }

        Integer pivot = a[(lo + hi) / 2];
        a[(lo + hi) / 2] = a[hi];
        a[hi] = pivot;

        while( lo < hi ) {
            while (a[lo] <= pivot && lo < hi){
                lo++;
            }

            while (pivot <= a[hi] && lo < hi ){
                hi--;
            }
            
            if( lo < hi ){
                Integer T = a[lo];
                a[lo] = a[hi];
                a[hi] = T;
            }
        }
        
        a[hi0] = a[hi];
        a[hi] = pivot;
        
        quicksort(a, lo0, lo-1);
        quicksort(a, hi+1, hi0);
    }

 
    public void doSort(){
        List<Integer> numbers = new List<Integer>();
            
        numbers.add(844);
        numbers.add(3);
        numbers.add(14); 
        numbers.add(37); 
        numbers.add(51);
        numbers.add(51);
        numbers.add(123);
        numbers.add(340);  
        numbers.add(14); 
        
        for(Integer d : numbers){
            system.debug(d);
        }
        
        dsort(numbers);
               
        for(Integer d : numbers){
            system.debug(d);
        }
    }         
    
    public void dsort(Integer[] innumbers){ 
        Integer y = 0; 
        Integer z = innumbers.size()-1; 
        
        while(y < z){
            Integer min = y;
            Integer max = z;
          
            for(Integer i = y; i <= z; i++){ 
                
                if(innumbers[i] < innumbers[min]){
                    min = i;
                }
                
                if(innumbers[i] > innumbers[max]){
                    max = i;
                }
            }
            
            triswap(innumbers, y, z, min, max);
            y++;
            z--;
        }
    }
    
    private void triswap(Double[] innumbers, Integer low, Integer high, Integer min, Integer max){
        Integer tmp = innumbers[high];
        innumbers[high] = innumbers[max];
        innumbers[max] = innumbers[low];
        innumbers[low] = innumbers[min];
        innumbers[min] = tmp;
    }
}

 


Message Edited by TehNrd on 09-22-2008 09:40 AM
TehNrdTehNrd
The results are in!

I created a random List of 1000 Integers and then ran this quick sort about 10 times. The average number of script statements was near 25,000. This is the first algorithm that has actually allowed me to sort a full List of 1000 elements so I am happy.

One thing about this quicksort algorithm is that it sorts ascending. I will try to rework the code so you can enter an extra parameter to define ascending or descending sort order.  If successful I'll report back and post the code.

Code for creating a random Integer list:
Code:
for(Integer i = 0; i < 1000; i++){
    numbers.add(Math.round(Math.random() * 1000));
}




Message Edited by TehNrd on 09-22-2008 10:53 AM
TehNrdTehNrd
In response to Andrew's comment about using sort() on primitive data types:

I totally agree, use sort() on primitive data sets. The example I have supplied is providing a sort algorithm for a primitive data type but this could be easy converted to sort a list of sObjects. Lets say you had an List of Opportunities. Anywhere you see comparisons or the code referencing an index you would need to access the opp Amount:

while (a[lo] <= pivot && lo < hi){

you would change to:

while (a[lo].Amount <= pivot && lo < hi){

where 'a' is a list of opps.

-Jason



Message Edited by TehNrd on 09-22-2008 10:08 AM
XactiumBenXactiumBen
I decided to have a little play with this myself.  Instead of coming up with my own sort algorithm which would undoubtedly be very similar to everyone elses sorts, I came up with a method that uses the List.Sort() method on object fields.

Code:
public class sortTesting
{
    public static testMethod void testSorting()
    {
        List<Opportunity> opps = new List<Opportunity>();
        
        Opportunity current = null;
        for (integer x=0;x<1000;x++)
        {
            current = new Opportunity();
            current.Name = 'Opp ' + x;
            current.Amount = Math.round(Math.random() * 1000);
            opps.add(current);
        }
        
        List<Opportunity> sorted = null;
        System.debug(opps);
        
        System.Test.startTest();
        sorted = sortOpps(opps);
        System.Test.stopTest();
        
        System.debug(sorted);
    }
    
    
    public static Opportunity[] sortOpps(Opportunity[] oppList)
    {
        List<Decimal> myAmounts = new List<Decimal>();
        Map<Decimal, List<Opportunity>> oppMap = new Map<Decimal, List<Opportunity>>();
        for (Opportunity o : oppList)
        {
            myAmounts.add(o.Amount);
            
            if (!oppMap.containsKey(o.Amount))
            {
                oppMap.put(o.Amount, new List<Opportunity>());
            }
            oppMap.get(o.Amount).add(o);
        }
        
        myAmounts.sort();
        
        List<Opportunity> sortedOpps = new List<Opportunity>();
        for (Decimal i : myAmounts)
        {
            // Get the first opp 
            sortedOpps.add(oppMap.get(i).get(0));
            oppMap.get(i).remove(0);
            if (oppMap.get(i).size() == 0)
            {
                oppMap.remove(i);
            }
            continue;
        }
        
        return sortedOpps;
    }
}

 I basically put the values that want sorting into a seperate list, put the unsorted values into a map with the Key as the values I want sorting, and a list of Opportunities as the value.  I then sort my list of values to sort, then loop through the sorted values and get the Opportunities from the Map.

I tried this on 6 opportunities at first to see if they were successfully sorted, and it seemed to turn out well.  Next, I created 1000 opportunities and used those with the random number generator provided earlier in this thread.  This is what I got:

Testing resources:

Resource usage for namespace: (default)
Number of SOQL queries: 0 out of 100
Number of query rows: 0 out of 10000
Number of SOSL queries: 0 out of 20
Number of DML statements: 0 out of 100
Number of DML rows: 0 out of 10000
Number of script statements: 7006 out of 200000
Maximum heap size: 52418 out of 1000000
Number of callouts: 0 out of 10
Number of Email Invocations: 0 out of 10
Number of fields describes: 0 out of 10
Number of record type describes: 0 out of 10
Number of child relationships describes: 0 out of 10
Number of picklist describes: 0 out of 10
Number of future calls: 0 out of 10


Hope I did the System.Test.StartTest correctly to provide accurate results.  If not, here is what I got without using StartTest and StopTest:

Cumulative resource usage:

Resource usage for namespace: (default)
Number of SOQL queries: 0 out of 100
Number of query rows: 0 out of 500
Number of SOSL queries: 0 out of 20
Number of DML statements: 0 out of 100
Number of DML rows: 0 out of 500
Number of script statements: 11013 out of 200000
Maximum heap size: 52594 out of 500000
Number of callouts: 0 out of 10
Number of Email Invocations: 0 out of 10
Number of fields describes: 0 out of 10
Number of record type describes: 0 out of 10
Number of child relationships describes: 0 out of 10
Number of picklist describes: 0 out of 10
Number of future calls: 0 out of 10


Anyone else want to try this out?
TehNrdTehNrd
I just gave it a quick look over but what happens when there are two Opportunities with the same amount?

edit: Only one of the opps with the duplicate amount will make it to the returned list. So your returned list will actually be smaller that the list you sent for sorting.




Message Edited by TehNrd on 09-23-2008 12:59 PM
mtbclimbermtbclimber
I have a blog entry in draft around this which I think you'll find interesting (coming soon I hope).  The solution is along the lines of what XactiumBen was doing.
TehNrdTehNrd
Looking forward to this post! :smileyvery-happy:

Awhile ago I actually tried something similar to what  XactiumBen was doing where I would add something on the end of the amount to make it unique and then try to sort. The problem was this turned the list of Numbers into strings and the sort then doesn't work correctly.

-Jason




Message Edited by TehNrd on 09-23-2008 01:02 PM
XactiumBenXactiumBen
In answer to your previous question about duplicates, I use a List of Opportunities in my Map so it can store lots of Opportunities per unique key:

Code:
Map<Decimal, List<Opportunity>> oppMap = new Map<Decimal, List<Opportunity>>();

 
mtbclimbermtbclimber
As promised:

Link below should read: "Sorting collections in Apex and "Too many script statements"" instead of "Link:"

Sorting collections in Apex and "Too many script statements"
TehNrdTehNrd
XactiumBen wrote:
In answer to your previous question about duplicates, I use a List of Opportunities in my Map so it can store lots of Opportunities per unique key:


Whoops I totally overlooked that. Looks like Andrew's method is very similar but he uses the addAll() method.

I've done some testing on Lists of 1000 and with the custom quick sort method and it averages around 24,000 statements. With the cool standard sort it uses around 2,600. Very nice.

My next challenge, an efficient algorithm to add values to an already sorted list. I've describe how I would try that here but I have yet to actually code it. http://community.salesforce.com/sforce/board/message?board.id=Visualforce&message.id=5394#M5394 but depending on Andrew's next blog post I may not have to do this.


Message Edited by TehNrd on 09-25-2008 09:21 AM