↓Skip to main content

[Algorithm] 정렬, 탐색 알고리즘

Table of Contents



정렬 알고리즘 #

  • 정렬 알고리즘과 시간 복잡도
정렬 알고리즘 Best Avg Worst
삽입 정렬 $n$ $n^2$ $n^2$
선택 정렬 $n^2$ $n^2$ $n^2$
버블 정렬 $n^2$ $n^2$ $n^2$
셸 정렬 $n$ $n^{1.5}$ $n^2$
퀵 정렬 $n \log n$ $n \log n$ $n^2$
힙 정렬 $n \log n$ $n \log n$ $n \log n$
병합 정렬 $n \log n$ $n \log n$ $n \log n$
계수 정렬 $n + k$ $n + k$ $n + k$
기수 정렬 $dn$ $dn$ $dn$



  • (오름 차순 정렬 기준)

삽입 정렬(Insertion sort) #

  • 정렬되지 않은 첫 번째 데이터를 선정한다.
  • 정렬된 부분의 제일 오른쪽 데이터부터 선정한 데이터와 비교해서, 선정한 데이터가 더 작으면 교환을 반복해 나간다.
  • 시간 복잡도
    • 이미 정렬된 상태라면?
    • 한번씩 밖에 비교를 안하므로 최선의 경우 $n$가 된다.
void InsertionSort()
{
    // target의 위치를 확정해본다.
    for (int target = 1; target < arrSize; target++) // target = 1 ~ 마지막 인덱스
    {
        // 어떻게? 앞으로 가면서 target이 더 작으면 swap해서!
        for (int goFront = target; goFront >= 1; goFront--)  // goFront = target ~ 1
        {
            // goFront와 goFront - 1을 비교한다.
            if (arr[goFront] < arr[goFront - 1])
                swap(arr[goFront], arr[goFront - 1]);
            else
                break;
        }
    }
}

선택 정렬(Selection sort) #

  • 정렬되지 않은 데이터 중에서 가장 작은 것을 선택한다.
  • 정렬되지 않은 맨 앞의 데이터와 교환한다.
void SelectionSort()
{
    // targetPos 위치에 들어갈 숫자를 확정해본다.
    for (int targetPos = 0; targetPos < arrSize; targetPos++)
    {
        int min = targetPos;

        // 어떻게? 뒤로 가면서 제일 작은걸 선택해서!
        for (int goBack = targetPos + 1; goBack < arrSize; goBack++)
            if (arr[goBack] < arr[min])
                min = goBack;

        swap(arr[targetPos], arr[min]);
    }
}

버블 정렬(Bubble sort) #

  • 인접한 두 원소를 비교해서 큰 원소를 뒤로 민다.
void BubbleSort()
{
    for (int orderedSize = 1; orderedSize < arrSize; orderedSize++) // orderedSize : 1 ~ 마지막인덱스
        for (int i = 0; i < arrSize - orderedSize; i++)             // i : 0부터 (맨 뒤에 정렬된 것들 빼고) 비교해나간다.
            if (arr[i + 1] < arr[i])
                swap(arr[i + 1], arr[i]);
}

셸 정렬(Shell sort) #

  • 간격을 전체 크기의 절반부터 점차 2로 나눠서 줄여가면서, 간격만큼 떨어진 데이터들의 부분리스트를 만들고, 삽입정렬을 한다.
void InsertionSort(int start, int gap)
{
    // 숫자들이 start인덱스에서 시작해서 gap만큼 떨어진 상태임을 고려한다.
    for (int target = start + gap; target < arrSize; target += gap)
    {
        for (int goFront = target; goFront >= start + gap; goFront -= gap)
        {
            if (arr[goFront] < arr[goFront - 1])
                swap(arr[goFront], arr[goFront - 1]);
            else
                break;
        }
    }
}

void ShellSort()
{
    for (int gap = arrSize / 2; gap > 0; gap /= 2) // gap을 반씩 줄여가며 반복한다.
    {
        if (gap % 2 == 0) gap += 1;

        for (int start = 0; start < arrSize / gap; start++) // 해당 gap으로 만들어진 부분 배열의 개수만큼 반복
            InsertionSort(start, gap);
    }
}

퀵 정렬(Quick sort) #

  • I 큰 값 찾기 >> … << J 작은 값 찾기 (내림차순이면 방향만 바뀜)
  • 각각 값을 찾으면 I와 J를 교환하고,
  • I와 J가 교차하면 J와 피벗을 교환하고,
  • 그룹을 나눈 후 반복한다.
  • 시간 복잡도
    • 요소의 개수 만큼 반복 $n$ $*$ 절반씩 나누어지므로 $\log n$
    • 하지만, 피벗이 한쪽 끝에 있고 + 모두 정렬(혹은 역으로) 되어 있다면?
    • 계속 $1 : n-1$로 끝에서 나누어지므로, 총$n$번 나누는 게 된다.
    • 따라서 최악의 경우 $n^2$가 된다.
