Implementation (Part 2)
Coddyの「クイックソート - DSAシリーズ」コースのレッスン 6/9。
ここで、ピボット、パーティション、再帰を組み合わせて完全なアルゴリズムにします。
チャレンジ
簡単それでは、これらすべてを組み合わせて完全なアルゴリズムを作成しましょう。
整数配列を受け取り、それを昇順でソートして返す quickSort という名前の関数を作成してください。
最後の要素をピボットとして使用し、残りの要素を小さいグループと大きいグループに分割します。それぞれのグループに対して再帰的に quickSort を実行し、それらを「ソートされた小さいグループ + ピボット + ソートされた大きいグループ」として結合します。要素数が 0 または 1 の配列はすでにソートされているため、そのまま返します。
前のレッスンで学んだ分割（パーティション）の考え方を再利用できます。
自分で試してみよう
#include <stdlib.h>
int* quickSort(int* arr, int arr_size, int* returnSize) {
// ここにコードを書いてください
*returnSize = arr_size;
return arr;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
クイックソート - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity