5.Algorithm Description

Sorting Algorithms

Bubble Sort

The bubble sort algorithm is one of the simplest sorting algorithms, that works by repeatedly swapping the adjacent elements if they are in wrong order. The use of this algorithm took place when doing the functions related to the sorting of the publication dates from newest to lowest. Here´s a basic implementation of the code:

class BubbleSort 
{ 
    void bubbleSort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 0; i < n-1; i++) 
            for (int j = 0; j < n-i-1; j++) 
                if (arr[j] > arr[j+1]) 
                { 
                    // swap arr[j+1] and arr[i] 
                    int temp = arr[j]; 
                    arr[j] = arr[j+1]; 
                    arr[j+1] = temp; 
                } 
    } 
}

Quick Sort

The way this sorting algorithm works, is that basically, it is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array, or in our case, the singly linked list, around the picked pivot. There are many different versions of quickSort that pick pivot in different ways:

1. Always pick first element as pivot.
2. Always pick last element as pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot. This algorithm was used for the implementation of the functions regarding the sorting of the rating of the recipes, it travels the AVL tree and stores the title and the rating of each recipe and then sorts it. Here´s a basic implementation of the code:

class QuickSort 
{ 
    int partition(int arr[], int low, int high) 
    { 
        int pivot = arr[high];  
        int i = (low-1); // index of smaller element 
        for (int j=low; j<high; j++) 
        { 
            // If current element is smaller than the pivot 
            if (arr[j] < pivot) 
            { 
                i++; 
  
                // swap arr[i] and arr[j] 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        } 
        // swap arr[i+1] and arr[high] (or pivot) 
        int temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 
  
        return i+1; 
    } 
}

Radix Sort

Radix sort is an integer sorting algorithm that sorts data with integer keys by grouping, the keys by individual digits that share the same significant position and value (place value). Radix sort uses counting sort as a subroutine to sort an array of numbers, or in this case, it uses a singly linked list. Radix sort was used for the sorting of the all the difficulties related to the recipes, the way this works is that it travels the recipe AVL tree, and storages the title and the difficulty of each recipe, then the sorting occurs. Here´s a brief example of the implemented code:

RadixSort{
    // The main function to that sorts arr[] of size n using 
    // Radix Sort 
    static void radixsort(int arr[], int n) 
    { 
        // Find the maximum number to know number of digits 
        int m = getMax(arr, n); 
  
        // Do counting sort for every digit. Note that instead 
        // of passing digit number, exp is passed. exp is 10^i 
        // where i is current digit number 
        for (int exp = 1; m/exp > 0; exp *= 10) 
            countSort(arr, n, exp); 
    } 
}

Search Algorithms

Binary Search for Trees

This algorithm was implemented for searching for an specific data contained in the Binary Search, AVL and Splay tree, the way this algorithm was implemented was by using a recursive function that travels the tree using a function called "greater" that returns "key", "leaf" or "equals" depending of which string was the greatest. Example of the code:

public static AlphNodeTree<User> BinarySearch(String data){
        return BinarySearch(UserTree.getUserTree().getRoot(),data);
    }
    private static AlphNodeTree<User> BinarySearch(AlphNodeTree<User> reference, String data){
        if(reference.getKey().equals(data)){
            return reference;
        }
        switch(greater(reference.getKey(),data)){
            case "key":
                if(reference.getRight()!=null){
                    return BinarySearch(reference.getRight(),data);}
                else{
                    return null;
                }
            case "leaf":
                if(reference.getLeft()!=null){return BinarySearch(reference.getLeft(),data);}
                else{ return null;}
        }
        return null;
    }