--------------------------------------------------------------------------------
PROGRAM Heapsort
--------------------------------------------------------------------------------
INFORMATION
--------------------------------------------------------------------------------
Heapsort is an efficient, comparison-based sorting algorithm that organizes an
array into a binary heap data structure to sort elements in O(n log n) time.
--------------------------------------------------------------------------------
CHARACTERISTICS
--------------------------------------------------------------------------------
Best, average, and worst: O(n log n). Space: O(1). Stable: No.
--------------------------------------------------------------------------------
LANGUAGES TO IMPLEMENT IN
--------------------------------------------------------------------------------
#	LANGUAGE		IDE												
--	---------		----------------------------------------------	
01	Ada				GNAT Studio										
02	BASIC			GW-BASIC										
03	C\C++			Borland C++										
04	C++ .NET		Visual Studio  2026								
05	C#				Visual Studio  2026								
06	COBOL			OpenCobolIDE									
07	Java			Eclipse											
08	Lua				ZeroBrane Studio								
09	Pascal			Turbo Pascal									
10	Perl			Notepad++ -> Command Line						
11	PowerShell		Notepad++ -> Windows PowerShell					
12	Python			Idle											
13	VB .NET			Visual Studio 2026								
14	Haskell			Emacs											
15	x64 Assembly	Visual Studio 2026								
---6502 Atari---
16	6502 Assembly	Atari Assembler Editor
17  Atari BASIC		Atari BASIC Editor								
18	C				Deep Blue C
---68000 Atari---
19	68000 Assembly	GFA Assembler for Atari ST
20  GFA Basic		GFA Basic Atari ST								
21  C				Borland's Turbo C for Atari ST
--------------------------------------------------------------------------------
VARIABLES
--------------------------------------------------------------------------------
Max_Values  - Total Number Of Values To Be sorted (unsigned integer) = 1000
Values      - Array of Integers
Count       - Unsigned Integer for Looping
Elapsed     - End_Time - Start_Time
--------------------------------------------------------------------------------
METHODS/FUNCTIONS
--------------------------------------------------------------------------------
NAME        : Sift_Down
FUNCTION    : To repair the heap property by moving a value downward until it is 
              in the correct position.
ACCEPTS     : Start_Node (unsigned int)
              End_Node (unsigned int)  
RETURNS     : Nothing
LOCAL VARS  : Root (unsigned int)
              Child (unsigned int)
              Temp (integer)
PSEUDOCODE  :    
	Root = Start_Node
    WHILE (2 * Root + 1) < End_Node
         -- Select the left child
         Child = (2 * Root + 1);
         -- If the right child is larger, it becomes the larger child to swap with.
         IF (Child + 1) < End_Node 
            AND Values(Child) < Values(Child + 1) THEN
                -- Choose the right child
                Child = (Child + 1);
         END IF
         IF Values(Root) >= Values(Child) RETURN
         -- Perform the swap
         Temp = Values(Root);
         Values(Root) = Values(Child);
         Values(Child) = Temp;
         Root = Child;
    END WHILE
--------------------------------------------------------------------------------
NAME        : Load_File
FUNCTION    : Reads all integers from the input file into the Values array.
ACCEPTS     : FileSpec (string)
RETURNS     : Nothing
LOCAL VARS  : Input_File (file pointer)
PSEUDOCODE  :    
    PRINT "READING INPUT FILE..."
    OPEN Input_File AS INPUT USING FileSpec
    WHILE NOT EOF
        READ FROM Input_File INTO Values(Count)
        INCREMENT Count
		IF Count > Max_Values THEN EXIT LOOP
    END WHILE
    CLOSE(Input_File)
    PRINT "DONE."
--------------------------------------------------------------------------------
NAME        : Save_File
FUNCTION    : Saves all integers from Values array into the given output file.
ACCEPTS     : FileSpec (string)
RETURNS     : Nothing
LOCAL VARS  : Output_File (file pointer)
PSEUDOCODE  :    
    PRINT "WRITING OUTPUT FILE..."
    CREATE Output_File AS OUTPUT USING FileSpec
    FOR EACH Count in Values()
        WRITE TO Output_File Values(Count)
    NEXT 
    CLOSE(Output_File)
    PRINT "DONE."
--------------------------------------------------------------------------------
NAME        : Perform_Sort
FUNCTION    : Builds a heap, repeatedly extracts the maximum value, and measures 
              runtime.
ACCEPTS		: Nothing
RETURNS     : Nothing
LOCAL VARS  : Start_Time (time)
              End_Time (time)
              Temp (integer)
		      Start_Index (unsigned int)
              End_Index (unsigned int)  
PSEUDOCODE  :    
    PRINT "SORTING ELEMENTS..."
    Start_Time = CURRENT TIME
    IF Count > 1 THEN
        // Build the Max-Heap
        LOOP BACKWARDS FROM Count / 2 - 1 TO ZERO
            Sift_Down(Start_Index, Count)
        END LOOP
        // Sort the array
        LOOP BACKWARDS FROM Count -1 TO 1
            Temp = Values(0)
            Values(0) = Values(End_Index)
            Values(End_Index) = Temp
            Sift_Down(0, End_Index)
        END LOOP
    END IF
    End_Time = CURRENT TIME
    PRINT "DONE."
    Elapsed = End_Time - Start_Time
--------------------------------------------------------------------------------
NAME        : Main
FUNCTION    : Main program flow
ACCEPTS     : Nothing
RETURNS     : Nothing
LOCAL VARS  : None
PSEUDOCODE  :    
	Count = 0
    PRINT "***HEAPSORT [LANGUAGE]***"
    Load_File("D:\Sorting\Sorting_Input.txt") 
    Perform_Sort()
    Save_File("D:\Sorting\Output_[LANGUAGE].txt")    
    PRINT "***RUN COMPLETE***"
    PRINT "HEAPSORT TOOK {Elapsed} SECONDS."
--------------------------------------------------------------------------------