Tuesday, February 17, 2015

A Sorting Algorithm

I thought of this algorithm this evening and implemented it for fun. It's not very good but anyways:

Time Complexity : O(n^2)
Space Complexity : O(n^2)

Algorithm:

We have an array of elements.

Start with first element. Store it in a stack. Iterate over remaining elements and check to see if they are greater than the last biggest found element in this stack. If it is bigger, store it in the stack and change bigger to contain this element. If it is less, skip it.

Now for the remaining elements, start with the first remaining element. Put it in a stack. Now do the same process with this stack (Iterate over the remaining elements to see if they are bigger than the current biggest element in this stack, skipping if they are smaller).

Do this until all of the elements have been put in some stack. 

It is possible to have stacks containing only one element.

Now, compare the stack tops and pop that stack which has the biggest of all stack top elements.
Put the popped element in the original array at location i (i=0 to length of the array).

Do this until all of the stacks become empty.

The array is sorted.

Consider the array:

3, 7, 7, 4, 2, -3, 0

Stacks:

                                                                                                                             
7                                                                                                                           
7                        0                                                                                              
3       4       2       -3
S1      S2      S3      S4

Now merge these stacks

Max(7, 4, 2, 0) = 7
Max(7, 4, 2, 0) = 7
Max(3, 4, 2, 0) = 4
Max(3, 2, 0)     = 3
Max(2, 0)         = 2
Max(0)             = 0
Max(-3)            = -3      

Sorted Array  = 7, 7, 4, 3, 2, 0, -3

Elements have been sorted!                                                                                                                                                                                  
Code:

import java.util.Arrays;

public class ASort {

    public static void main(String[] args) throws Exception {
        int array[] = {6, 4, 8, 9, 6, 5, -8, -9, 5, 6, -99, -5, 5, 0, 2, 3, 5,5,6,7,8,8,9,0, 0, 2, 5, 6, 9, -9, -8, -56};

        int[][] stackAr = new int[array.length][array.length];
        int[] indices = new int[array.length];
        Arrays.fill(indices, -1);
        int index = 0;

        for (int i = 0; i < array.length; ++i) {
            if (array[i] != Integer.MAX_VALUE) {
                stackAr[index][++indices[index]] = array[i];
                int greater = array[i];

                for (int j = i + 1; j < array.length; ++j) {
                    if (array[j] != Integer.MAX_VALUE && array[j] >= greater) {
                        stackAr[index][++indices[index]] = array[j];
                        greater = array[j];
                        array[j] = Integer.MAX_VALUE;
                    }
                }
                index++;
            }
        }

        index = 0;
        for (int i = 0; i < array.length; ++i) {
            int max = Integer.MIN_VALUE;
            int indexOfTarget = 0;
            for (int j = 0; j < array.length; ++j) {
                if (indices[j] != -1) {
                    if (stackAr[j][indices[j]] > max) {
                        max = stackAr[j][indices[j]];
                        indexOfTarget = j;
                    }
                }
            }
            array[i] = stackAr[indexOfTarget][indices[indexOfTarget]--];
        }

        for (int i = array.length - 1; i > -1; --i) {
            System.out.print(array[i] + ", ");
        }
        System.out.println();
    }
}
                                                                                                                                                                     
Output:

-99, -56, -9, -9, -8, -8, -5, 0, 0, 0, 2, 2, 3, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 8, 8, 8, 9, 9, 9,                                                                                                                       

No comments:

Post a Comment