📘[Algorithms] 정렬 알고리즘 의사코드

선택정렬(Selection Sort)

의사코드

Step 1: Pass = 0

Step 2: SmallestItemPosition = Pass

Step 3: Comparison = Pass + 1

Step 4: if Item[Comparison] < Item[SmallestPosition] 
            then SmallestPosition = Comparison

Step 5: Comparison = Comparison + 1

Step 6: If Comparison < Count
            then goto Step 4

Step 7: Temp = Item[Pass]
            Item[Pass] = Item[SmallestItemPosition]
        Item[SmallestItemPosition] = Temp

Step 8: Pass = Pass + 1

Step 9: If Pass < Count
            then goto Step 2

버블정렬(Bubble Sort)

의사코드

BubbleSort(Array arr of N element)
  for i=1 to N-1
      for j=1 to N-i
          if arr[j] > arr[i+1]
              then interchange(arr[j], arr[j+1])
          end if
      end for
  endfor

interchange(n, m)
    temp = n
    n = m
    m = temp

합병정렬

의사코드

Merge(A, p, q, r)
    $n_1$ = q - p + 1
    $n_2$ = r - q
    let L[1...$n_1$+1] and R[1..$n_2$+1] be new arrays

    for i = 1 to $n_1$
        L[i] = A[p + i -1]
    for j = 1 to $n_2$
        R[j] = A[q + j]

    L[$n_1$ + 1] = $\infty$
    R[$n_2$ + 1] = $\infty$

    i = 1
    j = 1

    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i += 1
        else A[k] = R[j]
            j += 1

Merge_Sort(A, p, r)
    if p < r
        q = {(p + r) / 2}           // 이 값을 넘지 않는 최댓값 -> divide
        Merge_Sort(A, p, q)         // conquer
        Merge_Sort(A, q + 1, r)     // conquer
        Merge(A, p, q, r)           // combine
        

퀵정렬 (Quick Sort)

Quick_Sort(A, p, r)
    if p < r
        q = Partition(A, p, r)
        Quick_Sort(A, p, q - 1)
        Quick_Sort(A, q + 1, r)

Initial call is Quick_Sort(A, 1, n)

Partition(A, p, r)
    x = A[r]
    i = p - 1

    for j = p to r - 1
        if A[j] <= x
            i += 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1

참고자료

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=deardiary11&logNo=220571744021
교재 : Introduction to Algorithms