I measured some sorts with Python.
Bubble sort This is the simplest and easiest sorting method, and the amount of calculation is about $ O (n ^ 2) $ for the input size n. The algorithm is very simple, it sorts in order for a given array.
The following is a program that randomly generates 1000 elements and sorts them with Bubble sort.
bubble.py
import time
import numpy as np
def BUBBLE_SORT(A):
n = np.size(A)
m = n-1
while m > 1:
k = 0
while k < m :
if A[k] > A[k+1]:
A[k],A[k+1] = A[k],A[k+1]
k += 1
m -= 1
return A
# mesure time from here
start = time.time()
# set the range for random
Min = 1
Max = 1000
N = Max
# get a list consisted by N random integers in [min,max]
LIST = np.random.randint(Min,Max,N)
# sorting by bubble
BUBBLE_SORT(LIST)
print LIST
print str(time.time()-start) + 'sec'
As a result of measuring about 10 times, the average execution time was about 0.87 sec. This is the first time to measure the execution time, and is this all right?
Quick sort As the name of Quick suggests, it's fast. The (average) amount of calculation is $ O (n \ log {n}) $, which is a very fast sorting method compared to Bubble sort. From the first given sequence, take one suitable element (called a pivot) and divide it into larger and smaller ones. And the method of giving the same operation to the divided ones. (See Wiki for details)
The following is a program that randomly generates 1000 elements and sorts them with Quick sort.
quick.py
import time
import numpy as np
#ignore exception
def QUICK_SORT(A,L,R):
if L < R:
p = L
k = L+1
while k <= R:
if A[k] < A[L]:
A[p+1], A[k] = A[k], A[p+1]
p += 1
k += 1
A[L], A[p] = A[p], A[L]
A = QUICK_SORT(A,L,p-1)
A = QUICK_SORT(A,p+1,R)
return A
# measure time from here
start = time.time()
# set the range for random
Min = 1
Max = 1000
N = Max
# get a list consisted by N random integers in [min,max]
LIST = np.random.randint(Min,Max,N)
N -= 1
# sort by quick
LIST = QUICK_SORT(LIST,0,N)
print LIST
print str(time.time()-start) + 'sec'
As a result of measuring 10 times, the execution time was 0.21 sec on average. However, in reality, this sort is unstable, and if you continue to select pivots that deviate significantly from the median, the result will be as long as Bubble sort (the worst case complexity is $ O (n ^ 2) $).
… Hmm, is it okay like this… Can Quicksort be parallelized? If there is anything else that looks interesting, I will write it again! Then
In the comments, I received a request for "Bogosort", so I will post it for the time being. .. .. (Lol) Below is a program that randomly generates 10 elements and sorts them with Bogo sort.
bogo.py
import numpy as np
import time
start = time.time()
def BOGO_SORT(A):
set_range = range(0,A.size -1)
# if A is ssorted, ignore while
while not isSorted(A,set_range):
np.random.shuffle(A)
def isSorted(B,Range):
for i in Range:
# if there exist some illegal in the given array, return false
if B[i] > B[i+1]:
return False
return True
# measure time from here
start = time.time()
# set the range for random
Min = 1
Max = 10
N = Max
# get a list consisted by N random integers in [min,max]
LIST = np.random.randint(Min,Max,N)
# sorting by bubble
BOGO_SORT(LIST)
print LIST
print str(time.time()-start) + 'sec'
Bubble sort and Quicksort gave a nice average run time (because the standard deviation was small), but not Bogo sort. The execution time was in the range of about 3.79sec to 47.25sec.
Bogo sort is an unstable sort, and the (average) complexity is $ O (nn!) $. … It's not very practical (; ´ ･ ω ･)