কুইক সর্ট
From Wikipedia, the free encyclopedia
কুইক সর্ট একটি সুপরিচিত সর্টিং অ্যালগোরিদম। টোনি হোর ১৯৬০ সালে এটি উদ্ভাবন করেন। এই সর্টিং অ্যালগোরিদমটি n সংখ্যক জিনিসকে সর্ট করতে বা নির্দিষ্ট ক্রমে সাজাতে গড়ে Θ(n log n) সংখ্যক তুলনা(comparisons) করে থাকে। তবে ওয়ার্স্ট কেসে অরথাত সব থেকে প্রতিকুল অবস্থায় অ্যালগোরিদমটি O(n2) সংখ্যক তুলনা করে থাকে। সাধারণভাবে, কুইক সর্ট অন্যান্য Θ(n log n) সর্টিং অ্যালগোরিদমগুলির চেয়ে উল্লেখযোগ্যপরিমাণ দ্রুততর, কারণ এর ভেতরের লুপটি বেশির ভাগ নির্মাণ-কৌশলে সুবিধাজনকভাবে বাস্তবায়ন করা যায় এবং বাস্তব জীবনে ব্যবহৃত বেশির ভাগ উপাত্তের জন্য নকশাটি এমনভাবে বেছে নেয়া যায় যাতে দ্বি-ঘাত সময় এড়ানো সম্ভবপর হয়। কুইক সর্ট একরকমের তুলনাকেন্দ্রিক সর্ট। সুবিধাজনক বাস্তবায়নে এটা আর সুস্থিত সর্ট থাকে না।