Sorting Algorithms

The efficiency of the algorithms is calculated based on two things

1.Time Complexity

2.Space Complexity

Time Complexity is defined as number of times the particular iteration is needed to be executed not the time of execution because it may vary due to processor speed.

Space Complexity is the total memory space needed for execution

Lets have a look on to the few sorting Algorithms

First in the list is Bubble Sort Algorithms which has Time Complexity Of

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
Auxiliary Space: O(1)

Lets Have a Look on to it with the sample program from JAVA

class BubbleSort{
    public static void main(String[] args) {
        int numbers[] = {1,4,3,2};

        for(int i=0;i<numbers.length;i++) {
            int swap = 0;
            for(int j=0;j<numbers.length-1;j++) {
            if(numbers[j] > numbers[j+1]) {
                int temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] =  temp;
                swap = 1;
            }
        }
            if(swap == 0)
                break;
        }

        for(int i = 0;i<numbers.length;i++) {
            System.out.println(numbers[i]);
        }
    }
}

Lets Have a Look on to it with the sample program from Kotlin

fun main() {

    var numbers = arrayOf(4,3,2,1)

    for(i in 0..numbers.size-1) {
        var swap = 0
        for(j in 0..numbers.size-2) {
            if(numbers[j] > numbers[j+1]) {
                val temp = numbers[j]
                numbers[j] = numbers[j+1]
                numbers[j+1] = temp
                swap = 1
            }
        }
        if(swap == 0)
            break
    }
    for(i in 0..numbers.size -1) {
        println(numbers[i])
    }
}

Quick Sort Algorithms

It picks an element as pivot and partitions the given array around the picked pivot. We use this algorithms mainly for sorting because its average run time is good when compared to other algorithms

Lets see an example of quicksort Algorithm in JAVA

class HelloWorld {
    public static void main(String[] args) {
        int numbers[] = {1,3,4,2,6,5};
        quickSort(numbers,0,numbers.length-1);

        for(int i=0;i<numbers.length;i++) {
            System.out.println(numbers[i]);
        }
    }

    private static void quickSort(int numbers[],int lowIndex,int highIndex) {

        if(lowIndex < highIndex) {
            int pivot = numbers[highIndex];

            int LP = lowIndex;
            int RP = highIndex;

            while(LP < RP) {
                while(numbers[LP] <= pivot && LP < RP) {
                    LP++;
                }
                while(numbers[RP] >= pivot && LP < RP) {
                    RP--;
                }

                swap(numbers,LP,RP);
            }

            swap(numbers,LP,highIndex);
            quickSort(numbers,lowIndex,LP-1);
            quickSort(numbers,LP+1,highIndex);
        }
    }

    private static void swap(int numbers[],int index1,int index2) {
        int temp = numbers[index1];
        numbers[index1] = numbers[index2];
        numbers[index2] = temp;
    }
}

Lets see an example of quicksort Algorithm in Kotlin

fun main() {

    var numbers = arrayOf(1,3,4,2,6,5)

    quickSort(numbers,0,numbers.size-1)

    for(i in 0..numbers.size-1) {
        System.out.println(numbers[i])
    }

}

fun quickSort(numbers:Array<Int>,lowIndex:Int,highIndex:Int) {

    if(lowIndex < highIndex) {

        var pivot = numbers[highIndex];
        var LP = lowIndex;
        var RP = highIndex;

        while(LP < RP) {
            while(numbers[LP] <= pivot && LP < RP) {
                LP++
            }
            while(numbers[RP] >= pivot && LP < RP) {
                RP--
            }
            swap(numbers,LP,RP)
        }
        swap(numbers,LP,highIndex)

        quickSort(numbers,lowIndex,LP-1)
        quickSort(numbers,LP+1,highIndex)
    }
}

fun swap(numbers:Array<Int>,index1:Int,index2:Int) {
    var temp = numbers[index1];
    numbers[index1] = numbers[index2];
    numbers[index2] = temp;
}

Time Complexity

Best Case O(n*logn) Average Case O(n*logn) Worst Case O(n2)