All Honey Tip

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

수정 일:

발행 일:

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

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

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





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

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






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

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







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

평균 O(NlogN) 입니다.






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

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







// 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





퀵 소트 외에도 추가로 공부하실 수 있는 책 3권 추천해 드립니다. 🙂

이것이 자료구조+알고리즘이다 with C 언어:문제 해결 능력을 키워주는 자료구조+알고리즘 입문서, 한빛미디어 C언어로 쉽게 풀어 쓴 자료구조, 생능출판 Do it! 자료구조와 함께 배우는 알고리즘 입문: 파이썬 편:내 손으로 직접 코딩하며 확인한다, 이지스퍼블리싱






마치며

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

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

image 27


코멘트

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다