Question

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.

Was it helpful?

Solution 2

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).

OTHER TIPS

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.

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!

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top