Sorting algorithms

[Articron 738]

Tutorial on the sorting algorithms that are traditionally looked at quite early in a computer science education.
Useful for the people that study CS and struggle with the concepts, or people that are interested in algorithms in general.
 
Note: will add 1 algorithm / day until the list is finished
 
Sorting algorithms covered in this tutorial:

• Bubble sort
• Insertion sort
• Selection sort
• Quick sort
• Merge sort

1. The bubble sort
 
Complexity: O(N²)
 
Generally the bubble sort is the first algorithm that is introduced in CS. This is traditionally shown first in order to be able to point out how bad the bubble sort actually is down the road.
 
Assume the following array:

 
Procedure: The bubble sort compares each and every element in the array with its predecessor in the array (index -1).
If the predecessor is higher, the values are swapped. This ensures the highest value will always be on the right.
 
A visual representation, each row is 1 step:
 

 
Yellow = the predecessor
Blue = The focus value
 
In this part, you can already see the last 2 elements ordered after 2 rotations.
TL;DR to order a 10-element array, we'll have to iterate through the array / element (hence why its O(N²) ) 
N = 10 elements x 10 iterations = N²
 
Bubblesort code:

public void evaluateSort(int[] dataset)
    {
        int size = dataset.length;
        for (int i = 0; i < size; i++)
        {
            for (int x = 1; x < (size - i); x++)
            {
                if (dataset[x -1] > dataset[x])
                {
                    Arrays.swapValues(dataset,x,x-1);
                }
            }
        }
    }

2. The insertion sort
 
Complexity: O(N)
Note: worst case is still O(N²)
 
The insertion sort is essentially the same thing as traditional human beings do: We put them inbetween a value which is lower/equal than the number in our hand, and it preceeds a number HIGHER than the number in our hand. 
 
 

 
We just have to make sure that we move the elements that come AFTER the insertion, as their index will have to be increased by one.
 
A code implementation (commented for clarity):

private void evaluateSort(int[] dataset)
    {
        //Sequentially loop through the entire array
       for (int i = 1; i < dataset.length; i++)
       {
           int focusIndex = i - 1; //set the index to the first predecessor
           int currentValue = dataset[i]; //focus on the current looped element
           /*
            * Whilst there are still predecessors, and they're HIGHER, shift them
            */
           while (focusIndex >= 0 && dataset[focusIndex] > currentValue) {
               /* example procedure: {5,3,4,7}
               *  while 5 > 3
               *  3 index = 1 -1 = 0 => 3 is index 0, break loop
               */
               dataset[focusIndex + 1] = dataset[focusIndex--];
           }

           //we put the focus value after the focussed index (highest number below our focus)
           dataset[focusIndex + 1] = currentValue;
       }

    }

3. Selection sort
 
Complexity: O(N²)
 
Selection sorts are what you expect: They hook onto 1 array slot, and "select" which number belongs there. This value that must be selected is the lowest value that is still in the unordered (right) part of our array.
 

 
Green: ordered
Yellow: Unordered
First red character: the current slot
Second red character: the slot with the lowest value
 
As you can see, these values get swapped, creating an ordered array as it fills up.
 
The code implementation is quite simple as well:

private void evaluateSort(int[] dataset)
    {
        for (int i = 0; i < dataset.length; i++)
        {
            int low = i;
            for (int x = i; x < dataset.length; x++)
            {
                if (dataset[x] < dataset[low])
                {
                    low = x;
                }
            }
            Arrays.swapValues(dataset,i,low);
        }
    }

4. Quicksort
 
Average complexity: O(n log(n))
Worst case complexity: O(N²)
 
Here's where that good shit comes in. The algorithms we've seen prior to the quicksort, have been sequential and have had no need for things like recursion. 
The quicksort traditionally performs a lot better compared to a bubble/insertion/selection sort, as the amount of comparisons we make are considerably lower. 

A quicksort is a divide and conquer  principle'd algorithm. It partitions/divides array sectors based on something we call "the pivot".

Due to the quicksort being pretty difficult for most people picking it up first, I'll go through the motions step-by-step with you.
 
We will assume the following array:

 
Step 1: picking the pivot
 
For determining the pivot, you have two generally accepted options:

• Calculating the meridian of all the values of your current sector (as this is step 1, our full array = the sector)
• Picking the middle index of your sector

For the sake of simplicity, we'll just pick the middle index. (This is either index 4, or index 5)
 
We pick 4 as our pivot:

 
 
Step 2: Comparing the left-pivot elements with the right-pivot elements
 
[7,3,8,2,4,9,8,2,3,1] is considered our left-pivot dataseries.
[1,3,2,9,8,4,2,8,3,7] (note: reverse order), is considered out right-pivot dataseries.
 
What we need to do now, is iterate through both dataseries until...

• Left-pivot: we find a value that is >= the pivot value
• Right pivot: we find a value that is <= the pivot value

A visual example:

 
We swap the values if the left-pivot element > the right-pivot element. In this case, 7 > 1, so we swap the values.
We do this until our left and right index have "touched" each other. With this, I mean that they essentially traverse past each other.
 
A visual example again of the full process in motion:



Yellow = the values being compared
grey = The pivot
Blue = left-pivot sector
Right = right-pivot sector
 

Step 3: repeating the process until sectors have a size of 1

This is where you keep going through the motions. After we've compared all values in relation to the pivot, the array is split into two "sectors". We repeat this whole process until our sector's size is just 1.
 
Let's look at what happens if we repeat these steps until the very end:

 
Gray = pivot
Yellow = comparing values
Orange = right-pivot sector
Blue = left-pivot sector
Green = Sorted (as there is only 1 element in that sector)
 
That might look pretty tricky to you, but if you do this yourself once (I did it in microsoft word), it will become easier to understand for you.
 
As I already mentioned in the beginning of this chapter, Quicksort is not a sequential sort: the amount of actions is not reliant on the amount of elements within our dataseries. We will need to apply recursion:
 

@Override
    public void sort(int[] dataset)
    {
        evaluateSort(dataset,0,dataset.length - 1);
    }

 private void evaluateSort(int[] array, int min, int max)
    {
        int midIndex = min + (max - min) / 2; //the middle index
        int pivot = array[midIndex]; //the value of the middle index
        int low = min; //left-pivot sector starting point
        int high = max; //right-pivot sector starting point

        while (low <= high) //whilst both points have not touched each other
        {

            while (array[low] < pivot) //find a value on left-sector that is >= the pivot
            {
                low++;
            }

            while (array[high] > pivot) //find a value on the right-sector that is <= the pivot
            {
                high--;
            }

            if (low <= high) ////swap these around
            { 
                Arrays.swapValues(array, low, high);
                low++;
                high--;
            }

        }

        if (min < high) //if there's a sector with length > 1 on the left, sort again
        {
            evaluateSort(array, min, high);
        }
        if (max > low) //if there's a sector with length > 1 on the right, sort again
        {
            evaluateSort(array, low, max);
        }

[LogicSoup 92]

can you make a PDF? Want to keep it for future use as I will start learning this next semester

[Articron 738]

can you make a PDF? Want to keep it for future use as I will start learning this next semester

 

The post will stay here, don't worry 

[Manly 879]

I like the way you presented this Arti, thanks. Will come in handy later on this semester when I need to revise for those exams.

[Articron 738]

I like the way you presented this Arti, thanks. Will come in handy later on this semester when I need to revise for those exams.

 

Yeah all of us go through the sorting algorithms at some point, so I figured it would be handy for a few peeps

Added quicksort for the daily update

[Scorpius 144]

You are one fucking legend