FreeBASIC クイック・ソート・ルーチン

'linear indexing of sorted Data
'Re: Dictionary Class
'by paul doe ≫ May 20, 2018 16:05
'https://www.freebasic.net/forum/viewtopic.php?f=7&p=247578&sid=f1f8d87f561e0314a8c80b12b12a478c#p247578


/'
  Define a composite type, with all it's members public. This will
  represent the 'data' that our app will process.
  複合型を定義します。複合型の全メンバーを公開します。
  これは、アプリが処理する 'データ' を表します。
'/
Type Record
   Public:
      Declare Constructor()
      Declare Constructor( _
         ByRef As Const String, ByRef As Const String, ByVal As Integer )
      
      Declare Destructor()
      
      As String      Name
      As String      address
      As Integer   age
End Type

Constructor Record()
  Name = "Unknown"
  address = "Unknown"
  age = 0
End Constructor

Constructor Record( _
   ByRef pName As Const String, ByRef pAddress As Const String, ByVal pAge As Integer )

   Name = pName
   address = pAddress
   age = pAge
End Constructor

Destructor Record()

End Destructor

'' Sort an array of Records by age
'' レコードの配列を年齢順にソートする
Sub sortArray( ByVal startIndex As Integer, ByVal endIndex As Integer, array() As Record Ptr )
   Dim As Integer firstHalf, secondHalf
   Dim As Integer pivot
   
   firstHalf = startIndex
   secondHalf = endIndex
   
   '' Use the median value as pivot
   '' 中央値をピボットとして使用する
   pivot = array( ( firstHalf + secondHalf ) \ 2 )->age 'Sort an array of Records by age

  Do
    '' Find > pivot
    Do While( array( firstHalf )->age < pivot )         'Sort an array of Records by age
      firstHalf = firstHalf + 1
    Loop
      
      '' Find < pivot
      Do While( array( secondHalf )->age > pivot )      'Sort an array of Records by age
         secondHalf = secondHalf - 1
      Loop
      
      '' Swap if needed
      If( firstHalf <= secondHalf ) Then
         Swap array( firstHalf ), array( secondHalf )
         
         firstHalf = firstHalf + 1
         secondHalf = secondHalf - 1
      End If
   Loop Until( firstHalf > secondHalf )
 
  '' Repeate sort until each half is sorted
  '' 各半分がソートされるまでソートを繰り返す
   If( secondHalf > startIndex ) Then
      sortArray( startIndex, secondHalf, array() )
  End If
   
   If( firstHalf < endIndex ) Then
      sortArray( firstHalf, endIndex, array() )
   End If
End Sub

/'
  Main code
  主コード
'/
Dim As Record Ptr records( 0 To 2 )

records( 0 ) = New Record( "Paul Doe", "1st Street", 36 )
records( 1 ) = New Record( "Jane Doe", "2st Street", 30 )
records( 2 ) = New Record( "Shaiel Doe", "Dreamland", 9 )

'' Sort the array of records
'' レコードの配列をソートする
sortArray( 0, UBound( records ), records() )

For i As Integer = 0 To UBound( records )
  ? records( i )->Name
  ? records( i )->address
  ? records( i )->age
  ?
Next

'' Cleanup
For i As Integer = 0 To UBound( records )
  Delete( records( i ) )
Next

? "何かキー入力でプログラムを終了します。"
Sleep()