Replacement Selection Sort - from Advanced Databases Lecture 6

replacement_selection_sort.py

import heapq
import random

class HeapSorter:
  def __init__(self, num_blocks, input_sequence):
    self.num_blocks = num_blocks
    self.input_sequence = input_sequence

  def sorted(self):
    return heapq.merge(*self.__sorted_subsequences__())

  def __sorted_subsequences__(self):
    # Initialization: read B pages into the current_heap
    current_heap = [self.input_sequence.pop(0) for x in xrange(self.num_blocks)]
    heapq.heapify(current_heap)
    next_heap = []
    current_run = []

    while current_heap:
      # Write the lowest key from current heap into the current_run
      lowest = heapq.heappop(current_heap)
      current_run.append(lowest)

      # Get next input (if any) and store in correct heap
      if self.input_sequence:
        next_element = self.input_sequence.pop(0)
        heapq.heappush(current_heap if next_element >= lowest else next_heap, next_element)

      # If current heap exhausted, swap heaps and yield the sorted subsequence
      if not current_heap:
        current_heap, next_heap = next_heap, current_heap
        yield current_run
        current_run = []

if __name__ == "__main__":
  sorter = HeapSorter(10, [random.randrange(10000) for x in xrange(100)])
  print(list(sorter.sorted()))