1

Allow me to be more specific by using an example (in Java).

Say you want to sort this array:

[10, 20, 30, 40, 50, 60, 70, 80, 90]

Lets assume the pivot is, oh say, the value 30. After sorting it should look like this:

[40, 50, 60, 70, 80, 90, 30, 10, 20]

The numbers that are greater than 30, end on the left side of 30 (while still sorted as least to greatest) and the numbers less than 30 are on the right side of 30 (while still sorted as least to greatest).

Note: Assume that the data set is very large, it doesn't have to this exact array set.

Now here's my algorithm that I had come up with (in pseudocode):

1). Count how many values are more than 30, call this count value 'X'. Swap the value of 30 at index X.

2). Have 2 "movers" that start on both ends, each moving towards the pivot and determining which numbers should go on what side

3). Use bubble sort on both sides of the pivot to finish the algorithm.

Now, here's my problem with my own algorithm. It's O(n) up until I get to the bubble sort, which makes it O(n^2).

My specific question is: What would be a better approach for this and still keep it as O(n)? Or if possible O(log n) ? Answers could be in pseudocode, but you chose to code for the answer, I prefer it be in Java.

Note: The array is an integer array. All with unique values.

Edit: Mergesort is obviously a much better solution than bubble sort. My question is really geared towards finding an O(n) or O(log n) solution.

Ebad Saghar
  • 1,107
  • 2
  • 16
  • 41
  • 2
    Get hold of Donald E. Knuth's book "The Art of Computer Programming", Volume 3 – Sorting and Searching. It will answer all of your questions. – laune Feb 19 '15 at 07:35

2 Answers2

1

First if you are concern about time why you are using bubble sort? The first thing you could do is to replace bubble sort with algorithms like Merge Sort, its complexity is O(n log n).

Now I tell you it is not possible to find a better solution with O(n) or O(log n), suppose you find and O(n) or even O(log n) algorithmic solution. Now you can sort every array with O(n)! Because at first you find the minimum of array with O(n), and then use it as pivot and then use your algorithm, now you have a sorted array, and it complexity is O(n) which is not possible yet. For more info about O(n log n) look at What are the rules for the "Ω(n log n) barrier" for sorting algorithms?

You can find java implementation of sorting algorithms here .

Community
  • 1
  • 1
Lrrr
  • 4,755
  • 5
  • 41
  • 63
  • Using Merge Sort is of coarse much better than bubble sort. In fact, I was in favor of using Merge sort, I can't remember why I chose bubble sort though. But my question is actually really geared to finding if there is an O(n) or O(log n) solution, if so what would be that approach – Ebad Saghar Feb 19 '15 at 07:44
  • @EbadSaghar I know what your question is really about, and in second my second paragraph I try to answer your question, in one word it is not possible – Lrrr Feb 19 '15 at 07:46
  • 1
    Sorry for the misunderstanding. I guess this solves my question then – Ebad Saghar Feb 19 '15 at 07:49
  • You can sort with O(n) if the data is integers in a small range. Depending on the range of values a Counting Sort would work. – Jerry Jeremiah Feb 19 '15 at 09:03
  • @JerryJeremiah "Assume that the data set is very large", I'm aware of that, but it wouldnt be a general answer – Lrrr Feb 19 '15 at 09:08
1

If you want to do it in the simplest way possible, sort the array in its natural order first, then rotate it.

public static void main(String[] args) {
    int pivotValue = 3;
    Integer[] array = { 6, 4, 7, 3, 9, 1, 2, 0, 5, 8 };
    System.out.println(java.util.Arrays.toString(array));

    java.util.Arrays.sort(array);
    int pivotIndex = java.util.Arrays.binarySearch(array, pivotValue);
    int pivotOffset = Math.abs(pivotIndex + 1);
    java.util.List<Integer> list = java.util.Arrays.asList(array);
    java.util.Collections.rotate(list, -pivotOffset);
    if (pivotIndex > 0) {
        list = list.subList(array.length - pivotOffset, array.length);
        java.util.Collections.rotate(list, 1);
    }
    System.out.println(java.util.Arrays.toString(array));
}

The binary search is O(log n) but the sort and rotate are O(n) so the overall complexity is O(n log n) (corrected per @brimborium).

gknicker
  • 5,509
  • 2
  • 25
  • 41