Clash Royale CLAN TAG#URR8PPP

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

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

This question appears to be off-topic. The users who voted to close gave this specific reason:

3 Answers
3

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:

N=10,000,000

M=100

O(N+M)

O(N*log N)

O(M)

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.

key

Counter

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.}

O(logN * M)

N

logN

logN

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


random.shuffle

random.shuffle

import

import

importlib

shuffle

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

numpy

numpy array

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]


scipy.ndimage