Sign in to follow this  

Sorting Algorithm

This topic is 3589 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! I have an array of integers and it can be up to 10000 integers in it. I have to proccess with all of those integers one by one BUT starting from the smallest and go to the biggest. For now I am scanning through all of the array and finding the smallest and proccessing it then I am scanning again through all of the array and finding the smallest... till the end of the array. also I am doing this code for some kind of competition and it wants me to do it in 1 seconds but for my programm it takes about 1.3 seconds. What I think is; Sorting the array for ONE time and saving it to a linked list and then proccess that linked list quickly. But as I searched I have found many sorting algorithms.. Which I should use for a 10000 integer-array? And one last thing, do arrays that contain 10000 variable matter for our "high-speed" computers?It occurs to me that it is a very huge number but sometimes computers can do a lot better :o What I asked was just a sorting algorithm but I explained it in a detailed way. Thanks, I am waiting for your replies :)

Share this post


Link to post
Share on other sites
Answer: It depends. If you're allowed to use whatever libraries your language gives you, then use the standard sort function. C++ has std::sort, for example.

If not, it sounds like this is a one-time need, and the program doesn't need to be that fast, so the easiest algorithms to implement are insertion sort or selection sort. You can write selection sort in about 8 lines of easy to read code, although from your description of how you're handling the problem now, it's not going to be significantly faster. (It will be faster by some small constant, though).

10,000 numbers is basically nothing. You should be able to sort (or scan) that faster than you can react. I'd expect sorting 10k numbers to take on the order of 1 millisecond, at worst. (This obviously depends on lots of factors.)

Finally, if you already have an array of numbers, and you sort them so you can process them in order... why bother putting them in a linked list? Why not just leave them in the array and process them there? For the problem that you're describing, it sounds like the linked list would just make things slower.

Edit: Yeah, I didn't trust my original time guess (it's much easier to discuss relative performance than absolute numbers). It turns out I was pretty accurate. I threw together a tiny C# program to generate 10,000 random integers, then I sorted it using Array.Sort. My (not very good) laptop completes the sort in about 1.5 milliseconds. (That's 0.0015 seconds).

Share this post


Link to post
Share on other sites
Your best bet for a large array is a selection/linear sort. It finds the lowest number in the array and places it in the first position. It is repeated until the array is sorted.

To run it you will need to find the smallest number: FindSmallest(), swap the two values: Swap() and display the array: DisplayNumbers()


