CODEWITHSUNDEEP
javaalgorithmsorting
johnlacrosse
johnlacrosse

Reputation: 37

Bubblesort-like algorithm. What is the worst-case time complexity?

I made a sorting algorithm using the same kind of logic of the heapify algorithm. However, I do not believe this is heap sort. The logic of it, is that I compare two pieces of an array (Initially was going to be a double linked list, but java would not allow me to do that without making my own class) with the one next to it. If it is larger, swap. Much like a bubble sort. However, when the swap is completed, I then do a reverse bubble sort on the second element, to maintain the order of the array.

I'm not entirely sure of the worst case time complexity of this, but I think it is O(n^2). What is the time complexity of this, and also, what sorting algorithm does it most look like?

import java.util.Arrays;

/**
 * firstNum and secondNum trade places.
 * Whenever a swap is done, sink the secondNumber
 */
private static void swap(int[] A, int firstNum, int secondNum) {
    int temp = A[secondNum];

    A[secondNum] = A[firstNum];
    A[firstNum] = temp;

    sink(A, firstNum);
}

/**
 * Swap places upward until condition is false.
 */
private static void rise(int[] A, int currIndex) {

    int nextIndex = currIndex + 1;

    if (nextIndex <= A.length - 1 && A[currIndex] > A[nextIndex]) {

        swap(A, currIndex, nextIndex);
        rise(A, nextIndex);
    }
}

/**
 * Swap places downward until condition is not met.
 */
private static void sink(int[] A, int currIndex) {

    int prevIndex = currIndex - 1;

    if (currIndex > 0 &&  A[currIndex] < A[currIndex - 1]) {
        swap(A, prevIndex, currIndex);
    }
}

public static void main(String[] args) {

    int[] values = {4, 7, 2, 1, 3, 5, 100, 0};

    for (int i = 0; i < values.length - 1; i++) {
        rise(values, i);
    }

    System.out.println(Arrays.toString(values));


}

}

Upvotes: 1

Views: 182

Answers (1)

michid
michid

Reputation: 10814

I'd say this is insertion sort in disguise. It thus has worst case and average complexity of O(n^2).

To see this, first realize that the recursive call to rise in the rise method is redundant: the element being raised there will be reached anyway by a later call to rise from the outer loop in the main method. What's left is recursive calls to sink from the swap method for every element in the list. What that does is to place every element into the right position in the already sorted initial bit of the list: this is essentially insertion sort.

Upvotes: 1

Related Questions