Implementation (Part 1)
Coddyの「クイックソート - DSAシリーズ」コースのレッスン 5/9。
クイックソートを、その中心となる操作から順に構築していきます。
チャレンジ
簡単クイックソートの核心はパーティション（分割）ステップです。まずはそれを作成しましょう。
arrの最後の要素をピボットとして使用し、以下の内容を含む新しい配列を返す、partitionという名前の関数を記述してください：
- ピボットより小さいすべての要素（元の順序のまま）、
- 次にピボット、
- その後に残りのすべての要素、つまりピボット以上のすべての要素（元の順序のまま）。
例えば、[3, 7, 1, 8, 5] は [3, 1, 5, 7, 8] になります（ピボットは 5）。
自分で試してみよう
#include <stdlib.h>
int* partition(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