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.
Win a copy of Real-World Software Development: A Project-Driven Guide to Fundamentals in Java this week in the Agile and Other Processes forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Bear Bibeault
  • Liutauras Vilda
  • Devaka Cooray
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • Henry Wong
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • Tim Holloway
Bartenders:
  • salvin francis
  • Frits Walraven
  • Piet Souris

Sorting with 1 million integers

 
Ranch Hand
Posts: 159
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
I am trying to display cpu utilization. I am getting zero value for it.

I am trying to run my sorting program with 1 million integers but my system hangs up.

I am using following following command:

In the above code, I am trying to run my selection sort program with 1000000 integers
How to solve this problem in Python?
Is there any size limitation with integers in python?
Zulfi.
 
Saloon Keeper
Posts: 21717
148
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Zulfi Khan
Ranch Hand
Posts: 159
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
Thanks for your reply.

Can python integer variables hold values greater than 66000?

Zulfi.
 
Ranch Hand
Posts: 43
1
Python VI Editor Postgres Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Zllfi,

Is there a limit to the size of an integer?  The short answer is no.

The python documentation at https://docs.python.org/3/reference/lexical_analysis.html#operators states:

There is no limit for the length of integer literals apart from what can be stored in available memory.


Thus python integers are limited only by the amount of memory on the computer.

HTH,
Travis
 
Author
Posts: 8
5
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Zulfi,

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
 
Marshal
Posts: 67979
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
 
Campbell Ritchie
Marshal
Posts: 67979
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Saloon Keeper
Posts: 11462
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote: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.


You only need a copy of half of the original array for a stable sort:
 
Something about .... going for a swim. With this tiny ad ...
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!