1

I'm currently learning how to program with Java, so I'm taking a class on Data Structures and whatnot. Recently, we've been covering the concepts of Sorting Algorithms, and from the start I've been very much confused about the concept as a whole.

We've been given an assignment recently on Sorting Algorithms, and one of the questions looks like this:

Closest 1d pair. Given a sequence of N real numbers, find the pair of integers that are closest in value. Give a O(N log N) algorithm. Describe your proposed algorithm in English.

Basically, what I'm trying to ask is this: Can someone explain to me the general idea of Sorting Algorithms and their purpose as a whole, as well as walk me through how I would go about answering this question? You don't have to give me an answer, I just am looking to acquire the knowledge necessary for answering this question.

Thank you.

Improve this question
1
  • 2
    Robert Sedgewick: Algorithms (Fourth Edition), Chapter 2: Sorting Commented Mar 3, 2014 at 21:04

4 Answers 4

Reset to default
1

The idea of sorting is that in a sorted structure (e.g array, list, or balanced tree), you can find s specific element in log N operations. (Using e.g binary search in arrays) If the list is not sorted you would need N/2 operations on average.

Altough common, the term "log N", is not very precise, correctly it is "ld N" or log2 (ld: logarithmus dualis, or logarithmus on base 2). log normally stands for log on base10. In computer science, nearly ever log(N) means log2(N)

So a sorted list speeds up your algorithm, espcially if you have to search more than a few times.

In your case: If the sequence is sorted, then then one of the candidate pairs is constructed by looking at the previous and next element in the sequence.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

The question is to find the 2 closest elements, lets look at an example:

What would be the two closest elements in this list?

data = {1,45,32,7,87,54,10};

Hmm, its hard to tell by looking.

One thing we could do would be to compare each element, with every other element, something like this:

for(int a = 0; a < data.length; a++) {
    for(int b = 0; b < data.length; b++) {
       //compare data[a] to data[b], keep track of closest
    }
}

This is called a brute force approach, and would result would be O(n^2) solution, which is too slow for your purposes.

Lets try a different approach; lets try sorting the array first.

data = {1,45,32,7,87,54,10};
sorted = magicalSort(data)  //You will have to implement the sorting

The contents of sorted are as follows:

{1,7,10,32,45,54,87}

By sorting the data first, finding the closest 2 elements becomes a lot easier, it doesn't take long to look and see that 7 and 10 are the closest two.

The cost of this solution would be : O(n log n) for sorting (see Quicksort and Mergesort), plus O(n) for iterating over the sorted list and searching for the closest two elements.

This gives you:

O(n log n) + O(n)

which is approximately:

O(n log n).

Improve this answer

3 Comments

Good, but this part is confusing: "O(n) is more efficient than O(n log n)", Its O(N * log N) + O(N) which is approx O(N*logN)
Thank you to everyone who answered, each of you put it into different perspectives for me, and I am finding that I am beginning to actually understand this! TylerAndFriends, your answer really put it into the simplified way that I needed most, so thank you very much. I appreciate the help.
Thanks @AlexWien I will clarify that.
0

If you have an unsorted list of numbers [-3, -7, 9, 6, 0] and wish to find the two 'closest' numbers, you need to calculate the distances: (-3,-7), (-3,9), (-3,6), (-3,0), (-7,9), (-7,6), (-7,0), (9,6), (9,0), (6,0). This is N! calulations, which is quite huge when N gets big.

if the list is sorted, then you only need to calculate (-7,-3), (-3,0), (0,6), (6,9), or N-1 calculations.

Ofcourse, sorting the list will cost something. MergSort and QuickSort are both O(n(log n)) on average. But note that (sort time) + (delta time) < n!

that is, n(log n) + (n-1) < n!

Improve this answer

1 Comment

The term "n!" is confusing n! means n * (n-1) * n * (n-2) * ... * 2 * 1; (Faktorielle)
0

To answer your questions:

  1. Purpose of sorting algorithm To make the sorting process more efficient in time and space. Say if you have N numbers, the brute-force way is to compare each number with the other N-1 numbers, thus in total you have to make N^2 comparisons. However, a good sorting algorithm can help you to reduce the complexity to N*logN, performance improved.

  2. A general idea about this problem First, you may try to sort the array of numbers. Then walk through the sorted array for only 1 time and compare the difference of two consecutive numbers, try to find the closest pair. This doesn't necessarily have to be the best solution, just for your reference.

  3. Try to look at the insertion sort, quick sort, merge sort They are classics and helpful in understanding sorting algorithms.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.