February 9, 2019
Sorting an array using ArraySort, BubbleSort and QuickSort
Comments
(0)
February 9, 2019
Sorting an array using ArraySort, BubbleSort and QuickSort
I try to bend the internet to my will.
Newbie 34 posts
Followers: 24 people
(0)

I didn’t study Computer Science so when I read about sorting algorithms I know what they achieve but not really how they work. So I thought I’d have a go at two well known ones; Bubble Sort and Fast Sort.

Before I go any further, I should point out that I’ve never had to write my own sorting algorithm, the native ArraySort works perfectly well!

data = [5,-1,2,1,001,3,0,-4.10,-3,01,-2,-5,4];

result = data.sort("numeric");
// result: [-5,-4.1,-3,-2,-1,0,1,001,01,2,3,4,5]

or using a custom sorter function.

data = [5,-1,2,1,001,3,0,-4.10,-3,01,-2,-5,4]

function sorter(x,y) {
    if (x == y) {
        return 0;
    }
    return x < y ? -1 : 1;
}

result = data.sort(sorter);
// result: [-5,-4.1,-3,-2,-1,0,1,001,01,2,3,4,5]

As I’ve mentioned in previous posts about arrays, in ColdFusion, the default is to pass arrays by value, this means the original array is not mutated. However, if you enable this.passArrayByReference = true in ColdFusion or use Lucee then the array is passed by reference, so the original array is mutated. Just something to be aware of so you don’t end up with some nasty unexpected side-effects.

If you want to ensure the original array is not mutated, even when this.passArrayByReference = true, then simply do (using ColdFusion 2018 syntax):

result = data[::].sort("numeric");

or

result = data[::].sort(sorter);

If you’ve not seen the [::] syntax before, it was added in 2018 as a way to slice an array. As I’ve not given it a start, end or count parameter, it copies the whole array. If you’re not on ACF 2018, you could use data.duplicate().

You can stop reading now if all you wanted to know was how to sort an array of numbers in CFML.

Still here? OK. So one thing I found interesting about the result above is that the array values with the leading ‘0’ are preserved – for example 001 is unchanged in the result rather than being 1. However, the 4.10 is changed to 4.1. If I run the same code on Lucee the001 is changed to 1 and 4.10 is changed to 4.1.

Moving onto my attempts to implement a BubbleSort. First here’s how Wikipedia describes the process:

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

This is what I came up with (as I say don’t actually use this code – use ArraySort instead!).

function bubbleSort(a) {
    var size = a.len();
    if (size < 2) {
        return a;
    }
    // we need to keep looping until there is nothing left to sort
    var done = false;
    while(!done) {
        // until elements are moved assume done
        done = true;
        a.each(function(element, index) {
            // compare with the next and swap if needed
            if(index < size && element > a[index+1]) {
                a[index] = a[index+1];
                a[index+1] = element;
                done = false;
            }
        });
    }
    return a;
}

I found that surprisingly hard to write, but I think it satisfies the technique. Having written it though I can see why this can be slow to complete – although if the array happens to be in the correct order from the start it’ll be very fast!

Moving onto my attempts to implement a QuickSort. Here’s how Wikipedia describes the process:

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

The steps are:

  1. Pick an element, called a pivot, from the array.
  2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Here’s my attempt to implement it.

function quickSort(a) {
    var elements = a.len();
    if (elements < 2) {
        return a;
    }

    // find the middle index 
    var midPoint = floor(elements/2); 
    // use mid point value to compare against
    var midValue = a[midPoint];
    // remove mid point value from the array before comparing
    a.deleteAt(midPoint);

    // assign values based on if they are less than mid value
    var left = [];
    var right = [];
    for (var el in a) {
        if(el < midValue) {
            left.append(el);
        } else {
            right.append(el);
        }
    }

    // sort the left and right arrays
    var leftSorted = quickSort(left);
    var rightSorted = quickSort(right);
    
    // join the arrays back together
    var result = [];
    return result
        .append(leftSorted, true)
        .append(midValue)
        .append(rightSorted, true);
};

By splitting the array into two and sorting them independently you reduce the number of operations required. Of course the value at the midpoint may actually be at the higher or lower end of the range, in which case it needs to do more work.

I won’t be using either of these functions, but it was an interesting exercise and I feel I have a better understanding of how these things work so thought I’d post it.

0 Comments
Add Comment