void QuickSort(int start, int finish)
{
    if (finish <= start) return;

    int pivot = start;
    int left = pivot + 1;
    int right = finish;

    // 대략적으로 요소의 개수 n 만큼 반복하면서 검사하게 된다.
    while(left <= right) // 겹치면, 나간다
    {
        // left -> : 큰 값을 찾아서.
        // 마지막 이하이고, 이번 값이 피벗보다 작을 때 반복한다.
        // (점점 커지면 배열을 넘어선다... 하지만 그 말은 겹쳤다는 뜻이며, 겹쳤을 때 이 값을 쓰진 않으므로 상관없다)
        while (left <= finish && arr[left] < arr[pivot])
            left++;

        // <- right : 작은 값을 찾아서.
        // 첫번째 이상이고, 이번 값이 피벗보다 클 때 반복한다.
        // (점점 작아지면 피벗 이후 두 번째 칸까지 간다)
        while (start <= right && arr[pivot] < arr[right])
            right--;

        // 겹치면, 피벗과 작은 값을(right) 교체한다, 그리고 나가게 된다
        if (right < left)
            swap(arr[pivot], arr[right]);
        // 겹친게 아니면, 둘이 교체한다
        else
            swap(arr[left], arr[right]);
    }

    // 겹칠 때까지 교환한 결과, 겹친 부분을 중심으로 왼쪽은 작음 오른쪽은 큼으로 나뉘게 된다
    // 겹쳤을 때는 작은 것과 교환했으므로 작은 것이 중심이 된다.
    // 계속해서 절반씩 나누게 된다면 그 높이는 log n일 것이다.
    QuickSort(start,     right - 1);
    QuickSort(right + 1, finish);
}

힙 정렬(Heap sort) #

  • 완전 이진 트리의 일종인 힙을 사용한다.
  • 힙을 만들고, 루트를 꺼낸 후 다시 힙을 만들고($\log n$)를 반복($n$)한다.
// 루트를 제일 큰 값으로 만드는 최대 힙이다.
// log n 만큼의 (트리 높이 만큼의) 반복 횟수가 예상된다.
void MakeHeap(int start, int finish)
{
    // 루트에서 시작해서
    int rootToMove = arr[start];
    int parent;
    int maxChild = start;

    for (parent = start; parent < (finish + 1) / 2; parent = maxChild)
    {
        int leftChild  = (parent * 2) + 1;
        int rightChild = (parent * 2) + 2;

        // 왼쪽과 오른쪽 자식 중에 루트보다 큰 값이 있으면
        maxChild = (rightChild <= finish && arr[leftChild] < arr[rightChild]) ? rightChild : leftChild;

        if (arr[maxChild] <= rootToMove)
            break;

        // 그 큰 자식이 부모의 자리를 꿰찬다.
        arr[parent] = arr[maxChild];
        
        // 그 자식을 루트로 보고 다시 반복한다.
    }

    // 더이상 큰 자식이 없을 때, 그 자리가 적절한 자리이다.
    arr[parent] = rootToMove;
}

void HeapSort()
{
    // 제일 작은 이진 트리의 루트에서 부터 한 부모씩 올라가면서 전체를 힙으로 만든다.
    int smallestRoot = arrSize / 2 - 1;
    for (int i = smallestRoot; i >= 0; i--)
        MakeHeap(i, arrSize - 1);

    // 한 요소씩 트리에서 빼면서 반복하므로 n 만큼 반복된다.
    for (int orderedSize = 1; orderedSize < arrSize; orderedSize++)
    {
        // 이진 트리의 루트(0)를 맨 뒷 요소(arrSize - 1)와 바꿔서 맨 뒤는 제일 큰 루트가 차곡차곡 저장되게 한다.
        swap(arr[0], arr[arrSize - orderedSize]);
        
        // 이제 맨 끝은 큰게 저장되었으므로 루트부터 그 전(size - 2)노드까지 다시 힙을 만든다.
        MakeHeap(0, arrSize - orderedSize - 1);
    }
}

병합 정렬(Merge sort) #

  • 원소가 1일 때까지 나눠서 1이면 리턴하고,
  • 그 이상일 경우 정렬하고 합치기를 반복한다.
void Merge(int start, int finish)
{
    int size = (finish - start) + 1;
    int mid  = (start + finish) / 2;

    int idx = 0;
    int left = start;
    int right = mid + 1;

    // 총 요소의 개수만큼 n번 반복하면서 비교가 된다.

    // 인덱스를 더해가면서 비교한다.
    // left는 start에서 mid까지이다.
    // right는 mid+1에서 finish까지이다.
    while (left <= mid && right <= finish)
    {
        if (arr[left] <= arr[right])     sorted[idx++] = arr[left++];
        else if (arr[right] < arr[left]) sorted[idx++] = arr[right++];
    }

    // 남은 배열은 모두 순서대로 추가해준다.
    // left가 mid를 넘어섰다는 것은, right가 남았다는 것이다.
    if (left > mid)
    {
        for (int i = right; i <= finish; i++)
            sorted[idx++] = arr[i];
    }
    // right가 finish를 넘어섰다는 것은, left가 남았다는 것이다.
    else if (right > finish)
    {
        for (int i = left; i <= mid; i++)
            sorted[idx++] = arr[i];
    }

    // 원래 배열로 옮긴다.
    for (int i = 0; i < size; i++)
        arr[start + i] = sorted[i];
}

