Voraussetzung: HeapSort Die
Heap-Sortierung ist eine vergleichsbasierte Sortiertechnik, die auf der B inary Heap- Datenstruktur basiert . Es ähnelt der Auswahlsortierung, bei der wir zuerst das maximale Element finden und das maximale Element am Ende platzieren. Wir wiederholen den gleichen Vorgang für das verbleibende Element.

Wir implementieren hier die Heap-Sortierung, rufen sie für Zufallslisten unterschiedlicher Größe auf, messen die für verschiedene Größen benötigte Zeit und erstellen ein Diagramm der Eingabegröße gegen die benötigte Zeit.

  
import time 
from numpy.random import seed 
from numpy.random import randint 
import matplotlib.pyplot as plt 
  
  
def left(i): 
    return 2 * i + 1
  
def right(i): 
    return 2 * i + 2
  
def heapSize(A): 
    return len(A)-1
  
  
def MaxHeapify(A, i): 
    
    l = left(i) 
    r = right(i) 
      
    
    
    if l<= heapSize(A) and A[l] > A[i] : 
        largest = l 
    else: 
        largest = i 
    if r<= heapSize(A) and A[r] > A[largest]: 
        largest = r 
    if largest != i: 
       
        A[i], A[largest]= A[largest], A[i] 
       
        MaxHeapify(A, largest) 
      
def BuildMaxHeap(A): 
    for i in range(int(heapSize(A)/2)-1, -1, -1): 
        MaxHeapify(A, i) 
          
def HeapSort(A): 
    BuildMaxHeap(A) 
    B = list() 
    heapSize1 = heapSize(A) 
    for i in range(heapSize(A), 0, -1): 
        A[0], A[i]= A[i], A[0]  
        B.append(A[heapSize1]) 
        A = A[:-1] 
        heapSize1 = heapSize1-1
        MaxHeapify(A, 0) 
          
  
elements = list() 
times = list() 
for i in range(1, 10): 
  
    
    a = randint(0, 1000 * i, 1000 * i) 
    
    start = time.clock() 
    HeapSort(a) 
    end = time.clock() 
  
    
    print(len(a), "Elements Sorted by HeapSort in ", end-start) 
    elements.append(len(a)) 
    times.append(end-start) 
  
plt.xlabel('List Length') 
plt.ylabel('Time Complexity') 
plt.plot(elements, times, label ='Heap Sort') 
plt.grid() 
plt.legend() 
plt.show() 

Ausgabe :

Eingabe: Unsortierte Listen unterschiedlicher Größe werden zufällig generiert
Ausgabe :
1000 Elemente sortiert nach HeapSort in 0.023797415087301488
2000 Elemente, sortiert nach HeapSort in 0.053856713614550245
3000 Elemente, sortiert nach HeapSort in 0.08474737185133563
4000 Elemente, sortiert nach HeapSort in 0.13578669978414837
5000 Elemente, sortiert nach HeapSort in 0.1658182863213824
6000 Elemente sortiert nach HeapSort in 0.1875901601906662
7000 von HeapSort in 0.21982946862249264 sortierte Elemente
8000 Elemente, sortiert nach HeapSort in 0.2724293921580738
9000 Elemente sortiert nach HeapSort in 0.30996323029421546
Das Komplexitätsdiagramm für die Heap-Sortierung ist unten angegeben