Quick Sort, Selection Sort and Bubble Sort algorithm in VB6

Here we have an application that measures execution times for the three sorting algorithms: Quick Sort, Selection Sort and Bubble Sort.  A visual interface shows what these algorithms do in real time. The implementation is made in algorithm in Visual Basic 6.0 and the source code is shown below:

Download from me

The quicksort algorithm was developed in 1959 by Tony Hoare while in the Soviet Union, as a visiting student at Moscow State University. At that time, Hoare worked in a project on machine translation for the National Physical Laboratory. As a part of the translation process, he needed to sort the words of Russian sentences prior to looking them up in a Russian-English dictionary that was already sorted in alphabetic order on magnetic tape. After recognizing that his first idea, insertion sort, would be slow, he quickly came up with a new idea that was Quicksort. He wrote a program in Mercury Autocode for the partition but couldn't write the program to account for the list of unsorted segments. On return to England, he was asked to write code for Shellsort as part of his new job. Hoare mentioned to his boss that he knew of a faster algorithm and his boss bet sixpence that he didn't. His boss ultimately accepted that he had lost the bet. Later, Hoare learned about ALGOL and its ability to do recursion that enabled him to publish the code in Communications of the Association for Computing Machinery, the premier computer science journal of the time.

Quicksort gained widespread adoption, appearing, for example, in Unix as the default library sort subroutine. Hence, it lent its name to the C standard library subroutine qsort and in the reference implementation of Java.

Robert Sedgewick's Ph.D. thesis in 1975 is considered a milestone in the study of Quicksort where he resolved many open problems related to the analysis of various pivot selection schemes including Samplesort, adaptive partitioning by Van Emden as well as derivation of expected number of comparisons and swaps. Bentley and McIlroy incorporated various improvements for use in programming libraries, including a technique to deal with equal elements and a pivot scheme known as pseudomedian of nine, where a sample of nine elements is divided into groups of three and then the median of the three medians from three groups is chosen. Jon Bentley described another simpler and compact partitioning scheme in his book Programming Pearls that he attributed to Nico Lomuto. Later Bentley wrote that he used Hoare's version for years but never really understood it but Lomuto's version was simple enough to prove correct. Bentley described Quicksort as the "most beautiful code I had ever written" in the same essay. Lomuto's partition scheme was also popularized by the textbook Introduction to Algorithms although it is inferior to Hoare's scheme because it does three times more swaps on average and degrades to O(n2) runtime when all elements are equal.

In 2009, Vladimir Yaroslavskiy proposed the new dual pivot Quicksort implementation. In the Java core library mailing lists, he initiated a discussion claiming his new algorithm to be superior to the runtime library’s sorting method, which was at that time based on the widely used and carefully tuned variant of classic Quicksort by Bentley and McIlroy. Yaroslavskiy’s Quicksort has been chosen as the new default sorting algorithm in Oracle’s Java 7 runtime library after extensive empirical performance tests.

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort. It can be practical if the input is usually in sorted order but may occasionally have some out-of-order elements nearly in position.

Implementation:

Public Declare Sub Sleep Lib "kernel32.dll" (ByVal dwMilliseconds As Long)

Public Sub QuickSort(vArray As Variant, L As Long, R As Long)
  '             Array            , LBound()     , UBound()
  Dim i As Long
  Dim j As Long
  Dim X
  Dim Y

  i = L
  j = R
  X = vArray((L + R) / 2)

  Do While (i <= j)
    DoEvents
    Do While (vArray(i) < X And i < R)
      i = i + 1
    Loop

    Do While (X < vArray(j) And j > L)
      j = j - 1
    Loop

    If (i <= j) Then
      Y = vArray(i)
      vArray(i) = vArray(j)
      vArray(j) = Y
      i = i + 1
      j = j - 1
    End If
  Loop

  If (L < j) Then QuickSort vArray, L, j
  If (i < R) Then QuickSort vArray, i, R
End Sub

