programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# what algorithm should i choose for this sort

Dan D'amico
Ranch Hand
Posts: 94

if i have an array that defined by this rools:
- the even indexes are sorted upwards, with no repeated numbers.
-the odd indexes are sorted downwards ,with no repeated numbers.

i'm not looking for a code.
i want to implement it myself.
but what i want to know is . what is the most effiecient sort algorithm i can choose that the complexity, both time and place will be the best it can.
if i can choose from - quicksort and mergesort . i can choose also insertion and selection but they both N^2 which is not good for this example.
what is the best bigO i can get for an algorithm that solve this problem ?

Paul Clapham
Sheriff
Posts: 22832
43
Dan D'amico wrote:... both time and place will be the best it can.

You can't really use this as a requirement, since you can often improve your time complexity at the expense of worse space complexity, and vice versa.

Liutauras Vilda
Sheriff
Posts: 4923
334
Dan D'amico wrote:if i can choose from - quicksort and mergesort

From those two, quick sort has better chances to win by a right guesses on pivot element.

Knute Snortum
Sheriff
Posts: 4281
127
what is the best bigO i can get for an algorithm that solve this problem ?

I believe O(log n).

Campbell Ritchie
Marshal
Posts: 56570
172
For an array that small bubble sort is the method of choice.

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
couldn't you treat this as two sorted arrays, and do a merge sort?

Paul Clapham
Sheriff
Posts: 22832
43
There's nothing special in your requirements as far as sorting is concerned. Basically you're sorting one list in ascending order and another list in descending order. That business about the two lists being intertwined like that is really irrelevant, it's just smoke which confuses the question. If you try to sort the data in place (i.e. not copying it to somewhere else) you're still going to use the same algorithms, it's just that your code for picking the right subset to sort is going to be a bit more complicated.

Dan D'amico
Ranch Hand
Posts: 94
Paul Clapham wrote:There's nothing special in your requirements as far as sorting is concerned. Basically you're sorting one list in ascending order and another list in descending order. That business about the two lists being intertwined like that is really irrelevant, it's just smoke which confuses the question. If you try to sort the data in place (i.e. not copying it to somewhere else) you're still going to use the same algorithms, it's just that your code for picking the right subset to sort is going to be a bit more complicated.

if its not in-place so i can simply do this by creating a new array and then merge to it the original one.
if its in-place i cant think now for an algorithm that will be more efficient then O(N^2) and since O(N) is the requirement i think i will just need to use another helper array and merge to it the original one ordered.

Campbell Ritchie wrote:For an array that small bubble sort is the method of choice.

this array is just an example. the algorithm should work for any array.

Liutauras Vilda
Sheriff
Posts: 4923
334
Dan D'amico wrote:if its in-place i cant think now for an algorithm that will be more efficient then O(N^2) and since O(N) is the requirement

Dan, it became confusing now. The runtime of a program is a function of the size n of the input taken for the worst case.

But since you stated
Dan D'amico wrote:i can choose that the complexity, both time and place will be the best it can

O(n) you can achieve with all most popular sorts.
So please, could you specify a bit more clear, what is your goal?

Liutauras Vilda
Sheriff
Posts: 4923
334
Dan D'amico wrote:this array is just an example. the algorithm should work for any array

Moreover, it doesn't look that you have any specific requirements for an array, so you can choose any sorting algorithm you like.
But probably you won't invent nothing new over here, but you still could challenge yourself and impress your professor by rewriting your chosen sort in complete recursive way (with no loops at all).

Dan D'amico
Ranch Hand
Posts: 94
Liutauras Vilda wrote:
Dan D'amico wrote:if its in-place i cant think now for an algorithm that will be more efficient then O(N^2) and since O(N) is the requirement

Dan, it became confusing now. The runtime of a program is a function of the size n of the input taken for the worst case.

But since you stated
Dan D'amico wrote:i can choose that the complexity, both time and place will be the best it can

O(n) you can achieve with all most popular sorts.
So please, could you specify a bit more clear, what is your goal?

my goal is to sort this array in O(n) for time . and O(1) for space. if its even possible, i dont know.
if the space complexity will be O(n) i know how to do this, but for O(1) not actually.

Liutauras Vilda wrote:
Dan D'amico wrote:this array is just an example. the algorithm should work for any array

Moreover, it doesn't look that you have any specific requirements for an array, so you can choose any sorting algorithm you like.
But probably you won't invent nothing new over here, but you still could challenge yourself and impress your professor by rewriting your chosen sort in complete recursive way (with no loops at all).

i have one requirement. that the algorithm will be efficient as possiblbe. and actually i now solve old exams to get ready to my final exam two weeks from now.

Knute Snortum
Sheriff
Posts: 4281
127
Dan D'amico wrote:O(n) you can achieve with all most popular sorts.

Pick one of these three sort algorithms and implement it. Post back here if you have specific problems.

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Dan D'amico wrote:i have one requirement. that the algorithm will be efficient as possible.

That isn't a requirement. it's not even a spec.

programming always involves trade-offs. something may be time-efficient, but you loose memory efficiency. an algorithm may be simple to understand, but take a long time to run (and long is a relative term).

And an algorithm may be fast for one data set, but slow for another...but it AVERAGES out to being pretty fast most of the time.

In the real world, it may be cheaper to spend more money on hardware (i.e. faster CPUs) than on improving the algorithm or code.

Paul Clapham
Sheriff
Posts: 22832
43
Dan D'amico wrote:if its in-place i cant think now for an algorithm that will be more efficient then O(N^2)

Here's one: sort the elements with odd-numbered indexes using any of the many standard sorts with efficiency better than that. Then sort the elements with even-numbered indexes ditto. Notice that any of the ordinary sorts will work here. Remember that I said that the business of having to sort the elements in two different ways was just a distraction? Don't be distracted, filter out the hard stuff up front and the rest is easy.