0
1

Quick Sort Algorithm কিভাবে কাজ করে ?

asked 30 Jan '15, 10:59

Borhan%20uddin's gravatar image

Borhan uddin
214

কুইক সর্ট অ্যালগরিদম কিভাবে কাজ করে সেটা কোরম্যান-এর ইনট্রোডাকশন টু অ্যালগরিদম বইতে খুব চমৎকারভাবে ছবিসহ বোঝানো আছে।

(30 Jan '15, 11:15) Tamim Shahriar Subeen ♦♦

Quick sort algorithm টা হচ্ছে divide-and-conquer নামক একটা type follow করে । এটার মানে হচ্ছে আমরা আমাদের যে ডাটা গুলোকে সর্ট করতে চাচ্ছি সেটার একটা list আমাদের থাকে, ওই list টাকে আমরা যখন quicksort algorithm দিয়ে সর্ট করতে যাই তখন আমরা সেটাকে আবার sub-list এ ভাগ বা divide করি । আমরা আমাদের লিস্ট বা array এর প্রথম element টা দিয়ে comparison শুরু করি । sub-list বানানোর এই স্টেপগুলোকে বলে reduction steps. reduction step এর প্রথমে আমরা right থেকে left এর দিকে কম্পেয়ার করতে করতে আসি । যে নাম্বারটার সাথে আমরা কম্পেয়ার করি সেটার থেকে যখন ছোট নাম্বার বা এলিমেন্ট পাই তখন আমরা element দুইটা swap করি । আবার যখন left থেকে right এ যাই তখন আমরা compared element টার থেকে বড় element পেলে swap করি । এভাবে আমরা প্রসেসটা রিপিট করতে থাকি প্রথম element টার ফাইনাল পজিশন না পাওয়া পর্যন্ত । আমরা যখন দেখবো যে আমরা যে element টা দিয়ে শুরু করেছিলাম কম্পারিজন , সেটার ডান দিকের সংখ্যাগুলো হবে ওই element টা থেকে বড় এবং বামদিকের গুলো হবে ওই element থেকে ছোট ।

উদাহরণ দিলে ব্যাপারটা ক্লিয়ার হবে । আমাদের লিস্টটা ধরি এমনঃ 13,33,11,77,55

  1. right to left (starting from 13): এখানে ডানদিক থেকে কম্পেয়ার করে আসার সময় 11<13 , তাহলে এই দুই element এর জায়গা বদল হবে। লিস্ট তখন হবেঃ 11,33,13,77,55
  2. এখন আমরা কম্পেয়ার করবো left to right (starting from 11): 11 থেকে আমরা ডানদিকে যেতে যেতে যখন একটা element পাবো যেটা 13 থেকে বড় তখন 13 আর ওই element টার জায়গা চেঞ্জ করে দিবো। 33>13 তাই এই দুইটা swap করবে । তখন list টা হবে 11,13,33,77,55. এখন খেয়াল করলে দেখা যাবে 13 এর বামদিকে ছোট সংখ্যা আছে তার থেকে এবং ডানদিকে আছে বড় সংখ্যা । তাহলে আমরা 13 এর final position পেয়ে গেছি। তাহলে আমরা আমাদের sub-list পেয়ে গেছি । A: (11,13) B: ( 33,77,55) । এখন আমাদের প্রথম সাবলিস্ট A sorted আছে তাই এই প্রসেসটা আমাদের A list এ রিপিট করার দরকার নাই কিন্তু B তে এই প্রসেসটা রিপিট করলে আমরা sorted list পেয়ে যাবো । এভাবে অনেকগুলা নাম্বারের জন্যও একইভাবে কাজ হবে ।

(স্কামস এর Data structure বই এর 6th chapter এর quicksort এর example পড়লে তোমার কাছে ব্যাপারটা ভালভাবে ক্লিয়ার হবে। ঐখানে ১৩ টা নাম্বারে লিস্ট দিয়ে example দেয়া আছে আর solved problem এও কিছু প্রবলেম করে দেয়া আছে )

permanent link

answered 30 Jan '15, 17:40

Tamanna%20Nishat%20Rini's gravatar image

Tamanna Nishat Rini ♦♦
3.0k312

edited 31 Jan '15, 07:37

permanent link

answered 30 Jan '15, 13:21

Kaiser%20Ahmed's gravatar image

Kaiser Ahmed
3.2k522

edited 30 Jan '15, 17:35

ভাইয়া বাংলায় নাই? :(

(31 Jan '15, 08:17) Ishan
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×13

question asked: 30 Jan '15, 10:59

question was seen: 2,333 times

last updated: 31 Jan '15, 15:08