How to sort 10million number in python without using sort function?

Question

Sort the list of random generated 10 Million numbers between 1 and 100, in python without using inbuilt functions, Quicksort didnt worked for me here.

I have used quicksort code from the mentioned link: http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.html

Error I got while implementing it : for x in range (0, 100000): listOfNumbers.append(random.randint(1, 100))

quickSort(listOfNumbers) print(listOfNumbers)

RuntimeError: maximum recursion depth exceeded

Are you sure you used quicksort correctly? Maybe start with bubble sort if you couldn't get quicksort. http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html — Mike, Aug 06 '18 at 16:31
What do you mean quicksort didn't work for you? Your implementation didn't work? — Easton Bornemeier, Aug 06 '18 at 16:31
You can write something a lot simpler—and more efficient—than quicksort for this problem. As a hint: if you had a list of 100 counts, could you turn that into a list of 10 million numbers in sorted order? — abarnert, Aug 06 '18 at 16:35
Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. — Prune, Aug 06 '18 at 16:38
@Easton, I tried quicksort. It worked fine for 1000 numbers. But with 10000 numbers, it showed error : Tree limit exceeded. — Ashish, Aug 06 '18 at 16:58
@Ashish Your quicksort implementation recurses too much. If you show it to us, maybe we could show you how to fix it, but as it stands, your question is basically equivalent to "I wrote a broken quicksort, tell me how to fix it without seeing the code or even a description of it", which is impossible to answer. — abarnert, Aug 06 '18 at 17:54
@abarnert,Below is my code that implements quicksort: Part1: — Ashish, Aug 06 '18 at 18:11
Don't try to put it in a comment. Comments are limited in size, and screw up formatting, and can't see seen by people looking for a good question in the queue, or found by search engines, etc.. Edit your question to add it there. — abarnert, Aug 06 '18 at 18:12
Please put the relevant code in the question, not in an external link. And also, format your code as code (select it and use the `{}` icon or Ctrl-K, or manually add 4 spaces before each line). — abarnert, Aug 06 '18 at 19:01
Here is a link to an [example of quicksort partition in C](https://stackoverflow.com/questions/47964255/quicksort-with-many-elements-causes-stackoverflowerror/47964618#47964618) that avoids stack overflow by modifying the partition function to only use recursion on the smaller partition and to use iteration (loop) for the larger partition. Although this reduces stack overhead complexity to (O log(n)), it doesn't prevent time complexity O(n^2). As answered below, since the range is limited to 1 to 100, using a counting sort would be much faster. — rcgldr, Aug 07 '18 at 01:14

score 2 · Accepted Answer · answered Aug 06 '18 at 18:09

You can use any sort algorithm you want, as long as you implement it right. But the problem is calling out for a radix sort. In particular, the dumbest kind of radix sort, a bucket-counter.

You have N=10,000,000 total values and a range of M=100 distinct values. A bucket counter will take O(N+M) time, which is better than O(N*log N), and O(M) space,¹ which is negligible—and. best of all, it's dead simple:

def bucketsorted100(xs):
    buckets = [0] * 101
    for x in xs:
        buckets[x] += 1
    for x, count in enumerate(buckets):
        yield from [x] * count

You can obviously extend this to not be hardcoded for numbers from 1-100 (actually, I hardcoded it for numbers from 0-100, wasting 1% space, but who cares?). Or you can add support for a key function. Or you can make it even simpler by using a Counter instead of a list.

_{1. Technically, it's O(logN * M) space, because the counts range up to N, which takes logN bits, which the values only range up to 100, which takes a constant number of bits. But practically, all of the counts fit into a single 30-bit "digit" in CPython, so the logN factor never comes up.}

Thanks Abanert for your answer. Just adding a bit modification of it. import random listOfNumbers=[] def bucketsorted100(xs): buckets = [0] * 101 for x in xs: buckets[x] += 1 for x, count in enumerate(buckets): if(count>0): yield [x] * count for x in range (0, 1000000): listOfNumbers.append(random.randint(1, 100)) #Calling function: tuple(bucketsorted100(listOfNumbers)) It worked for me(in less than 5 seconds) — Ashish, Aug 06 '18 at 18:59
@Ashish With your modification, this no longer produces an iterable of the sorted values, it now produces an iterable of _lists_ of values, which you have to flatten. But if that's OK for your use, that's fine. — abarnert, Aug 06 '18 at 19:05

score 1 · Answer 2 · answered Aug 06 '18 at 16:34

1

You can use the mighty Bogosort.

import random

def is_sorted(data):
    for i in range(len(data) - 1):
        if data[i] > data[i + 1]:
            return False
    return True

def bogosort(data):
    while not is_sorted(data):
        random.shuffle(data)
    return data

answered Aug 06 '18 at 16:34

Gabriel

1,922
2
19
37

1

But this uses the “inbuilt function” `random.shuffle`. Otherwise, of course, it would be perfect. :) – abarnert Aug 06 '18 at 16:36
@abarnert But `random.shuffle` [is not listed as a built in function](https://docs.python.org/3/library/functions.html) so I think we're good -- Unless you consider `import` statement to be a built in function... – Gabriel Aug 06 '18 at 16:39
@ gabriel Random.shuffle will not be considered as inbuilt function – Ashish Aug 06 '18 at 16:56
Well, the `import` statement isn't a function—it does call a bunch of functions from `importlib`, but those are implemented in Python, just like `shuffle` is, so I don't think it makes much difference. – abarnert Aug 06 '18 at 17:51
Thanks for your help !!! But,BogoSort is taking a lot of time. – Ashish Aug 06 '18 at 18:28
1

@Ashish It works best if you're lucky. – Gabriel Aug 06 '18 at 18:35
@Ashish Gabriel put a link to a description of Bogosort in the answer. If you read it, you'll see that taking a lot of time (unless you're very lucky) is expected behavior. – abarnert Aug 06 '18 at 19:03

score 0 · Answer 3 · answered Aug 06 '18 at 16:41

0

Maybe numpy will be faster... you can convert numbers to a numpy array then use numpy.sort

Like this:

import numpy as np
mylist=[15,65,3,1,10,35,11,65,23,95,20,36,85,12,37,85,46,93] # ...
sorted_mylist=np.ndarray.tolist(np.sort(np.asarray(mylist)))
print sorted_mylist

which give you:

[1, 3, 10, 11, 12, 15, 20, 23, 35, 36, 37, 46, 65, 65, 85, 85, 93, 95]

answered Aug 06 '18 at 16:41

A. STEFANI

6,707
1
23
48

1

Sometimes I feel numpy is the jQuery of Python. – Gabriel Aug 06 '18 at 16:42
Since Numpy is implemented in C, it makes sense that we'd be seeing a huge improvement over our pure Python Sort – A. STEFANI Aug 06 '18 at 16:44
NumPy's hybrid introsort/heapsort implemented in C still isn't going to be anywhere near as fast as a radix sort implemented in C for this problem… – abarnert Aug 06 '18 at 17:50
1

@Gabriel But can numpy generate freehand circles? Not very easy… unless you add in `scipy.ndimage`. :) – abarnert Aug 06 '18 at 18:13

How to sort 10million number in python without using sort function?

3 Answers3