Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

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 ?

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 ?

Campbell Ritchie

Marshal

Posts: 56570

172

posted 2 years ago

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

posted 2 years ago

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.

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

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.

posted 2 years ago

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

O(n) you can achieve with all most popular sorts.

So please, could you specify a bit more clear, what is your goal?

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?

posted 2 years ago

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

posted 2 years ago

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.

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.

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.

posted 2 years ago

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

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.

All things are lawful, but not all things are profitable.

posted 2 years ago

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.

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.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

posted 2 years ago

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.

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.