0

Algorithm

Basically, is the below algorithm O(n log n) or O(n^2). I'm sure the algorithm has a name; but I'm not sure what it is.

pseudo-code:

def sort(list):
    dest = new list
    for each element in list (call it a):
        for each element in dest (call it c):
            if a <= c, insert a into dest directly before c
    return dest

in Java:

public static List<Integer> destSort(List<Integer> list) {
    List<Integer> dest = new ArrayList<>();
    for (Integer a : list) {
        if (dest.isEmpty()) {
            dest.add(a);
        } else {
            boolean added = false;
            for (int j = 0; j < dest.size(); j++) {
                int b = dest.get(j);
                if (a <= b) {
                    dest.add(j, a);
                    added = true;
                    break;
                }
            }
            if(!added) {
                dest.add(a);
            }
        }
    }
    return dest;
}

Simply speaking, this algorithm walks a list, and inserts each element into a newly created list in its correct location.

Complexity

This is how I think about the complexity of this algorithm:

  • For each element in the list, dest increases in size by 1
  • This means that, at each step, the algorithm has a worst-case time of the size of dest
  • Summing those up, we'd get 0 + 1 + 2 + 3 + ... + n
  • The sum of all natural numbers up to n = n(n+1)/2
  • This simplifies to (n^2 - n)/2, and by removing constant & low degree terms, we get O(n^2)

Therefore the complexity is O(n^2).

However, I was recently browsing this answer, in which the author states:

O(n log n): There was a mix-up at the printer's office, and our phone book had all its pages inserted in a random order. Fix the ordering so that it's correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book.

This, to me, sounds like the same algorithm, so my question is:

  • Is the algorithm I described the same as the one described by @John Feminella?
  • If it is, why is my calculation of O(n^2) incorrect?
  • If it isn't, how do they differ?
Community
  • 1
  • 1
Socratic Phoenix
  • 556
  • 1
  • 7
  • 19
  • Looks like bubble sort - more or less. You're missing the part where you swap items according to your comparison. https://en.wikipedia.org/wiki/Bubble_sort – Stefan Falk Jun 24 '17 at 01:34
  • That quoted O(n log n) algorithm is based on the assumption of working with real-world objects as opposed to considering how computers work. You can't really compare the complexity of that against the code you've written. – Bernhard Barker Jun 24 '17 at 01:56

1 Answers1

2

The algorithm you have described is different than the O(n log n) algorithm described in the linked answer. Your algorithm is, in fact, O(n^2).

The key difference is in the way the correct location for each element is determined. In you algorithm, each element is searched in order, meaning that you check every element against every other already-sorted element. The linked algorithm is predicated on the O(log n) method used for finding a person's name:

O(log n): Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. Then repeat the process about halfway through the part of the book where the person's name lies. (This is a binary search for a person's name.)

If you use this method to find where each page should go in the new book, you only end up doing O(log n) operations for each page, instead of O(n) operations per page as in your algorithm.

Incidentally, the algorithm you have described is essentially an insertion sort, although it uses two lists instead of sorting in-place.

BJ Myers
  • 6,617
  • 6
  • 34
  • 50
  • Ah okay. So if I were to use a binary-search style insertion instead, then it would be O(n log n)? – Socratic Phoenix Jun 24 '17 at 01:33
  • @SocraticPhoenix Yep, you got it. – BJ Myers Jun 24 '17 at 01:37
  • @SocraticPhoenix Search for Divide and Conquer in sorting tasks, which is used e.g. by merge sort. – Stefan Falk Jun 24 '17 at 01:37
  • @SocraticPhoenix this answer is right, but you're not right that a binary insertion would result in O(n log n). This is just a sort, and O(log n) is achievable. – danh Jun 24 '17 at 01:40
  • @danh Not quite sure what you mean. Comparison-based sorts cannot be done in better than O(n log n). – BJ Myers Jun 24 '17 at 01:41
  • @SocraticPhoenix Not exactly. If you were to use an array, insertion is still O(n) even if you do binary search to find the position, so it's O(n^2) in total. Something like a (Balanced) Binary Search Tree would allow for O(log n) insertion at a specific position. – Bernhard Barker Jun 24 '17 at 01:47