Public Sub QuickSort33(vArray As Variant, AccordingTo As Integer, Dimension2Size As Integer, L As Integer, R As Integer)
  '   name of array,   sorting according to which dimension?,   size of second dimension,   lbound(),   ubound()
  Dim a As Integer, i As Integer, j As Integer  ' counters
  Dim X, Y, z   ' temporary values

  i = L
  j = R
  X = vArray((L + R) / 2, AccordingTo)
  Do While (i <= j)
    DoEvents
    Do While (vArray(i, AccordingTo) < X And i < R)
      i = i + 1
    Loop
    Do While (X < vArray(j, AccordingTo) And j > L)
      j = j - 1
    Loop
    If (i <= j) Then
      Y = vArray(i, AccordingTo)
      vArray(i, AccordingTo) = vArray(j, AccordingTo)
      vArray(j, AccordingTo) = Y
      For a = 0 To AccordingTo - 1
        z = vArray(i, a)
        vArray(i, a) = vArray(j, a)
        vArray(j, a) = z
      Next a
      For a = AccordingTo + 1 To Dimension2Size
        z = vArray(i, a)
        vArray(i, a) = vArray(j, a)
        vArray(j, a) = z
      Next a
      i = i + 1
      j = j - 1
    End If
  Loop

  If (L < j) Then QuickSort33 vArray, AccordingTo, Dimension2Size, L, j
  If (i < R) Then QuickSort33 vArray, AccordingTo, Dimension2Size, i, R
End Sub

Public Sub SelectionSort(vArray, L As Integer, R As Integer)
'    name of array,    lbound(),    ubound()
Dim i As Integer
Dim j As Integer
Dim best_value  ' smallest value in array
Dim best_j As Integer
    ' loop from left to right
    For i = L To R - 1
        DoEvents
        ' initialize lowest value
        best_value = vArray(i)
        best_j = i  ' initialize lowest value array location
        For j = i + 1 To R
            ' find the lowest value in the array in this loop
            If vArray(j) < best_value Then
                best_value = vArray(j)
                best_j = j
            End If
        Next j
        ' put the smallest value at the from (left) of the array
        ' and put the value on the left of the array in the smallest
        ' value's previous position
        vArray(best_j) = vArray(i)
        vArray(i) = best_value
    Next i
    
End Sub

Public Sub QuickSortBars(vArray As Variant, L As Integer, R As Integer, Optional SleepTime As Long = 0)
  Dim i As Integer    ' counter
  Dim j As Integer    ' counter
  Dim BarVal1         ' temporary bar value
  Dim BarVal2         ' temporary bar value

  i = L
  j = R
  BarVal1 = vArray((L + R) / 2)

  Do While (i <= j)
    DoEvents
    If SleepTime > 0 Then
      Sleep SleepTime
    End If
    Do While (vArray(i) < BarVal1 And i < R)
      i = i + 1
    Loop

    Do While (BarVal1 < vArray(j) And j > L)
      j = j - 1
    Loop

    If (i <= j) Then
      BarVal2 = vArray(i)
      vArray(i) = vArray(j)
      vArray(j) = BarVal2
      frmMain.Bar(i).Value = vArray(i)
      frmMain.Bar(j).Value = vArray(j)
      i = i + 1
      j = j - 1
    End If
  Loop

  If (L < j) Then QuickSortBars vArray, L, j, SleepTime
  If (i < R) Then QuickSortBars vArray, i, R, SleepTime
End Sub

Public Sub SelectionSortBars(vArray, L As Integer, R As Integer, Optional SleepTime As Long = 0)
  '    name of array,    lbound(),    ubound()
  Dim i As Integer    ' counter
  Dim j As Integer    ' counter
  Dim best_value  ' smallest value in array
  Dim best_j As Integer

  ' loop from left to right
  For i = L To R - 1
    DoEvents
    If SleepTime > 0 Then
      Sleep SleepTime
    End If
    ' initialize lowest value
    best_value = vArray(i)
    best_j = i  ' initialize lowest value array location
    For j = i + 1 To R
      ' find the lowest value in the array in this loop
      If vArray(j) < best_value Then
        best_value = vArray(j)
        best_j = j
      End If
    Next j
    ' put the smallest value at the from (left) of the array
    ' and put the value on the left of the array in the smallest
    ' value's previous position
    vArray(best_j) = vArray(i)
    vArray(i) = best_value
    frmMain.Bar(best_j) = vArray(best_j)
    frmMain.Bar(i) = vArray(i)
  Next i
End Sub

Sources:

https://en.wikipedia.org/wiki/Bubble_sort

https://en.wikipedia.org/wiki/Selection_sort

https://en.wikipedia.org/wiki/Quicksort