Implementation (Part 2)

Coddy의 퀵 정렬 - DSA 시리즈 코스 레슨 — 9개 중 6번째.

이제 피벗, 분할, 재귀를 결합하여 전체 알고리즘을 완성합니다.

챌린지

쉬움

이제 모든 것을 종합하여 전체 알고리즘을 완성해 보세요.

정수 배열을 입력받아 이를 오름차순으로 정렬하여 반환하는 quickSort라는 이름의 함수를 작성하세요.

마지막 요소를 pivot으로 사용하고, 나머지 요소들을 작은 그룹과 큰 그룹으로 분할한 뒤, 각 그룹에 대해 재귀적으로 quickSort를 수행합니다. 그리고 이를 정렬된-작은-그룹 + pivot + 정렬된-큰-그룹 형태로 결합하세요. 요소가 0개 또는 1개인 배열은 이미 정렬된 상태이므로 그대로 반환합니다.

이전 레슨에서 배운 분할(partition) 개념을 재사용할 수 있습니다.

직접 해보기

#include <stdlib.h>

int* quickSort(int* arr, int arr_size, int* returnSize) {
    // 여기에 코드를 작성하세요
    *returnSize = arr_size;
    return arr;
}

실력 점검

이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.

퀵 정렬 - DSA 시리즈의 모든 레슨

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) 프로젝트 레슨

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2