void MergeSort(int start, int finish)
{
    int size = (finish - start) + 1;
    if (size <= 1) return;

    int mid = (start + finish) / 2;

    // 계속 절반씩 나누므로 총 log n번 반복된다.
    MergeSort(start,   mid);
    MergeSort(mid + 1, finish);
    
    // 합친다.
    Merge(start, finish);
}

계수 정렬(Counting sort) #

  • 최대값만한 크기의 리스트를 만들고 나온 횟수를 센다. 그리고 횟수만큼 출력한다.
  • 조건
    • 음수가 아닌 정수만 가능하다.
    • 만약 정수의 최댓값 $k$가 너무 크면 비효율적이다.
    • 추가적인 메모리가 필요하다.
  • 시간 복잡도
    • 원소 개수만큼 넣고 $n$ $+$ 정수의 최댓값만큼 꺼내기 $k$
void CountingSort()
{
    // 최대값 찾기
    int max = 0;
    for (int i = 0; i < arrSize; i++)
        if (arr[i] > max)
            max = arr[i];

    // 최대값만한 크기의 리스트 만들기
    vector<int> counter(max);

    // 중복 횟수 입력하기 n번
    for (int i = 0; i < arrSize; i++)
        counter[arr[i]]++;
    
    // 순서대로 출력하기 k번
    for (int i = 0; i < max; i++)
        for (int j = 0; j < counter[i]; j++)
            cout << i << ' ';

    cout << '\n';
}

기수 정렬(Radix sort) #

  • 낮은 1의 자리수부터 버킷에 넣었다가 꺼내기를 반복한다.
  • 조건
    • 음수가 아닌 정수만 가능하다.
    • 추가적인 메모리가 필요하다.
  • 시간 복잡도
    • 최대 자릿수만큼 반복 계산하기 $d$ $*$ 원소 개수만큼 $n$ 탐색하기
void RadixSort()
{
    queue<int> q[10];

    // 최대값 찾기
    int max = 0;
    for (int i = 0; i < arrSize; i++)
        if (max < arr[i])
            max = arr[i];

    // 최대자릿수인 Radix를 찾는다.
    int radix = 1;
    while (true)
    {
        if (radix >= max) break;
        radix = radix * 10;
    }

    // 1의 자리부터 10씩 곱하면서 최대자릿수 Radix까지 반복한다. d번
    for (int r = 1; r < radix; r *= 10)
    {
        // 모든 배열을 다 탐색하면서. n번
        for (int i = 0; i < arrSize; i++)
        {
            int k;
            if (arr[i] < r) k = 0;                  // 현재 배열의 값 < 현재 자릿수 i 이면, k = 0
            else            k = (arr[i] / r) % 10;  // 그게 아니라면, k = 현재 자릿수에 해당하는 값

            // 큐에 현재 배열의 값을 k에 따라 순차적으로 저장한다.
            q[k].push(arr[i]);
        }

        // 0부터 9까지 큐에 저장된 값들을 순차적으로 빼내서, 배열에 다시 저장한다.
        int idx = 0;
        for (int i = 0; i < 10; i++)
        {
            while (q[i].empty() == 0)
            {
                arr[idx] = q[i].front();
                q[i].pop();
                idx++;
            }
        }
    }
}



탐색 알고리즘 #

  • 정렬된 배열에서, 원소 $x$를 찾고자 할 때 사용한다.
  • $x$가 중간의 원소보다 작다면 왼쪽을, 크다면 오른쪽을 재탐색한다.
void BinarySearch_Loop()
{
    int start = 0;
    int finish = arrSize - 1;
    int mid;

    while(start <= finish)
    {
        mid = (start + finish) / 2;

        if (arr[mid] == target)
        {
            cout << "Found it in index : " << mid << '\n';
            return;
        }
        else if (arr[mid] < target) start = mid + 1;
        else                        finish = mid - 1;
    }

    cout << "Couldn't find it." << '\n';
}

void BinarySearch_Recursion(int start, int finish)
{
    if (finish < start) return;

    int mid = (start + finish) / 2;

    if (arr[mid] == target)
    {
        cout << "Found it in index : " << mid << '\n';
        return;
    }
    else if (arr[mid] < target)
    {
        BinarySearch_Recursion(mid + 1, finish);
    }
    else
    {
        BinarySearch_Recursion(start, mid - 1);
    }
}



이진 탐색 트리(Binary search tree) #

  • 다음과 같은 특징을 갖는 트리 자료구조이다.
    • 자식이 최대 2개 + 왼쪽 모든 자식 < 부모 < 오른쪽 모든 자식

코드 보기



References #



↑