[기술 면접] 9. 퀵소트(Quick Sort)에 대해 설명해주세요

저번 시간에 이어, 이번엔 퀵소트(Quick Sort)에 대해 알아보겠습니다. 퀵소트는 정렬 알고리즘 중 하나로, 면접 빈출도가 높은 내용은 아니지만, 등장한 이력이 있긴 해서 준비해보았습니다.

Table of Contents

Q: 퀵소트(Quick Sort)에 대해 설명해주세요

퀵소트는 정렬 알고리즘 중 하나로, 피벗(Pivot)을 기준으로 부분 배열로 나누고, 각 부분 배열을 정렬한 이후 합치는 과정을 거칩니다. 어떤 피벗을 선택하느냐에 따라 성능이 달라질 수 있습니다.

Q: 정렬 과정을 설명해주세요

피벗을 선택합니다. (보통 첫 번째를 선택)
오른쪽(j)에서 왼쪽으로 가면서 피벗보다 작은 수를 탐색합니다.
왼쪽(i)에서 오른쪽으로 가면서 피벗보다 큰 수를 탐색합니다.
i와 j를 교환합니다.
2 ~ 4 과정을 반복합니다.
i > j인 경우, 즉 더 이상 위 단계를 진행할 수 없으면, 현재 피벗과 i를 교환합니다.

Q: 퀵소트의 시간복잡도는 무엇입니까?

평균 O(NlogN) 입니다.

Q: 왜 평균이라는 표현을 쓰죠?

정렬된 경우 O(N²)의 시간복잡도를 갖지만, 그 경우가 매우 미미하기 때문에 평균이라는 표현을 덧붙여 사용합니다.

Quick Sort Java code – GeeksForGeeks

// Java implementation of QuickSort
import java.io.*;
 
class GFG {
 
    // A utility function to swap two elements
    static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    // This function takes last element as pivot,
    // places the pivot element at its correct position
    // in sorted array, and places all smaller to left
    // of pivot and all greater elements to right of pivot
    static int partition(int[] arr, int low, int high)
    {
        // Choosing the pivot
        int pivot = arr[high];
 
        // Index of smaller element and indicates
        // the right position of pivot found so far
        int i = (low - 1);
 
        for (int j = low; j <= high - 1; j++) {
 
            // If current element is smaller than the pivot
            if (arr[j] < pivot) {
 
                // Increment index of smaller element
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return (i + 1);
    }
 
    // The main function that implements QuickSort
    // arr[] --> Array to be sorted,
    // low --> Starting index,
    // high --> Ending index
    static void quickSort(int[] arr, int low, int high)
    {
        if (low < high) {
 
            // pi is partitioning index, arr[p]
            // is now at right place
            int pi = partition(arr, low, high);
 
            // Separately sort elements before
            // partition and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    // To print sorted array
    public static void printArr(int[] arr)
    {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 10, 7, 8, 9, 1, 5 };
        int N = arr.length;
 
        // Function call
        quickSort(arr, 0, N - 1);
        System.out.println("Sorted array:");
        printArr(arr);
    }
}
 
// This code is contributed by Ayush Choudhary
// Improved by Ajay Virmoti

// Output
Sorted array: 
1 5 7 8 9 10

마치며

이번 시간에는 퀵소트(Quick Sort)에 대한 면접 질문들을 알아보았습니다.

다음 시간에는 트라이(Trie) 자료구조에 대한 면접 질문들을 알아보겠습니다.