Quick Sort

Linh B. Ngo

CPSC 3620

Very popular sequential sorting algorithm that performs well with average sequential time complexity of O(nlogn).
First list divided into two sublists.
All numbers in one sublist arranged to be smaller than all numbers in other sublist.
Achieved by first selecting one number, called a pivot, against which every other number is compared. If number less than pivot, it is placed in one sublist, otherwise, placed in other sublist.
Pivot could be any number in list, but often first number chosen. Pivot itself placed in one sublist, or separated and placed in its final position.

_{Wilkinson, Barry, and Michael Allen. Parallel programming. 2nd Ed. 2003.}



In [15]:

    
%%writefile codes/mpi4py/quicksort.py
#!/usr/bin/env python
# quicksort.py
import numpy as np
from mpi4py import MPI
comm = MPI.COMM_WORLD
rank = comm.Get_rank(); size = comm.Get_size(); status = MPI.Status();
N = 16
HAS = 1
HASNOT = 0
unsorted = np.zeros(N, dtype="int")
final_sorted = np.zeros(N, dtype="int")
local_array = None
local_tmp = None
local_tmp_size = np.zeros(1,dtype="int")

if rank == 0:
    unsorted = np.random.randint(low=0,high=N,size=N)
    print ("Unsorted array ", unsorted)
    local_array = unsorted

distance = size / 2
print ("Rank: ", rank)
while (distance >= 1):
    if (rank % distance == 0 and (rank / distance) % 2 == 0):
        print ("Rank ", rank, " send to rank ", int(rank + distance))
        if (local_array is not None):
            if local_array.size == 1 or np.unique(local_array).size == 1:
                comm.Send(local_array[0], dest = rank + distance, tag = HASNOT)
            else:
            #    print ("median is ", np.median(local.array))
                local_tmp = local_array[local_array > np.median(local_array)]
                comm.Send(np.full(shape = 1, fill_value = local_tmp.size, dtype="int"), dest = rank + distance, tag = HAS)
                comm.Send(local_tmp, dest = rank + distance, tag = HAS)
                local_array = local_array[local_array <= np.median(local_array)]
        else:
            comm.Send(np.zeros(1,dtype="int"), rank + distance, tag = HASNOT)
    elif (rank % distance == 0 and (rank / distance) % 2 == 1):
        comm.Recv(local_tmp_size, source = rank - distance, tag = MPI.ANY_TAG, status = status)
        if status.Get_tag() == HASNOT:
            continue
        else:
            local_array = np.zeros(local_tmp_size[0], dtype="int")
            comm.Recv(local_array, source = rank - distance, tag = MPI.ANY_TAG, status = status)
    distance /= 2
#    print (local_array)
    
local_array.sort()
print ("Local array at rank ", rank, ": ", local_array)









    



Overwriting codes/mpi4py/quicksort.py



In [1]:

    
!chmod 755 codes/mpi4py/quicksort.py
!module load gcc/5.3.0 openmpi/1.10.3; mpirun -np 4 codes/mpi4py/quicksort.py









    



Rank:  3
Unsorted array  [ 1 14 10 14 11 14  5 12  2 11 11  3 11  4 11 15]
Rank:  0
Rank  0  send to rank  2
Rank  0  send to rank  1
Rank:  1
Rank:  2
Rank  2  send to rank  3
Local array at rank  2 :  [12 14 14 14]
Local array at rank  3 :  [15]
Local array at rank  0 :  [ 1  2  3  4  5 10]
Local array at rank  1 :  [11 11 11 11 11]

Sorting Conclusions

Computational time complexity using n processors

Odd-even transposition sort - O(n)
Parallel mergesort - O(n) but unbalanced processor load and communication
Parallel quicksort - O(n) but unbalanced processor load, and communication, can degenerate to O(n2)