[GO] Heap-Sortierung in C-Sprache

Am Anfang

Ich wollte verschiedene Algorithmen in C-Sprache erstellen, also schreibe ich zunächst eine Heap-Sortierung.

Nachschlagewerk

"Datenstruktur und Algorithmus (von Atsushi Sugihara)" [Klicken Sie hier für Amazon](https://www.amazon.co.jp/%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0%E3 % 81% A8% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0-% E6% 9D% 89% E5% 8E% 9F-% E5% 8E% 9A% E5% 90% 89 / dp / 4320120345)

Was ist Heap-Sortierung?

Der einfachste Weg, mit Binärbäumen zu sortieren, ist das schnelle Sortieren. In den meisten Fällen erfordert die schnelle Sortierung eine Berechnungszeit von O (nlogn). Wenn Sie jedoch Pech haben (der sortierte Wert ist in der Eingabe enthalten), dauert die Berechnungszeit von O (n ^ 2). Die Heap-Sortierung füllt dieses Manko.

Haufen

Es gibt zwei Heap-Bedingungen

(1)Binärbaum ist Tiefe k-Alle Eckpunkte kleiner oder gleich 1 werden verwendet, und Eckpunkte mit der Tiefe k werden in der Reihenfolge von links verwendet.
(2)F wenn der Scheitelpunkt u der Elternteil des Scheitelpunkts v ist(u) ≥ f(v)Ist

Wenn diese beiden Bedingungen erfüllt sind, wird der Binärbaum als Heap bezeichnet.

Haufen sortieren

Zunächst werden alle Werte gespeichert und ein Heap erstellt. Wenn die Bedingung (2) während der Erstellung nicht erfüllt ist, werden der Scheitelpunkt und der übergeordnete Scheitelpunkt vertauscht und der Heap korrigiert. Die Berechnungszeit zu diesem Zeitpunkt beträgt maximal O (nlogn) in einem Binärbaum mit n Eckpunkten. Das Folgende ist die Heap-Sortiermethode.

1. Wenn Sie alle Werte speichern und einen Heap erstellen können, hat der Heap den Maximalwert im Stammverzeichnis. Notieren Sie diesen Wert also ganz am Ende des Sortierergebnisses.
2. Da der Stammwert entfernt wird, muss ein alternativer Wert in diesem Stamm gespeichert werden. Stattdessen wird der tiefste und am weitesten rechts liegende Wert des Binärbaums gespeichert und ein temporärer Wert gespeichert. Machen Sie einen Zustand.
3. In diesem vorläufigen Zustand ist die Bedingung (2) nicht erfüllt, daher werden die übergeordneten und untergeordneten Werte erneut ausgetauscht.

Diese Wiederholungen sind Haufenarten.

Implementierung der Heap-Sortierung

Dieses Mal werde ich, wie der Titel schon sagt, in C-Sprache schreiben.

Heap erstellen

Erstellen Sie zunächst den Heap. Da der Index bis zu 0, 1, ..., n ist, ist der übergeordnete Index (i -1) / 2, wenn der untergeordnete Index i ist. Dies kann durch Schreiben eines Binärbaums verstanden werden. Erstellen Sie damit ein Programm.

HeapFunction

/*Heap erstellen*/
/*Komm zurück mit weiter*/
i = 0;
while (i < n)
{
    if (num_array[i] > num_array[(i - 1) / 2])
    {
        swap(&num_array[i], &num_array[(i - 1) / 2]);
        i = 0;
        continue;
    }
    i++;
}

n ist die Anzahl der Elemente im Array. Nach dem Austausch von Werten mit Swap beginne ich weiterhin mit dem Root-Wert. Die in der if-Anweisung verwendete Swap-Funktion ist meine eigene.

SwapFunction

void	swap(int *a, int *b)
{
	int tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
}

Fertig

Wenn ein Heap erstellt wird, ist index = 0 der Maximalwert. Tauschen Sie diesen Wert also gegen den letzten Wert im Array aus. Nach dieser Operation nimmt der Wert des ersten Ketsu nicht an der Heap-Operation teil. Verwenden Sie daher den Wert ht (Heap-Zeiten), um die Länge des Arrays nacheinander zu verringern.

Die Operation wurde ebenfalls hinzugefügt, um die Funktion heap_sort zu vervollständigen.

HeapFunction

void	heap_sort(int *num_array, int n)
{
	int 	i;
	int 	ht;

	hi = 0;
	while (ht < n - 1)
	{
		/*Heap erstellen*/
		i = 0;
		while (i < n - ht)
		{
			if (num_array[i] > num_array[(i - 1) / 2])
			{
				swap(&num_array[i], &num_array[(i - 1) / 2]);
				i = 0;
				continue;
			}
			i++;
		}
		swap(&num_array[n - ht - 1], &num_array[0]);
		hi++;
	}
}

Drehen Sie, bis die Heap-Zeiten n-1-mal erreichen. Nach jeder Heap-Operation wird swap verwendet, um den Root-Wert und den Wert des Ketsu des Arrays zu diesem Zeitpunkt auszutauschen.

Programmausführung

Das ganze Programm sieht so aus, einschließlich der Hauptfunktion.

heap_sort.c

#include <stdio.h>

void    swap(int *a, int *b)
{
    int tmp;

    tmp = *a;
    *a = *b;
    *b = tmp;
}

void    heap_sort(int *num_array, int n)
{
    int i;
    int hi;

    hi = 0;
    while (hi < n - 1)
    {
        /*Heap erstellen*/
        i = 0;
        while (i < n - hi)
        {
            if (num_array[i] > num_array[(i - 1) / 2])
            {
                swap(&num_array[i], &num_array[(i - 1) / 2]);
                i = 0;
                continue;
            }
            i++;
        }
        swap(&num_array[n - hi - 1], &num_array[0]);
        hi++;
    }
}

void    print_num_array(int *num_array, int n)
{
    int i;

    i = 0;
    while (i < n)
    {
        printf("%d ", num_array[i]);
        i++;
    }
    printf("\n");
}

int     main(void)
{
    int num_array[] = {23, 5, 900, 45, 11, 65, 4, 0, 0, 9, 432, 43, 444, 899};
    int num;

    num = sizeof(num_array) / sizeof(int);
    printf("----Vor dem Sortieren----\n");
    print_num_array(num_array, num);
    heap_sort(num_array, num);
    printf("----Vor dem Sortieren----\n");	
    print_num_array(num_array, num);
    return (0);
}

Ausführungscompiler, Ausführungsoptionen

gcc -Wall -Wextra -Werror heap_sort.c

Ausführungsergebnis

[zippowriter qiita]$ ./a.out
----Vor dem Sortieren----
23 5 900 45 11 65 4 0 0 9 432 43 444 899
----Nach dem Sortieren----
0 0 4 5 9 11 23 43 45 65 432 444 899 900

Es hat vorerst funktioniert.

Am Ende

Ich habe die Wörter im Nachschlagewerk ehrlich in den Code geschrieben, daher weiß ich ehrlich gesagt nicht, ob dies die richtige Antwort ist. Die Verschachtelung ist tiefer geworden, daher möchte ich in der Lage sein, intelligenteren Code zu schreiben.