-------------------------------------------------------------------------------- PROGRAM Introsort -------------------------------------------------------------------------------- INFORMATION -------------------------------------------------------------------------------- Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort, it switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted and it switches to insertion sort when the number of elements is below some threshold. This combines the good parts of the three algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort. Since the three algorithms it uses are comparison sorts, it is also a comparison sort. -------------------------------------------------------------------------------- CHARACTERISTICS -------------------------------------------------------------------------------- Average and worst: O(n log n). Space: O(log n) for in-place implementations. 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 05 C# Visual Studio 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 14 x64 Assembly GUI Turbo Assembler ---6502 Atari--- 15 Atari BASIC Atari BASIC Editor 16 C Deep Blue C ---68000 Atari--- 17 68000 Assembly GFA Assembler for Atari ST 18 GFA Basic GFA Basic Atari ST 19 C HiSoft C Atari ST -------------------------------------------------------------------------------- METHODS/FUNCTIONS (Pseudocode from https://en.wikipedia.org/wiki/Introsort) -------------------------------------------------------------------------------- // --------------------------------------------------------------------------- // sort // Purpose: // Prepare the depth limit and start introsort on the complete input array. // Parameters: // A - array of values to sort. // Returns: // No value; the array is sorted in place. // Side effects: // Reorders A and invokes the sorting helpers. // --------------------------------------------------------------------------- procedure sort(A : array): maxdepth <- log2(length(A)) × 2 introsort(A, maxdepth) // --------------------------------------------------------------------------- // introsort // Purpose: // Sort a range using quicksort-style partitioning, switching to insertion // sort for short ranges and heapsort when the recursion budget is exhausted. // Parameters: // A - range of values to sort in place. // maxdepth - remaining partition budget; each recursive level reduces it. // Returns: // No value; A is sorted in place. // Side effects: // Reorders A and selects one of the three sorting strategies. // --------------------------------------------------------------------------- procedure introsort(A, maxdepth): n <- length(A) if n < 16: insertionsort(A) else if maxdepth = 0: heapsort(A) else: p ← partition(A) // assume this function does pivot selection, p is the final position of the pivot introsort(A[1:p-1], maxdepth - 1) introsort(A[p+1:n], maxdepth - 1) -------------------------------------------------------------------------------- // --------------------------------------------------------------------------- // insertionsort // Purpose: // Sort a small array by inserting each value into the already ordered prefix. // Parameters: // A - array of values to sort in place. // Returns: // No value; A is sorted. // Side effects: // Shifts larger values one position right to make room for each insertion. // --------------------------------------------------------------------------- procedure insertionsort(A) is for index <- 1 to length(A) - 1 do value <- A[index] position <- index - 1 while position >= 0 and A[position] > value do A[position + 1] <- A[position] position <- position - 1 A[position + 1] <- value -------------------------------------------------------------------------------- // --------------------------------------------------------------------------- // heapsort // Purpose: // Sort the array with a max heap, providing introsort's O(n log n) fallback. // Parameters: // A - array of values to sort in place. // Returns: // No value; A is sorted. // Side effects: // Builds and repeatedly shrinks a max heap over A. // --------------------------------------------------------------------------- procedure heapsort(A) is build a max heap from A repeatedly move the root to the end and restore the remaining max heap -------------------------------------------------------------------------------- // --------------------------------------------------------------------------- // partition // Purpose: // Divide the array around a pivot so recursive introsort calls handle // smaller ranges on either side. // Parameters: // A - array range to rearrange in place. // Returns: // The pivot's final index, which separates the resulting ranges. // Side effects: // Reorders elements while preserving all values. // --------------------------------------------------------------------------- function partition(A) is choose a pivot and move it to the end of A move values less than or equal to the pivot before it move the pivot to its final position return the pivot's final index -------------------------------------------------------------------------------- SEE ALSO: Heapsort.txt -------------------------------------------------------------------------------- // --------------------------------------------------------------------------- // readSortingInput // Purpose: // Read the integer records from the named text file into an array. // Parameters: // filePath - path of the input file. // Returns: // The array of parsed integers. // Side effects: // Opens and closes the input file. // --------------------------------------------------------------------------- function readSortingInput(filePath) is values <- empty array open filePath for reading for each line in filePath do append integer(line) to values close filePath return values --------------------------------------------------------------------------------