Quicksort
কুইকসর্ট
Pivot বেছে array-কে ছোট-বড় দুই ভাগে partition করে প্রতিটা ভাগ recursively sort করা divide-and-conquer — average O(n log n), in-place, কিন্তু unstable।
also: quick sort, partition-exchange sort
Partition-ই সব কাজ করে — pivot-এর সঠিক জায়গা ঠিক করে, ছোটগুলো বামে বড়গুলো ডানে ফেলে:
def partition(a, lo, hi):
p = a[hi]; i = lo
for j in range(lo, hi):
if a[j] < p:
a[i], a[j] = a[j], a[i]; i += 1
a[i], a[hi] = a[hi], a[i]
return iAverage O(n log n); sorted input-এ প্রথম/শেষ element pivot হলে O(n²)। Randomized pivot বা median-of-three দিলে ওই দুর্ভাগ্য বাস্তবে অসম্ভব।
Extra array লাগে না, swap local — cache-friendly, তাই practical দৌড়ে
প্রায়ই দ্রুততম comparison sort। C++ std::sort-এর introsort এটা
দিয়েই শুরু করে।