S N log log N sort

[phillip1882]

so i had the idea of taking quicksort and making the number of pivots scale to the size of the input logarithmically.
here is the result:

import math, random
def prettyQuick(data):
   if len(data) < 16:
      for i in range(1,len(data)):
         j = i
         while data[j] < data[j-1] and j > 0:
            data[j], data[j-1] =data[j-1], data[j]
            j-=1
      return(data)
   totpivit = int(math.log(len(data),4))
   pivits = []
   for i in range(0,totpivit):
      pivits += [data[random.randint(0,len(data)-1)]]
   for i in range(len(pivits),-1,-1):
      for j in range(0,i-1):
         if pivits[j] > pivits[j+1]:
            pivits[j], pivits[j+1] = pivits[j+1], pivits[j]
   data = orderT(data,pivits)
   return data


def orderT(data,pivits):
   bucket = []
   for i in range(0,len(pivits)+1):
      bucket += [[]]
   for i in range(0,len(data)):
      gotHere = True
      for j in range(0,len(pivits)):
         if data[i] <pivits[j]:
            bucket[j] += [data[i]]
            gotHere = False
            break
      if gotHere == True:
         bucket[-1] +=[data[i]]
   result = []
   for i in range(0, len(bucket)):
      if bucket[i] == []:
         continue
      result += prettyQuick(bucket[i])
   return result
data = list(range(0,1000))
random.shuffle(data)
print(data)
data =prettyQuick(data)
print(data)

 

[WhiteCube]

My gut tells me that there's no advantage in having more than one pivot.

With one pivot, partitioning an array needs only 2 pointers and 1 temporary variable.

On the other hand, I'm wrong a lot, so I would test that with a program.

I'd have 2 versions, single pivot, and multi pivot. I would count the number of comparisons, and the number of moves.

 

[WhiteCube]

The compares are roughly the same for single pivot and multi pivot.

If the language is doing += of arrays without moves (linked list?), then SP and MP are similar.

If the a += b costs 1 move per element of b, then MP does twice as much moving as SP.

I could be wrong.

 

[phillip1882]

i went ahead and timed the two sorts. prettyQuick on 10,000,000 values, took roughly 34.7 seconds with the multiple pivots, and took roughly 70.7 seconds with the 1 pivot. i couldn't get a counting of number of comparisons to work properly.

 

[WhiteCube]

The more pivots the better. Less recursion. A key gets closer to its final position using fewer jumps.

The time cost is joining the buckets back together.

A single pivot has more recursion, but doesn't need any buckets.

Are you using the same program to compare times? If so, your 1 pivot quicksort is using 2 buckets for no reason.

 

[phillip1882]

yes i weas using the same program for both. i'll try standard quick sort for time, see if that's any faster.

ok i tried the standard quicksort algorithm, and clocked in at 30 seconds for 10,000,000 values.

 

[phillip1882]

i went ahead and tried the standard 2 pivot quick sort and clocked in at 21.5 seconds.