VB.NET 정렬 알고리즘과 예제 코드

VB.NET에서 정렬 알고리즘을 구현하는 방법은 매우 중요한 주제입니다. 이 글에서는 VB.NET에서 사용 가능한 몇 가지 대표적인 정렬 알고리즘에 대해 살펴보고, 각 알고리즘의 구현 방법과 성능에 대해서도 자세히 다룰 것입니다.

1. 버블 정렬(Bubble Sort)

버블 정렬은 가장 간단한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 인접한 두 개의 요소를 비교하고, 만약 두 개의 요소가 잘못된 순서로 되어 있으면 위치를 교환하는 과정을 반복합니다. 이 과정을 모든 요소에 대해 반복하면 정렬이 완료됩니다. 하지만 버블 정렬은 시간 복잡도가 O(n^2)이라는 단점이 있어서 속도가 느리다는 단점이 있습니다.

Sub BubbleSort(ByVal arr() As Integer)
    Dim i, j, temp As Integer
    For i = 0 To arr.Length - 2
        For j = 0 To arr.Length - 2 - i
            If arr(j) > arr(j + 1) Then
                temp = arr(j + 1)
                arr(j + 1) = arr(j)
                arr(j) = temp
            End If
        Next
    Next
End Sub

2. 선택 정렬(Selection Sort)

선택 정렬은 가장 작은 값을 찾아서 맨 앞에 놓고, 그 다음으로 작은 값을 찾아서 두 번째 자리에 놓는 방식으로 정렬하는 알고리즘입니다. 선택 정렬도 버블 정렬과 마찬가지로 시간 복잡도가 O(n^2)입니다.

Sub SelectionSort(ByVal arr() As Integer)
    Dim i, j, min, temp As Integer
    For i = 0 To arr.Length - 2
        min = i
        For j = i + 1 To arr.Length - 1
            If arr(j) < arr(min) Then
                min = j
            End If
        Next
        If min <> i Then
            temp = arr(i)
            arr(i) = arr(min)
            arr(min) = temp
        End If
    Next
End Sub

3. 삽입 정렬(Insertion Sort)

삽입 정렬은 각 요소를 적절한 위치에 삽입하면서 정렬하는 알고리즘입니다. 삽입 정렬은 버블 정렬과 선택 정렬보다는 약간 더 빠르며, 최선의 경우 시간 복잡도는 O(n)이지만, 평균적으로는 O(n^2)입니다.

Sub InsertionSort(ByVal arr() As Integer)
    Dim i, j, key As Integer
    For i = 1 To arr.Length - 1
        key = arr(i)
        j = i - 1
        While j >= 0 AndAlso arr(j) > key
            arr(j + 1) = arr(j)
            j -= 1
        End While
        arr(j + 1) = key
    Next
End Sub

4. 퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복(Divide and Conquer) 방식을 사용하여 정렬하는 알고리즘 중 하나입니다. 배열을 분할하여 각 부분 배열을 정렬한 다음, 이를 병합하여 전체 배열을 정렬합니다. 퀵 정렬은 평균적으로는 O(nlogn)의 시간 복잡도를 가지며, 최악의 경우 O(n^2)의 시간 복잡도를 가집니다.

Sub QuickSort(ByVal arr() As Integer, ByVal low As Integer, ByVal high As Integer)
    If low < high Then
        Dim pivot As Integer = Partition(arr, low, high)
        QuickSort(arr, low, pivot - 1)
        QuickSort(arr, pivot + 1, high)
    End If
End Sub

Function Partition(ByVal arr() As Integer, ByVal low As Integer, ByVal high As Integer) As Integer
    Dim pivot As Integer = arr(high)
    Dim i As Integer = low - 1
    Dim j As Integer
    For j = low To high - 1
        If arr(j) <= pivot Then
            i += 1
            Swap(arr(i), arr(j))
        End If
    Next
    Swap(arr(i + 1), arr(high))
    Return i + 1
End Function

Sub Swap(ByRef a As Integer, ByRef b As Integer)
    Dim temp As Integer = a
    a = b
    b = temp
End Sub

5. 병합 정렬(Merge Sort)

병합 정렬은 분할 정복(Divide and Conquer) 방식을 사용하여 정렬하는 알고리즘 중 하나입니다. 배열을 반으로 나누어 각 부분 배열을 정렬한 다음, 이를 병합하여 전체 배열을 정렬합니다. 병합 정렬은 항상 O(nlogn)의 시간 복잡도를 가집니다.

Sub MergeSort(ByVal arr() As Integer, ByVal left As Integer, ByVal right As Integer)
    If left < right Then
        Dim mid As Integer = (left + right) \ 2
        MergeSort(arr, left, mid)
        MergeSort(arr, mid + 1, right)
        Merge(arr, left, mid, right)
    End If
End Sub

