This week's book giveaway is in the Agile and Other Processes forum. We're giving away four copies of Real-World Software Development: A Project-Driven Guide to Fundamentals in Java and have Dr. Raoul-Gabriel Urma & Richard Warburton on-line! See this thread for details.
There are many different types of sorts, each with its own best and worst cases. For example, the QuickSort is one of the fastest sorts oridinarily, but if the values being sorted are already mostly in order it will run very slowly. On the other hand, a bubble Sort is generaly very slow, but not if the elements being sorted are already mostly in order. I once had a project where everything was in order except for a couple of "high" values right in the middle. The optimal sort algorithm for that was the Shell-Metzner sort.
Sort performance can also be impacted when running on a virtual memory system where there aren't enough page slots to hold the entire set of data in RAM. If there are lots of page faults, performance will be absolutely awful, since swapping pages is a thousand times or more slower than direct memory access.
Got idle CPU cycles? Join the war on COVID-19 by donating them to find the coronavirus' weak spots. folding@home Runs in the background. https://foldingathome.org
posted 1 week ago
Thanks for your reply.
Can python integer variables hold values greater than 66000?
I don't think your program is necessarily hanging up because there's a bug in it. (You did try the sorting program with a smaller list of numbers, right?) And like Travis said, you can make integers as big as you want in Python, so that's not the problem either.
Instead, I think your sorting program is just taking a really long time to run. The selection sort algorithm has quadratic time complexity, which is a fancy way of saying that if you make the list a thousand times longer, selection sort will take a MILLION times longer to sort it! As Tim mentioned, there are other sorting algorithms you can write that might be able to sort your list more quickly.
Carter Sande wrote:. . . . The selection sort algorithm has quadratic time complexity . . .
About 14 years ago, I ran an exercise to sort 1,000,000 “random” ints in an array. Bubble sort took about 1hr40min to sort it. The built‑in method in Arrays#sort took about 0.4sec. If you look at the method documentation, you will find out what sort of algorithm it uses. I also counted how often a test for inequality was made: 499,999,500,000×, i.e. (n − 1) × n ÷ 2 If you look at this overloading of the method, you will find they use a different algorithm, and it tells you why.
When I made my little experiment, the number of inequality tests with selection sort, which I had been taught was faster than bubble sort, was 499,999,500,000. Selection sort ran faster than bubble sort: about 1hr39min!
By calculating the comparisons made with quicksort or merge sort (nlog(n)) (here about 20,000,000), you can make a rough guess how long it takes to execute each stage in the process 6,000 ÷ 500,000,000,000sec (=1.2ns) for bubble sort and 0.4 ÷ 20,000,000sec (=200ns) for Arrays#sort. So Arrays#sort won't be quicker at sorting a small array than bubble sort
posted 6 days ago
As to what Tim H said about memory, a merge sort runs much more happily if you have two copies of the data structure, one to use as soruce and one as destination. But that means increased memory consumption. On a modern computer, memory is very cheap and plentiful, so that shouldn't be a significant problem.