0

I have implemented a sorting algorithm to sort an un-ordered integer array. If I throw in a 100,000-element array, it took roughly 10,500 mil sec to return. Is my algorithm fast or very slow?. Below is the code.

public static void sort(int[] array) {
    int lastItem = array[array.length - 1];
    int length = array.length;
    for (int j = 0; j < array.length; j++) {

        for (int i = 0; i < length; i++) {

            if (array[i] > lastItem) {
                array[length-1] = array[i];
                array[i] = lastItem;
                lastItem = array[length - 1];
            }
        }
        length--;
        if (length > 1) lastItem = array[length - 1];
    }
}
Trash Can
  • 6,608
  • 5
  • 24
  • 38
  • 3
    If you are talking about "implementation performance": Compare it to `Arrays#sort` for the same array. See which one is faster. If you are talking about "algorithm complexity": Yours seems to have quadratic runtime. 10 times bigger array, 100 times slower. Not too good. – Thilo May 27 '15 at 00:32
  • if you are using java8 Please read http://stackoverflow.com/questions/23170832/java-8s-streams-why-parallel-stream-is-slower This link is havingn many good examples http://winterbe.com/posts/2014/07/31/java8-stream-tutorial-examples/ – bobs_007 May 27 '15 at 00:33
  • You should calculate the Big-O time of your algorithm, then compare it to other known algorithms. That's the best way. A single data point tells you very little. – markspace May 27 '15 at 00:33
  • Still `O(n^2)` not great. – Shahzeb May 27 '15 at 00:34
  • 1
    Thank you very much. Since I am new to programming and stuff. So Ihaven't known much yet. But from you guys' answers. I think I now where to go. – Trash Can May 27 '15 at 00:41
  • [This page](http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms) has some useful information for you. – user1803551 May 27 '15 at 02:14

2 Answers2

0

You algorithm is using bubble sort which takes o(n^2). For larger input it might be slow. Why not use quick sort which will achieve the result you desire in O(nlogn)?

Here is some code, please note that it might be better to select the pivot as mid-element.

/**
 * o(nlogn) - high probability otherwise o(n SQUARE)
 * 
 * 
 * Choose a pivot value. We take the value of the middle element 
 * as pivot value, but it can be any value, which is in range of 
 * sorted values, even if it doesn't present in the array.
 * 
 * Partition. Rearrange elements in such a way, that all elements 
 * which are lesser than the pivot go to the left part of the array 
 * and all elements greater than the pivot, go to the right part 
 * of the array. Values equal to the pivot can stay in any part 
 * of the array. Notice, that array may be divided in non-equal parts.
 * 
 * Sort both parts. Apply quicksort algorithm recursively to the left 
 * and the right parts.
 * 
 * @param input
 */
public void quickSort(int[] input, int start, int end){
    if( start < end ){
        int pindex = findParition(input, start, end);
        quickSort(input, start, pindex-1);
        quickSort(input, pindex+1, end);
    }
}

/**
 * findParition for quick sort
 * @param input
 * @param start
 * @param end
 * @return
 */
private int findParition(int[] input, int start, int end) {
    int pivot = input[end];
    int pindex = start;

    for( int i = start; i < end; i++){
        if( input[i] <= pivot ){
            int temp = input[pindex];
            input[pindex] = input[i];
            input[i] = temp;

            pindex++;
        }
    }

    int temp = input[pindex];
    input[pindex] = input[end];
    input[end] = temp;

    return pindex;
}
0

Click here to compare various sorts.

enter image description hereenter image description here

enter image description here

pola sai ram
  • 832
  • 7
  • 23