Sub Merge(ByVal arr() As Integer, ByVal left As Integer, ByVal mid As Integer, ByVal right As Integer)
    Dim n1 As Integer = mid - left + 1
    Dim n2 As Integer = right - mid
    Dim L(n1 - 1) As Integer
    Dim R(n2 - 1) As Integer
    Dim i, j, k As Integer
    For i = 0 To n1 - 1
        L(i) = arr(left + i)
    Next
    For j = 0 To n2 - 1
        R(j) = arr(mid + 1 + j)
    Next
    i = 0
    j = 0
    k = left
    While i < n1 AndAlso j < n2
        If L(i) <= R(j) Then
            arr(k) = L(i)
            i += 1
        Else
            arr(k) = R(j)
            j += 1
        End If
        k += 1
    End While
    While i < n1
        arr(k) = L(i)
        i += 1
        k += 1
    End While
    While j < n2
        arr(k) = R(j)
        j += 1
        k += 1
    End While
End Sub

6. 힙 정렬(Heap Sort)

힙 정렬은 힙(Heap) 자료구조를 이용하여 정렬하는 알고리즘 중 하나입니다. 먼저 배열을 힙으로 변환한 후, 가장 큰 값을 추출하여 배열의 뒤쪽부터 채워나가는 방식으로 정렬합니다. 힙 정렬은 항상 O(nlogn)의 시간 복잡도를 가집니다.

Sub HeapSort(ByVal arr() As Integer)
    Dim n As Integer = arr.Length
    For i As Integer = n \ 2 - 1 To 0 Step -1
        Heapify(arr, n, i)
    Next
    For i As Integer = n - 1 To 0 Step -1
        Swap(arr(0), arr(i))
        Heapify(arr, i, 0)
    Next
End Sub

Sub Heapify(ByVal arr() As Integer, ByVal n As Integer, ByVal i As Integer)
    Dim largest As Integer = i
    Dim left As Integer = 2 * i + 1
    Dim right As Integer = 2 * i + 2
    If left < n AndAlso arr(left) > arr(largest) Then
        largest = left
    End If
    If right < n AndAlso arr(right) > arr(largest) Then
        largest = right
    End If
    If largest <> i Then
        Swap(arr(i), arr(largest))
        Heapify(arr, n, largest)
    End If
End Sub

7. 계수 정렬(Counting Sort)

계수 정렬은 정수 배열에 대해서만 정렬할 수 있는 특수한 정렬 알고리즘입니다. 배열의 값이 0부터 최대값까지의 카운트 배열을 생성한 후, 각 숫자의 등장 횟수를 세어 카운트 배열에 누적시킵니다. 마지막으로 카운트 배열을 순회하며 각 숫자가 등장한 횟수만큼 배열에 다시 채워주는 방식으로 정렬합니다. 계수 정렬은 O(n+k)의 시간 복잡도를 가지며, k는 정수 배열의 최대값을 의미합니다.

Sub CountingSort(ByVal arr() As Integer)
    Dim n As Integer = arr.Length
    Dim maxVal As Integer = arr.Max()
    Dim count(maxVal) As Integer
    Dim output(n - 1) As Integer
    For i As Integer = 0 To n - 1
        count(arr(i)) += 1
    Next
    For i As Integer = 1 To maxVal
        count(i) += count(i - 1)
    Next
    For i As Integer = n - 1 To 0 Step -1
        output(count(arr(i)) - 1) = arr(i)
        count(arr(i)) -= 1
    Next
    For i As Integer = 0 To n - 1
        arr(i) = output(i)
    Next
End Sub

이제 위에서 구현한 모든 정렬 알고리즘을 사용하여, 정수 배열을 오름차순으로 정렬하는 예시 코드를 작성해보겠습니다.

Sub Main()
    Dim arr() As Integer = {10, 2, 6, 7, 1, 3, 8, 5, 9, 4}
    Dim n As Integer = arr.Length
    ' 선택 정렬
    SelectionSort(arr)
    ' 버블 정렬
    BubbleSort(arr)
    ' 삽입 정렬
    InsertionSort(arr)
    ' 퀵 정렬
    QuickSort(arr, 0, n - 1)
    ' 병합 정렬
    MergeSort(arr, 0, n - 1)
    Console.WriteLine("정렬 결과: ")
    For Each num As Integer In arr
        Console.Write(num & " ")
    Next
End Sub

위 예시 코드를 실행하면, 다음과 같은 결과가 출력됩니다.

정렬 결과: 1 2 3 4 5 6 7 8 9 10

마치며...

정렬 알고리즘을 포함한 모든 알고리즘은 언어의 종류에 구애받지 않는 개념적인 부분이고, 이번 글에서는 이런 정렬 알고리즘을 VB.NET을 이용해서 구현한 예제들을 수록했습니다. 정렬은 프로그래밍을 하다 보면 정말 빈번하게 많이 사용되는 기능이니 꼭 숙지하시기 바라며, 아래 관련글에 있는 List의 정렬은 이들 정렬 알고리즘이 List 클래스 내부에 포함되어 손쉽게 정렬을 할 수 있으니 참고하시기 바랍니다.

 

관련글 : 2022.12.05 - [VB.NET] - VB.NET OrderBy, ThenBy를 이용한 리스트 정렬 (역순정렬 포함)

VB.NET OrderBy, ThenBy를 이용한 리스트 정렬 (역순정렬 포함)