হালভিং কনভেনশন
যখন তালিকায় উপাদানগুলির সংখ্যা সমান হয়, তালিকা অর্ধেক করার অর্থ হল তালিকার আক্ষরিক অর্ধেক প্রথম অর্ধেক, এবং তালিকার আক্ষরিক দ্বিতীয় অর্ধেক দ্বিতীয়ার্ধ। পুরো তালিকার মধ্য (মধ্য) উপাদান, প্রথম তালিকার শেষ উপাদান। এর মানে হল মধ্যম সূচক দৈর্ঘ্য / 2 - 1, কারণ সূচক গণনা শূন্য থেকে শুরু হয়। দৈর্ঘ্য হল তালিকার উপাদানগুলির সংখ্যা। উদাহরণস্বরূপ, যদি উপাদানগুলির সংখ্যা 8 হয়, তবে তালিকার প্রথমার্ধে 4 টি উপাদান এবং তালিকার দ্বিতীয়ার্ধেও 4 টি উপাদান রয়েছে। ওটা দারুন. যেহেতু সূচক গণনা 0 থেকে শুরু হয়, মধ্যম সূচক 3 = 8/2 - 1।
ক্ষেত্রে কি হবে, যখন তালিকা বা উপ-তালিকায় উপাদান সংখ্যা বিজোড়? শুরুতে, দৈর্ঘ্য এখনও 2 দ্বারা বিভক্ত। কনভেনশন অনুসারে, এই বিভাগের প্রথমার্ধে উপাদানগুলির সংখ্যা দৈর্ঘ্য / 2 + 1/2। সূচক গণনা শূন্য থেকে শুরু হয়। মধ্যম সূচক দৈর্ঘ্য / 2 - 1/2 দ্বারা দেওয়া হয়। এটি মধ্যম মেয়াদ হিসাবে বিবেচিত হয়, প্রচলন দ্বারা। উদাহরণস্বরূপ, যদি একটি তালিকার উপাদানগুলির সংখ্যা 5 হয়, তাহলে মধ্য সূচক 2 = 5/2 - 1/2। এবং, তালিকার প্রথমার্ধে তিনটি উপাদান এবং দ্বিতীয়ার্ধে দুটি উপাদান রয়েছে। পুরো তালিকার মধ্যম উপাদান হল সূচকের তৃতীয় উপাদান, 2, যা মধ্য সূচক কারণ সূচক গণনা 0 থেকে শুরু হয়।
এভাবে বিভাজন হল পূর্ণসংখ্যা গাণিতিকের একটি উদাহরণ।
তিন মূল্যের মধ্যমা
প্রশ্ন: ক্রমের মধ্যমা কত?
C B A
সমাধান:
ক্রমানুসারে তালিকা সাজান:
A B C
মধ্যম শব্দ, বি, মধ্যমা। এটি মাত্রা যা অন্য দুটি মাত্রার মধ্যে অবস্থিত।
একটি তালিকায় মধ্যমা খোঁজা সেই ধরনের নয়। উদাহরণস্বরূপ, 19 টি উপাদানের তালিকায় অবিকৃত, প্রথম উপাদান, মধ্যম উপাদান এবং শেষ উপাদানটির মধ্যমা প্রয়োজন হতে পারে। এই তিনটি মান আরোহী ক্রমে নাও হতে পারে; এবং তাই, তাদের সূচকগুলি অবশ্যই বিবেচনায় নেওয়া উচিত।
দ্রুত বাছাইয়ের সাথে, পুরো তালিকা এবং উপ-তালিকার মধ্যমা প্রয়োজন। একটি তালিকায় (অ্যারে) ফাঁকা তিনটি মানগুলির মধ্যমা খুঁজতে সিউডোকোড হল:
মধ্য: =।(কম+উচ্চ) / 2।যদিআগমন[মধ্য] <আগমন[কম]
অদলবদল[কম]আগমনের সাথে[মধ্য]
যদিআগমন[উচ্চ] <আগমন[কম]
অদলবদল[কম]আগমনের সাথে[উচ্চ]
যদিআগমন[মধ্য] <আগমন[উচ্চ]
অদলবদল[মধ্য]আগমনের সাথে[উচ্চ]
পিভট: =আগমন[উচ্চ]
আর শব্দটির অর্থ অ্যারে। এই কোড সেগমেন্ট মধ্যমা খুঁজছে এবং কিছু সাজানোর কাজও করে। এই কোড সেগমেন্টটি দেখতে সহজ, কিন্তু এটি বেশ বিভ্রান্তিকর হতে পারে। সুতরাং, নিম্নলিখিত ব্যাখ্যা মনোযোগ দিন:
এই টিউটোরিয়ালে বাছাই একটি তালিকা তৈরি করবে যেখানে প্রথম মান হল সবচেয়ে ছোট মান, এবং শেষ মান হল সবচেয়ে বড় মান। বর্ণমালার সাথে, A, Z এর চেয়ে কম।
এখানে, পিভট হল মধ্যমা। নিম্ন হল তালিকা বা উপ-তালিকার সর্বনিম্ন সূচক (সর্বনিম্ন মানের জন্য নয়); উচ্চ হল তালিকা বা উপ-তালিকার সর্বোচ্চ সূচক (অগত্যা সর্বোচ্চ মানের জন্য নয়), এবং মধ্যম হল প্রচলিত মধ্য সূচক (পুরো তালিকার মধ্যম মানের জন্য অগত্যা নয়)।
সুতরাং, প্রাপ্ত হওয়ার মধ্যমা হল সর্বনিম্ন সূচকের মান, মধ্যম সূচকের মান এবং সর্বোচ্চ সূচকের মানের মধ্যে।
কোডে, প্রচলিত মধ্য সূচকটি প্রথমে পাওয়া যায়। এই শুরুতে, তালিকাটি সাজানো নেই। তিনটি মূল্যের ক্রমবর্ধমান ক্রমে তুলনা এবং কিছু পুনর্বিন্যাস একই সময়ে সংঘটিত হওয়ার কথা। প্রথম if-statement সর্বনিম্ন সূচকের এবং মধ্যম সূচকের মান তুলনা করে। যদি মধ্যম সূচকটি সর্বনিম্ন সূচকের চেয়ে কম হয়, তাহলে দুটি মান অবস্থান পরিবর্তন করে। এটি বাছাই শুরু করে এবং তালিকা বা উপ-তালিকার মানগুলির বিন্যাস পরিবর্তন করে। দ্বিতীয় if-statement সর্বোচ্চ সূচকের মান এবং সর্বনিম্ন সূচকের মান তুলনা করে। যদি সর্বোচ্চ সূচকটি সর্বনিম্ন সূচকের চেয়ে কম হয়, দুটি মান অবস্থান পরিবর্তন করে। এটি তালিকা বা উপ-তালিকার মানগুলির বিন্যাসের কিছু বাছাই এবং পরিবর্তন করে। তৃতীয় if-statement মধ্যম সূচকের এবং সর্বোচ্চ সূচকের মান তুলনা করে। যদি সর্বোচ্চ সূচকের মধ্যম সূচকের চেয়ে কম হয়, দুটি মান অবস্থান পরিবর্তন করে। কিছু বাছাই বা পুনর্বিন্যাসও এখানে ঘটতে পারে। এই তৃতীয় যদি শর্ত আগের দুটির মতো না হয়।
এই তিনটি অদলবদলের শেষে, প্রশ্নে তিনটি মানগুলির মধ্যম মান হবে A [উচ্চ], যার মূল বিষয়বস্তু কোড বিভাগে পরিবর্তিত হতে পারে। উদাহরণস্বরূপ, সাজানো ক্রম বিবেচনা করুন:
C B A
আমরা ইতিমধ্যেই জানি যে মধ্যমা বি।তবে, এটি প্রমাণিত হওয়া উচিত। এখানে লক্ষ্য হল উপরের কোড সেগমেন্ট ব্যবহার করে এই তিনটি মানের মধ্যমা অর্জন করা। প্রথম if- স্টেটমেন্ট B এবং C এর তুলনা করে। B C এর চেয়ে কম, তাই নতুন ব্যবস্থা হল:
B C A
লক্ষ্য করুন, সর্বনিম্ন সূচক এবং মধ্য সূচকের মান পরিবর্তিত হয়েছে। দ্বিতীয় if- স্টেটমেন্ট A এবং B- এর তুলনা করে। A, B এর চেয়ে কম, তাই নতুন ব্যবস্থা হল:
A C B
লক্ষ্য করুন, সর্বোচ্চ সূচক এবং সর্বনিম্ন সূচকের মান পরিবর্তিত হয়েছে। তৃতীয় if- স্টেটমেন্টটি C এবং B- এর তুলনা করে। C B এর চেয়ে কম নয়, তাই কোন অদলবদল হয় না। নতুন ব্যবস্থা আগের মতোই রয়ে গেছে, অর্থাৎ:
A C B
B হল মধ্যমা, যা A [উচ্চ] এবং এটি হল পিভট। সুতরাং, পিভট তালিকা বা উপ-তালিকার চূড়ান্ত প্রান্তে জন্মগ্রহণ করে।
সোয়াপিং ফাংশন
দ্রুত সাজানোর জন্য আরেকটি বৈশিষ্ট্য প্রয়োজন অদলবদল ফাংশন। সোয়াপিং ফাংশন, দুটি ভেরিয়েবলের মান বিনিময় করে। সোয়াপিং ফাংশনের জন্য সিউডোকোড হল:
সোয়াপ সংজ্ঞায়িত করুন(এক্স,এবং)তাপমাত্রা: =এক্স
এক্স: =এবং
এবং: =তাপমাত্রা
এখানে, x এবং y প্রকৃত মানগুলি বোঝায় এবং কপি নয়।
এই নিবন্ধে বাছাই একটি তালিকা তৈরি করবে যেখানে প্রথম মান হল ক্ষুদ্রতম মান, এবং শেষ মান হল সবচেয়ে বড় মান।
নিবন্ধ বিষয়বস্তু
দ্রুত সাজানোর অ্যালগরিদম
একটি অননুমোদিত তালিকা সাজানোর স্বাভাবিক উপায় হল প্রথম দুটি মান বিবেচনা করা। যদি তারা ক্রম না হয়, তাদের ক্রম রাখুন। পরবর্তী, প্রথম তিনটি মান বিবেচনা করুন। প্রথম দুইটি স্ক্যান করে দেখুন তৃতীয় মানটি কোথায় ফিট করে এবং যথাযথভাবে ফিট করে। তারপরে, প্রথম চারটি মান বিবেচনা করুন। চতুর্থ মানটি কোথায় ফিট হয় তা দেখতে প্রথম তিনটি মান স্ক্যান করুন এবং যথাযথভাবে ফিট করুন। পুরো তালিকাটি সাজানো না হওয়া পর্যন্ত এই পদ্ধতিটি চালিয়ে যান।
কম্পিউটার প্রোগ্রামিং ভাষায় এই পদ্ধতি, যাকে বর্বর-বল সাজানোর নামেও পরিচিত, খুব ধীর। দ্রুত সাজানোর অ্যালগরিদম অনেক দ্রুত পদ্ধতির সাথে আসে।
কুইকসর্ট অ্যালগরিদমের পদক্ষেপগুলি নিম্নরূপ:
- নিশ্চিত করুন যে অরক্ষিত তালিকায় সাজানোর জন্য কমপক্ষে 2 টি সংখ্যা আছে।
- তালিকার আনুমানিক কেন্দ্রীয় মান পান, যাকে পিভট বলা হয়। উপরে বর্ণিত মধ্যমা হল পিভট পাওয়ার একটি উপায়। বিভিন্ন উপায়ে তাদের সুবিধা এবং অসুবিধাগুলি আসে। - পরে দেখা হবে.
- তালিকা ভাগ করুন। এর অর্থ, তালিকায় পিভট রাখুন। এইভাবে, বাম দিকের সমস্ত উপাদান পিভট মানের চেয়ে কম এবং ডান দিকের সমস্ত উপাদান পিভট মানের চেয়ে বড় বা সমান। বিভাজনের বিভিন্ন উপায় রয়েছে। প্রতিটি পার্টিশন পদ্ধতি তার সুবিধা এবং অসুবিধা নিয়ে আসে। পার্টিশন বিভাজন এবং বিজয়ের দৃষ্টান্তে বিভক্ত।
- পুরো তালিকা বাছাই না হওয়া পর্যন্ত নতুন উপ-তালিকা জোড়াগুলির জন্য পুনরাবৃত্তি পদক্ষেপ 1, 2 এবং 3 পুনরাবৃত্তি করুন। এটি বিভাজন এবং বিজয়ের দৃষ্টান্তে বিজয়ী।
দ্রুত সাজানোর ছদ্মকোড হল:
অ্যালগরিদম quicksort(আগমন,কম,উচ্চ)হয়যদিকম<উচ্চ তারপর
পিভট(কম,উচ্চ)
পৃ: =বিভাজন(আগমন,কম,উচ্চ)
quicksort(আগমন,কম,পৃ- ঘ)
quicksort(আগমন,পৃ+ ঘ,উচ্চ)
একটি পার্টিশন সিউডোকোড
এই টিউটোরিয়ালে ব্যবহৃত পার্টিশন সিউডোকোড হল:
অ্যালগরিদম পার্টিশন(আগমন,কম,উচ্চ)হয়পিভট: =আগমন[উচ্চ]
আমি: =কম
j: =উচ্চ
কর
কর
++আমি
যখন(আগমন[আমি] <পিভট)
কর
-j
যখন(আগমন[j] >পিভট)
যদি (আমি<j)
অদলবদল[আমি]আগমনের সাথে[j]
যখন(আমি<j)
অদলবদল[আমি]আগমনের সাথে[উচ্চ]
প্রত্যাবর্তনআমি
নীচের দ্রুত বাছাইয়ের দৃষ্টান্তে, এই কোডটি ব্যবহার করা হয়েছে:
দ্রুত সাজানোর দৃষ্টান্ত
বর্ণানুক্রমিক অক্ষরের নিম্নলিখিত বিন্যাসিত তালিকা (অ্যারে) বিবেচনা করুন:
Q W E R T Y U I O P
পরিদর্শন দ্বারা, সাজানো তালিকা হল:
E I O P Q R T U W Y
বাছাইকৃত তালিকাটি এখন প্রমাণিত হবে, উপরের অ্যালগরিদম এবং সিউডোকোড বিভাগগুলি ব্যবহার করে, সাজানো তালিকা থেকে:
Q W E R T Y U I O P
প্রথম পিভটটি arr [0] = Q, arr [4] = T, এবং arr [9] = P থেকে নির্ধারিত হয় এবং Q হিসাবে চিহ্নিত করা হয় এবং তালিকার চরম ডানদিকে স্থাপন করা হয়। সুতরাং, কোন পিভট ফাংশন বাছাইয়ের সাথে তালিকাটি হয়ে যায়:
P W E R T Y U I O Q
বর্তমান পিভট হল প্র। ফলস্বরূপ তালিকাটি পুনর্বিন্যাস করতে হবে (পার্টিশনযুক্ত), যেমন, বাম দিকের সমস্ত উপাদানগুলি মান ছোট, তারপর পিভট এবং পিভটের ডানদিকে সমস্ত উপাদান, পিভটের সমান বা বড়। কম্পিউটার পরিদর্শন দ্বারা পার্টিশন করতে পারে না। সুতরাং, এটি সূচী এবং উপরের পার্টিশন অ্যালগরিদম ব্যবহার করে।
নিম্ন এবং উচ্চ সূচীগুলি এখন 0 এবং 9। সুতরাং, সূচক 0 থেকে স্ক্যান করে কম্পিউটার শুরু হবে যতক্ষণ না এটি একটি সূচকে পৌঁছায়, যার মান পিভটের সমান বা বেশি এবং সাময়িকভাবে সেখানে থামে। এটি উচ্চ (ডান) প্রান্ত, সূচী 9 থেকে নিচে স্ক্যান করবে, যতক্ষণ না এটি একটি সূচকে পৌঁছায় যার মান পিভটের চেয়ে কম বা সমান এবং সেখানে সাময়িকভাবে থামে। এর মানে হল দুটি স্টপের অবস্থান। যদি আমি, ক্রমবর্ধমান সূচক ভেরিয়েবল, কম থেকে এখনও কমতে থাকা সূচক ভেরিয়েবলের সমান বা বেশি না হয়, জে থেকে উচ্চ, তাহলে এই দুটি মান অদলবদল হয়। বর্তমান পরিস্থিতিতে, উভয় প্রান্ত থেকে স্ক্যান করা W এবং O তে থেমে গেছে। সুতরাং তালিকাটি হল:
P O E R T Y U I W Q
পিভটটি এখনও কিউ। যদি আমি এখনও j এর সমান বা তার চেয়ে বড় না হই, তাহলে যে দুটি মান উভয় প্রান্ত থেকে স্ক্যান করা বন্ধ হয়ে যায় সেগুলি অদলবদল করা হয়। এইবার, উভয় প্রান্ত থেকে স্ক্যান করা R এবং I তে থেমে গেল। সুতরাং, তালিকার বিন্যাসটি হল:
P O E I T Y U R W Q
পিভটটি এখনও কিউ। যদি আমি এখনও j এর সমান বা তার চেয়ে বড় না হই, তাহলে যে দুটি মান স্ক্যান করা বন্ধ হয়েছে, সেগুলি অদলবদল করা হয়। এইবার, উভয় প্রান্ত থেকে স্ক্যান করা বন্ধ হয়ে গেল I for i এবং I for j। আমি এবং জে দেখা করেছি বা অতিক্রম করেছি। সুতরাং, কোন অদলবদল করা যাবে না। তালিকাটি একই রকম রয়েছে:
P O E I T Y U R W Q
এই মুহুর্তে, পিভট, Q, সাজানোর ক্ষেত্রে তার চূড়ান্ত অবস্থানে স্থাপন করতে হবে। এটি arr [i] এর সাথে ar [high], T এবং Q অদলবদল করে করা হয়।
P O E I Q Y U R W T
এই মুহুর্তে, পুরো তালিকার জন্য পার্টিশন শেষ হয়েছে। পিভট = Q তার ভূমিকা পালন করেছে। এখন তিনটি উপ-তালিকা রয়েছে, যা হল:
P O E I Q Y U R W T
বিভাজন হল দৃষ্টান্তে বিভাজন এবং বিজয় (বাছাই)। Q তার সঠিক সাজানোর অবস্থানে। Q- এর বাম প্রতিটি উপাদান Q- এর চেয়ে ছোট এবং Q- এর ডানদিকের প্রতিটি উপাদান Q- এর চেয়ে বড়। এবং সঠিক তালিকাটি এখনও সাজানো হয়নি। বাম সাব-লিস্ট এবং ডান সাব-লিস্ট সাজানোর জন্য পুরো কুইক সার্ট ফাংশনটিকে পুনরাবৃত্তিমূলক বলা উচিত। কুইক সাজানোর এই প্রত্যাহার অব্যাহত রাখতে হবে; সম্পূর্ণ মূল তালিকা সম্পূর্ণরূপে সাজানো না হওয়া পর্যন্ত নতুন উপ-তালিকা তৈরি হবে। কুইক বাছাই ফাংশনের প্রতিটি প্রত্যাহারের জন্য, সংশ্লিষ্ট ডান সাব-লিস্টে অংশ নেওয়ার আগে বাম উপ-তালিকাটি প্রথমে উপস্থিত হয়। প্রতিটি উপ-তালিকার জন্য একটি নতুন পিভট পেতে হবে।
উপ-তালিকার জন্য:
P O E I
P, O, এবং I এর জন্য পিভট (মধ্যমা) নির্ধারিত। পিভট হবে O. 4-1] = arr [3], যেখানে আমি পূর্ববর্তী পার্টিশনের চূড়ান্ত পিভট সূচক। পিভট () ফাংশন বলা হওয়ার পর, নতুন পিভট মান, পিভট = ও। পিভট ফাংশন এবং পিভট ভ্যালুর মধ্যে বিভ্রান্ত হবেন না। পিভট ফাংশন কিছু ছোট বাছাই করতে পারে এবং উপ-তালিকার চরম ডানদিকে পিভট স্থাপন করতে পারে। এই উপ-তালিকা হয়ে যায়,
I P E O
এই স্কিমের সাথে, পিভট সর্বদা তার ফাংশন কলের পরে সাব-লিস্ট বা তালিকার ডান প্রান্তে শেষ হয়। উভয় প্রান্ত থেকে স্ক্যান করা শুরু হয় arr [0] এবং arr [3] থেকে i এবং j মিলিত হওয়া বা ক্রস না হওয়া পর্যন্ত। তুলনাটি পিভট = O দিয়ে করা হয়। প্রথম স্টপগুলি P এবং E এ থাকে।
I E P O
উভয় প্রান্ত থেকে স্ক্যান করা অব্যাহত রয়েছে, এবং নতুন স্টপগুলি P এর জন্য i এবং E এর জন্য j তে রয়েছে। এখন আমি এবং জে দেখা করেছি বা অতিক্রম করেছি। সুতরাং উপ-তালিকাটি একই রকম থাকে:
I E P O
একটি উপ-তালিকা বা তালিকার বিভাজন শেষ হয় যখন পিভটকে তার চূড়ান্ত অবস্থানে রাখা হয়। সুতরাং, arr [i] এবং arr [high] এর জন্য নতুন মান বদল করা হয়। অর্থাৎ, P এবং O অদলবদল হয়। নতুন উপ-তালিকা হল:
I E O P
O এখন পুরো তালিকার চূড়ান্ত অবস্থানে রয়েছে। পিভট হিসেবে এর ভূমিকা শেষ হয়েছে। উপ-তালিকাটি বর্তমানে আরও তিনটি তালিকায় বিভক্ত, যা হল:
I E O P
এই মুহুর্তে, প্রথম ডান উপ-তালিকার দ্রুত বাছাই করতে হবে। যাইহোক, এটি বলা হবে না। পরিবর্তে, এটি নোট এবং সংরক্ষিত হবে, পরে বলা হবে। যেহেতু পার্টিশন ফাংশনের বিবৃতিগুলি কার্যকর করা হচ্ছিল, ফাংশনের শীর্ষ থেকে, এটি বাম উপ-তালিকার জন্য দ্রুত বাছাই যা এখনই বলা উচিত (পিভট () কল করার পরে)। এটি তালিকার জন্য বলা হবে:
আমি E
এটি I এবং E- এর মধ্যমা খুঁজতে শুরু করবে। এখানে, arr [low] = I, arr [mid] = I এবং arr [high] = E. যাইহোক, উপরের পিভট সিউডোকোড পিভটকে ই হিসাবে নির্ধারণ করবে। নীচের বাস্তবায়নে, কোডের কিছু সমন্বয় আছে। উপ-তালিকা হয়ে যায়,
ই আই
পিভট সর্বদা উপ-তালিকা বা তালিকার ডান প্রান্তে তার ফাংশন কলের পরে শেষ হয়। উভয় প্রান্ত থেকে স্ক্যান করা শুরু হয় arr [0] এবং arr [1] একচেটিয়াভাবে যতক্ষণ না i এবং j মিলিত বা ক্রস হয়। তুলনাটি পিভট = I এর সাথে করা হয়। প্রথম এবং একমাত্র স্টপগুলি হল I এবং E: I এ i এর জন্য এবং J এর জন্য E এ। এখন আমি এবং জে দেখা করেছি বা অতিক্রম করেছি। সুতরাং, উপ-তালিকাটি একই রকম থাকে:
ই আই
একটি উপ-তালিকা বা তালিকার বিভাজন শেষ হয় যখন পিভটকে তার চূড়ান্ত অবস্থানে রাখা হয়। সুতরাং, arr [i] এবং arr [high] এর জন্য নতুন মান বদল করা হয়। এটি এখানে ঘটে যে arr [i] = I এবং arr [high] = I. সুতরাং, একই মান নিজের সাথে বদল করা হয়। নতুন উপ-তালিকা হল:
ই আই
আমি এখন পুরো তালিকার চূড়ান্ত অবস্থানে আছি। পিভট হিসেবে এর ভূমিকা শেষ হয়েছে। উপ-তালিকাটি এখন আরও দুটি তালিকায় বিভক্ত, যা হল,
ই আই
এখন, পিভটগুলি এখন পর্যন্ত Q, O, এবং I. পিভটগুলি তাদের চূড়ান্ত অবস্থানে শেষ হয়েছে। একক উপাদানের একটি উপ-তালিকা, যেমন উপরের পি, তার শেষ অবস্থানেও শেষ হয়।
এই মুহুর্তে, প্রথম বাম উপ-তালিকা সম্পূর্ণভাবে সাজানো হয়েছে। এবং বাছাই পদ্ধতি এখন এখানে:
E I O P Q Y U R W T
প্রথম ডান উপ-তালিকা:
Y U R W T
এখনও বাছাই করা প্রয়োজন।
প্রথম ডান উপ-তালিকা জয় করা
মনে রাখবেন যে প্রথম ডান উপ-তালিকার জন্য দ্রুত সাজানোর কলটি কার্যকর হওয়ার পরিবর্তে উল্লেখযোগ্য এবং সংরক্ষিত ছিল। এই মুহুর্তে, এটি কার্যকর করা হবে। এবং তাই, নতুন arr [low] = arr [5] = arr [QPivotIndex+1], এবং নতুন arr [high] arr [9] থাকে। প্রথম বাম উপ-তালিকার জন্য একই ধরনের ক্রিয়াকলাপ এখানে ঘটবে। এবং এই প্রথম ডান উপ-তালিকাটি সাজানো হয়েছে:
R T U W Y
এবং মূল অসংগঠিত তালিকা সাজানো হয়েছে:
E I O P Q R T U W Y
জাভা কোডিং
জাভাতে অ্যালগরিদম স্থাপন করা হচ্ছে উপরের সমস্ত সিউডোকোড সেগমেন্টগুলিকে একটি ক্লাসে জাভা পদ্ধতিতে রাখা। ভুলে যাবেন না যে ক্লাসে একটি প্রধান () পদ্ধতি থাকা দরকার যা অসম্পূর্ণ অ্যারের সাথে quicksort () ফাংশনকে কল করবে।
পিভট () পদ্ধতি
জাভা পিভট () পদ্ধতি যা মান প্রদান করে, পিভট হওয়া উচিত:
শূন্যপিভট(গৃহস্থালিআগমন[], intকম, intউচ্চ) {intমধ্য= (কম+উচ্চ) / 2;
যদি (আগমন[মধ্য] <আগমন[কম])
বিনিময়(আগমন,কম,মধ্য);
যদি (আগমন[উচ্চ] <আগমন[কম])
বিনিময়(আগমন,কম,উচ্চ);
যদি ((উচ্চ-কম) > 2) {
যদি (আগমন[মধ্য] <আগমন[উচ্চ])
বিনিময়(আগমন,মধ্য,উচ্চ);
}
}
সোয়াপ () পদ্ধতি
সোয়াপ () পদ্ধতি হওয়া উচিত:
শূন্যবিনিময়(গৃহস্থালিআগমন[], intএক্স, intএবং) {গৃহস্থালিতাপমাত্রা=আগমন[এক্স];
আগমন[এক্স] =আগমন[এবং];
আগমন[এবং] =তাপমাত্রা;
}
কুইকসর্ট () পদ্ধতি
Quicksort () পদ্ধতি হওয়া উচিত:
শূন্যquicksort(গৃহস্থালিআগমন[], intকম, intউচ্চ) {যদি (কম<উচ্চ) {
পিভট(আগমন,কম,উচ্চ);
intপৃ=বিভাজন(আগমন,কম,উচ্চ);
quicksort(আগমন,কম,পৃ- ঘ);
quicksort(আগমন,পৃ+ ঘ,উচ্চ);
}
}
পার্টিশন () পদ্ধতি
পার্টিশন () পদ্ধতি হওয়া উচিত:
intবিভাজন(গৃহস্থালিআগমন[], intকম, intউচ্চ) {গৃহস্থালিপিভট=আগমন[উচ্চ];
intআমি=কম;
intj=উচ্চ;
কর {
কর
++আমি;
যখন(আগমন[আমি] <পিভট);
কর
-j;
যখন(আগমন[j] >পিভট);
যদি (আমি<j)
বিনিময়(আগমন,আমি,j);
}যখন(আমি<j);
বিনিময়(আগমন,আমি,উচ্চ);
প্রত্যাবর্তনআমি;
}
প্রধান () পদ্ধতি
প্রধান () পদ্ধতি হতে পারে:
জনসাধারণস্থির শূন্যপ্রধান(স্ট্রিং[]যুক্তি) {গৃহস্থালিআগমন[] = {'প্রশ্ন', 'ভিতরে', 'এবং', 'আর', 'টি', 'এবং', 'ইউ', 'আমি', 'অথবা', 'পি'};
TheClass QuickSort= নতুনশ্রেণী();
কুইকসর্ট।quicksort(আগমন, 0, 9);
পদ্ধতি.বাইরে।println('সাজানো উপাদান:');
জন্য(intআমি=0;আমি<10;আমি++) {
পদ্ধতি.বাইরে।ছাপা(আগমন[আমি]);পদ্ধতি.বাইরে।ছাপা('');
}
পদ্ধতি.বাইরে।println();
}
উপরের সব পদ্ধতি এক শ্রেণীতে রাখা যেতে পারে।
উপসংহার
কুইক বাছাই হল একটি বাছাইয়ের অ্যালগরিদম যা বিভাজন এবং জয় করার দৃষ্টান্ত ব্যবহার করে। এটি একটি বাছাইকৃত তালিকাকে দুই বা তিনটি উপ-তালিকায় বিভক্ত করে শুরু হয়। এই টিউটোরিয়ালে, কুইক বাছাই একটি তালিকাকে তিনটি উপ-তালিকায় বিভক্ত করেছে: একটি বাম উপ-তালিকা, একটি একক উপাদানের মধ্যম তালিকা এবং একটি ডান উপ-তালিকা। দ্রুত বাছাইয়ে বিজয়ী একটি তালিকা বা উপ-তালিকা ভাগ করার সময় এটিকে বিভাজন করা হয়, একটি পিভট মান ব্যবহার করে। এই টিউটোরিয়াল জাভা কম্পিউটার ভাষায় কুইক সাজানোর একটি বাস্তবায়ন ব্যাখ্যা করেছে।
লেখক সম্পর্কে
ক্রিসান্থাস ফোরচা
প্রথম নীতি এবং সংশ্লিষ্ট সিরিজ থেকে গণিত ইন্টিগ্রেশনের আবিষ্কারক। কারিগরি শিক্ষায় মাস্টার্স ডিগ্রি, ইলেকট্রনিক্স এবং কম্পিউটার সফটওয়্যারে বিশেষজ্ঞ। বিএসসি ইলেকট্রনিক্স। আমার কম্পিউটিং এবং টেলিকমিউনিকেশনে মাস্টার্স পর্যায়ে জ্ঞান এবং অভিজ্ঞতা আছে। 20,000 লেখকের মধ্যে, আমি devarticles.com এ 37 তম সেরা লেখক ছিলাম। আমি 10 বছরেরও বেশি সময় ধরে এই ক্ষেত্রগুলিতে কাজ করছি।
সব পোস্ট দেখুনসম্পর্কিত লিনাক্স ইঙ্গিত পোস্ট
- জাভাতে স্ট্রিংগুলির তুলনা করা
- কিভাবে জাভাতে হ্যাশম্যাপ ব্যবহার করবেন
- জাভাতে দ্রুত সাজানোর ব্যাখ্যা
- জাভাতে বাইনারি ট্রি প্রি -অর্ডার ট্র্যাভারসাল
- জাভাতে মার্জ সাজান ব্যাখ্যা করা হয়েছে
- কিভাবে জাভাতে স্ক্যানার ব্যবহার করবেন
- জাভা ফাইল লিখুন