sort algorithms
Hi, I could really use some clues how to program this task. I'm bad at programing, so I have no idea where to start.
task:
Which of the matching algorithms you selected is faster with 100,000 not sorted out data?
Which of the matching algorithms you selected is faster with 100,000 reverse-sorted out data?
Algorithms:(need to program 2)
Bubble sort
Insertion sort
Selection sort
Heap
Shell
Merge
Quick
Radix
My questions:
1. how do I create a file with 100000 elements to read?
2. what is not sorted out and reverse sorted out elements and how to make them.
3. can you show some examples how to program?
Thank You for your time.
(I tried translating task from my language)
task:
Which of the matching algorithms you selected is faster with 100,000 not sorted out data?
Which of the matching algorithms you selected is faster with 100,000 reverse-sorted out data?
Algorithms:(need to program 2)
Bubble sort
Insertion sort
Selection sort
Heap
Shell
Merge
Quick
Radix
My questions:
1. how do I create a file with 100000 elements to read?
2. what is not sorted out and reverse sorted out elements and how to make them.
3. can you show some examples how to program?
Thank You for your time.
(I tried translating task from my language)
Last edited on
1) you can do this in another program (like excel) or you can do it in c++ or you can probably even find one online or generate one online. The thing here is whatever encryption it is using.
I don't even know what reverse paged is. Page to me means a block of memory in your cpu cache. Reversed ?? I would take that to mean its unpaged and a memory/cache hit cost for all entries? This maybe did not translate correctly.
2) I don't know. You will have to ask your teacher. To me, an encrypted integer is one of 2 things, its either a string or another integer, depending on what was needed by the user. Note that strings can be treated as integer or an array of integers, so the algorithm may not matter.
3) Is this your first program?
the first 3 sorts are brute force and take N*N to do worst case data. They are terribly slow for large amounts of data (100k is not large anymore; when I started programming that would have run for a week with bubble sort, its not even a min or 2 now).
shell is 'special'. Its run time depends on what sequence you use, and can vary from N*N to N^ n+1/n (7/6 is common). This is faster than NlgN for small Ns and slower for bigger Ns. the sort approaches linear time if the list is already sorted OR nearly in worst case. So it is good for already sorted lists that changed a little and need a re-sort. It is a solid general purpose sort and one of the fastest if your machine does not handle recursion well (some embedded machines).
I think radix is similar to bucket and gets linear (N) run time but the technique is not possible for all types of data.
The rest are NlgN time sorts and have different use cases depending on the type and storage methods of the data.
I recommend you program insertion and shell, as shell is a tweak to insertion so you can reuse most of the code, and, shell as I said is useful to have around in your toolbox.
We can help but you need to try it. The only way to get better at programming is to do it. Sorting has been done to death ... its a major need in software, and people like it to be fast and stuff... there are tons of online code, algorithm explains, and even animations on how they work. Google a bit, learn about the algorithms, and give it a try.
I don't even know what reverse paged is. Page to me means a block of memory in your cpu cache. Reversed ?? I would take that to mean its unpaged and a memory/cache hit cost for all entries? This maybe did not translate correctly.
2) I don't know. You will have to ask your teacher. To me, an encrypted integer is one of 2 things, its either a string or another integer, depending on what was needed by the user. Note that strings can be treated as integer or an array of integers, so the algorithm may not matter.
3) Is this your first program?
the first 3 sorts are brute force and take N*N to do worst case data. They are terribly slow for large amounts of data (100k is not large anymore; when I started programming that would have run for a week with bubble sort, its not even a min or 2 now).
shell is 'special'. Its run time depends on what sequence you use, and can vary from N*N to N^ n+1/n (7/6 is common). This is faster than NlgN for small Ns and slower for bigger Ns. the sort approaches linear time if the list is already sorted OR nearly in worst case. So it is good for already sorted lists that changed a little and need a re-sort. It is a solid general purpose sort and one of the fastest if your machine does not handle recursion well (some embedded machines).
I think radix is similar to bucket and gets linear (N) run time but the technique is not possible for all types of data.
The rest are NlgN time sorts and have different use cases depending on the type and storage methods of the data.
I recommend you program insertion and shell, as shell is a tweak to insertion so you can reuse most of the code, and, shell as I said is useful to have around in your toolbox.
We can help but you need to try it. The only way to get better at programming is to do it. Sorting has been done to death ... its a major need in software, and people like it to be fast and stuff... there are tons of online code, algorithm explains, and even animations on how they work. Google a bit, learn about the algorithms, and give it a try.
Last edited on
Hi nearc,
How fast these algorithms are...
When very few elements are "misplaced" compared to their final sorted order (with respect to the buble sort "direction"), Bubble sort is the fastest.
When few elements are misplaced and your data structure is a kind of list, then "insertion" type of sorting is the fastest : especially when "swaping" two elements is slow.
Almost all other sort algorithm has "static" time process. And one of the fastest is quick sort (when implemented properly, probably with use of move semantics).
But when it comes to sort on files (that is "you cannot store the whole data in memory (RAM)"), then merge sort kind are faster (because they are linear in reading data, like files, list etc.)
So, you see, it depends on several parameters.
For some example, you can find a bubble sort on the forum. But basically, you can search on the web, it's faster. There are a lot of litterature on that and you will never waste your time reading about "sorting". That is a fondamental aspect of computer science and you probably will be inspired in some way or an other by "that" :o)
So to say, just don't read... practice \o/
How fast these algorithms are...
When very few elements are "misplaced" compared to their final sorted order (with respect to the buble sort "direction"), Bubble sort is the fastest.
When few elements are misplaced and your data structure is a kind of list, then "insertion" type of sorting is the fastest : especially when "swaping" two elements is slow.
Almost all other sort algorithm has "static" time process. And one of the fastest is quick sort (when implemented properly, probably with use of move semantics).
But when it comes to sort on files (that is "you cannot store the whole data in memory (RAM)"), then merge sort kind are faster (because they are linear in reading data, like files, list etc.)
So, you see, it depends on several parameters.
For some example, you can find a bubble sort on the forum. But basically, you can search on the web, it's faster. There are a lot of litterature on that and you will never waste your time reading about "sorting". That is a fondamental aspect of computer science and you probably will be inspired in some way or an other by "that" :o)
So to say, just don't read... practice \o/
Topic archived. No new replies allowed.