for (CurrentPos = 0; CurrentPos < (MAX_NUMS - 1);
CurrentPos++)
{
DisplayNums( Number,MAX_NUMS );

LowestIndex=FindLowestIndex( Number,CurrentPos +
1,MAX_NUMS - 1;


if (Number[LowestIndex] < Number[CurrentPos])
{
Swap(Number[LowestIndex],Number[CurrentPos]);
}
}

Share this post


Link to post
Share on other sites
I'd probably just radix sort the integers and be done with it.

For a very rough estimation of speed, the floating point radix sort I wrote in C# takes on average about 2.7 milliseconds to sort 10000 random floats and it is far from optimized. An integer radix sort should perform quite a bit better than that.

Regards,
ViLiO

Share this post


Link to post
Share on other sites
Without boring you with complexities and big-o notation:

Quick-sort is considered one of the fastest sorting algorithms. Although it's usually implemented recursively so the number of recursions is limited by the call stack depth.

Heap-sort is quite fast also, almost on-par with quick-sort, but it isn't limited by the stack meaning it can run on much larger data sets than a typical quick-sort implementation.

Merge-sort is also one of the better algorithms, particularly popular when you only have sequential access (like a linked-list). It requires more memory than a heap-sort but it has the advantage of being a stable sort - although this doesn't seem to matter in your case.

Since you mentioned integers, you can also look into a Radix-sort, a lexicographical sort, which may be faster than all of the above, but then again maybe not [rolleyes].

On the off-chance that you're using C++ then you can just use std::sort, a typical implementation is a mix between quick-sort, heap-sort and insertion-sort making it very efficient and not call stack limited.

Share this post


Link to post
Share on other sites
Quote:
Original post by osmanb
Finally, if you already have an array of numbers, and you sort them so you can process them in order... why bother putting them in a linked list? Why not just leave them in the array and process them there? For the problem that you're describing, it sounds like the linked list would just make things slower.


I thought that swapping the values in an array was much much slower but then(now) I remembered that it was "adding new things" which caused problems.I won't bother the linked lists now.

Thanks for your answers I'll post again when I finished it or when I have further questions.


Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
On the off-chance that you're using C++ then you can just use std::sort, a typical implementation is a mix between quick-sort, heap-sort and insertion-sort hence making it very efficient.


I have never heard of that std::sort thing.. I'll look thanks !

Share this post


Link to post
Share on other sites
I had written a bi-directional linked list (left and right node pointers) that I needed sorted. After considering some algorithms, I realized that my list had something in common with binary trees (which are sorted by nature); they both use left and right node pointers. So, I converted all the pointers in my list to a binary tree structure and back again to a list. The result: a sorted linked list. I also wrote a two-pass unsort algorithm to avoid the worst-case scenario of sorting a sorted list (which had about a 90 minute run time). So, the complexity of this algorition was O(2n + n log n) and sorted 250,000 objects in 1000 to 2000 ms on a P4 1.4GHz.

The algorithm used recursion to convert to a tree structure, then recursed the tree returning list "splices" which it would link together and ultimately return one large splice (the entire list).

Another implementation you might want to consider is the red-black tree which achieves O(n log n) in all cases.

Share this post


Link to post
Share on other sites
Quote:
Original post by coderx75
Another implementation you might want to consider is the red-black tree which achieves O(n log n) in all cases.

IIRC a std::set is usually implemented as a red-black balanced binary tree; for the OP it might be worth considering using this container as opposed to sorting an array.

Share this post


Link to post
Share on other sites
I came across another sorting algorithm a few days ago called Comb Sort. It's basically an improved bubble sort which achieves a time complexity of O(n log n) in the average and worst case scenarios and has a space complexity of O(1). I haven't timed it but it appeared to me to sort an array of 1 million integers in about half a second give or take. The constant space complexity could be good in managed environments to avoid the expense of garbage collection on memory used during the sort.

Share this post


Link to post
Share on other sites
Hehe I didn't know that sorting inherits so much complex algorithms :S I chose the SelectionSort algorithm !


void selectionSort(int numbers[], int array_size)
{
int i, j;
int min, temp;

for (i = 0; i < array_size-1; i++)
{
min = i;
for (j = i+1; j < array_size; j++)
{
if (numbers[j] < numbers[min])
min = j;
}
temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}



My test results are..


Executing...
Test 1: TEST OK [0.004 secs]
Test 2: TEST OK [0 secs]
Test 3: TEST OK [0 secs]
Test 4: TEST OK [0.004 secs]
Test 5: TEST OK [0.004 secs]
Test 6: TEST OK [0.004 secs]
Test 7: TEST OK [0.016 secs]
Test 8: TEST OK [0.268 secs]

All tests OK.

Your program ('milk2') produced all correct answers!



Thanks everyone

Share this post


Link to post
Share on other sites
Quote:
Original post by TheUnbeliever
(As an aside, can someone tell me if I'm right in thinking the OP's algorithm was O(n2)?)


I think you're right, the OP compares n integers once for for each of those n integers, this gives n*n = n2 comparisons, so yeah O(n2) complexity.

Share this post


Link to post
Share on other sites
Quote:
Original post by Eralp
Hehe I didn't know that sorting inherits so much complex algorithms :S I chose the SelectionSort algorithm !

*** Source Snippet Removed ***

My test results are..

*** Source Snippet Removed ***

Thanks everyone

Why didn't you just use std::sort? It'd probably be faster, and it's easier to use and guaranteed to "just work".

Eg.

void SortNumbers(int numbers[], int array_size)
{
std::sort(numbers, numbers + array_size);
}

Share this post


Link to post
Share on other sites

This topic is 3589 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this