জাভাতে শীর্ষস্থানীয় ডেটা স্ট্রাকচার এবং অ্যালগরিদম যা আপনার জানা দরকার



জাভাতে ডেটা স্ট্রাকচার এবং অ্যালগরিদমের এই ব্লগটি আপনাকে জাভার সমস্ত বড় ডেটা স্ট্রাকচার এবং অ্যালগরিদম বুঝতে সহায়তা করবে।

যদি আমি সফ্টওয়্যার বিকাশের একক অত্যন্ত গুরুত্বপূর্ণ বিষয় বাছাই করতে পারি তবে তা হবে ডেটা স্ট্রাকচার এবং অ্যালগরিদম। আপনি এটিকে প্রতিটি কম্পিউটার প্রোগ্রামারকে উপলব্ধ মৌলিক সরঞ্জাম হিসাবে ভাবতে পারেন। প্রোগ্রামিং করার সময়, আমরা ব্যবহার করি উপাত্ত কাঠামো ডেটা সঞ্চয় এবং সংগঠিত করতে, এবং অ্যালগরিদম এই স্ট্রাকচারগুলিতে ডেটা ম্যানিপুলেট করতে। এই নিবন্ধটিতে সমস্ত সাধারণ ডেটা স্ট্রাকচার এবং এ্যালগরিদমের বিশদ পর্যালোচনা রয়েছে contains পাঠকদের সুসজ্জিত হতে দেয়।

এই নিবন্ধে আলোচিত বিষয়গুলি নীচে তালিকাভুক্ত করা হয়েছে:





জাভাতে ডেটা স্ট্রাকচারস

একটি ডেটা স্ট্রাকচার হ'ল কম্পিউটারে ডেটা সংরক্ষণ এবং সংগঠিত করার একটি উপায় যাতে এটি দক্ষতার সাথে ব্যবহার করা যায়। এটি দক্ষতার সাথে বিশাল পরিমাণে ডেটা পরিচালনা করার একটি উপায় সরবরাহ করে। এবং দক্ষ ডেটা স্ট্রাকচারগুলি দক্ষ অ্যালগরিদমগুলি ডিজাইনের মূল চাবিকাঠি।

ভিতরেএই ‘জাভাতে ডেটা স্ট্রাকচারস এবং অ্যালগরিদম’ নিবন্ধটি আমরা বুনিয়াদি ডেটা স্ট্রাকচার যেমন:



আসুন তাদের প্রতিটি পরীক্ষা করে নেওয়া যাক।

জাভাতে লিনিয়ার ডেটা স্ট্রাকচারস

লিনিয়ার ডেটা স্ট্রাকচার ইন যাদের উপাদানগুলি ক্রমানুসারে এবং একরকম অর্ডার করা হয় যাতে: কেবলমাত্র একটি প্রথম উপাদান এবং শুধুমাত্র একটি আছে পরবর্তী উপাদান , সেখানে শুধুমাত্র একটি শেষ উপাদান এবং শুধুমাত্র একটি আছে পূর্ববর্তী উপাদান অন্য সমস্ত উপাদানগুলির একটি রয়েছে পরবর্তী এবং ক আগে উপাদান।

অ্যারে

একটি অ্যারে একটি লিনিয়ার ডেটা স্ট্রাকচারসূচক দ্বারা অ্যাক্সেস করা অনুরূপ উপাদানগুলির একটি গোষ্ঠীর প্রতিনিধিত্ব করা। ডেটা সংরক্ষণের আগে একটি অ্যারের আকার অবশ্যই সরবরাহ করতে হবে। নীচে তালিকাভুক্ত একটি অ্যারের বৈশিষ্ট্য রয়েছে:



  • অ্যারের প্রতিটি উপাদান একই ডেটা টাইপের এবং একই আকারের হয়
  • অ্যারের উপাদানগুলি প্রথম উপাদানটির সাথে স্বল্পতম মেমরির অবস্থান থেকে শুরু করে সূক্ষ্ম মেমরি স্থানে সংরক্ষণ করা হয়
  • অ্যারের উপাদানগুলি এলোমেলোভাবে অ্যাক্সেস করা যায়
  • অ্যারের ডেটা কাঠামো সম্পূর্ণ গতিশীল নয়

অ্যারে - এডুরেকা

উদাহরণ স্বরূপ , আমরা সেই গেমটির জন্য সেরা দশ স্কোরের উপর নজর রাখতে একটি ভিডিও গেম চাই। বরং দশটি আলাদা ব্যবহার করুন পরিবর্তনশীল এই কাজের জন্য, আমরা পুরো গোষ্ঠীর জন্য একটি একক নাম ব্যবহার করতে পারি এবং সেই গোষ্ঠীর উচ্চতর স্কোরগুলি উল্লেখ করতে সূচি নম্বরগুলি ব্যবহার করতে পারি।

যোজিত তালিকা

প্রতি একাধিক নোডের সংগ্রহ সহ একটি লিনিয়ার ডেটা স্ট্রাকচার, যেখানে ইএচ উপাদান তার নিজস্ব ডেটা এবং পরবর্তী উপাদানটির অবস্থানের জন্য একটি পয়েন্টার সঞ্চয় করে। একটি লিঙ্কযুক্ত তালিকার শেষ লিঙ্কটি শূন্যের দিকে নির্দেশ করে, শৃঙ্খলের শেষটি নির্দেশ করে। লিঙ্কযুক্ত তালিকার একটি উপাদানকে বলা হয় অ নোড । প্রথম নোডকে বলা হয় মাথাশেষ নোড বলা হয়দ্য লেজ

লিঙ্কযুক্ত তালিকার প্রকার

এককভাবে সংযুক্ত তালিকা (ইউনি-দিকনির্দেশক)

দ্বিগুণভাবে সংযুক্ত তালিকা (দ্বি-দিকনির্দেশক)

বিজ্ঞপ্তিযুক্ত লিঙ্ক তালিকা

কীভাবে ডেটা মিশ্রন করা যায় তা ঝালাই

এখানে একটি সাধারণ উদাহরণ: একত্রে লিঙ্কযুক্ত পেপারক্লিপগুলির শৃঙ্খলার মতো লিঙ্কযুক্ত তালিকার কল্পনা করুন। আপনি সহজেই উপরে বা নীচে অন্য একটি পেপারক্লিপ যুক্ত করতে পারেন। মাঝখানে একটি toোকানো এমনকি দ্রুত। আপনাকে যা করতে হবে তা হ'ল কেবল মাঝখানে চেইনটি সংযোগ বিচ্ছিন্ন করা, নতুন পেপারক্লিপ যুক্ত করা, তারপরে অন্য অর্ধেক পুনরায় সংযোগ স্থাপন করা। একটি লিঙ্ক তালিকা একই।

স্ট্যাকস

স্ট্যাক, একটি বিমূর্ত তথ্য কাঠামো, একটি সংগ্রহ বস্তু যে অনুযায়ী sertedোকানো এবং সরানো হয় সর্বশেষে প্রথম আউট (লিফো) নীতি. অবজেক্টগুলি যে কোনও সময় একটি স্ট্যাকের মধ্যে সন্নিবেশ করা যেতে পারে তবে কেবলমাত্র সর্বাধিক সন্নিবেশ করা (যা 'শেষ') অবজেক্টটি যে কোনও সময় সরিয়ে নেওয়া যেতে পারে।নীচে তালিকাভুক্ত একটি স্ট্যাকের বৈশিষ্ট্য রয়েছে:

  • এটি একটি আদেশযুক্ত তালিকা যাসন্নিবেশ এবং মুছে ফেলা কেবলমাত্র এক প্রান্তে সঞ্চালিত হতে পারে যাকে বলা হয় শীর্ষ
  • এর শীর্ষ উপাদানটিতে একটি পয়েন্টার সহ পুনরাবৃত্ত তথ্য কাঠামো
  • অনুসরণ সর্বশেষে প্রথম আউট (লিফো) নীতি
  • দুটি সর্বাধিক মৌলিক পদ্ধতি সমর্থন করে
    • পুশ (ই): স্ট্যাকের শীর্ষে এলিমেন্ট ই sertোকান
    • পপ (): মুছে ফেলুন এবং স্ট্যাকের শীর্ষ উপাদানটি ফিরিয়ে দিন

স্ট্যাকের ব্যবহারিক উদাহরণগুলির মধ্যে কোনও শব্দকে বিপরীত করার সময় অন্তর্ভুক্ত রয়েছে,এর নির্ভুলতা পরীক্ষা করতে বন্ধনীক্রম,ব্রাউজারগুলিতে এবং আরও অনেক কিছুতে কার্যকারিতা বাস্তবায়ন করা হচ্ছে

সারি

এছাড়াও বিমূর্ত তথ্য কাঠামোর অন্য ধরণের। স্ট্যাকের বিপরীতে, সারিটি বস্তুর সংকলন যা সারণি অনুসারে sertedোকানো এবং মুছে ফেলা হয় ফার্স্ট-ইন-ফার্স্ট-আউট (ফিফো) নীতি. এটি হ'ল যে কোনও সময় উপাদান সন্নিবেশ করা যেতে পারে তবে কেবল যে উপাদানটি দীর্ঘকাল সারিতে রয়েছে তা যে কোনও সময় সরিয়ে নেওয়া যেতে পারে।নীচে তালিকাভুক্ত একটি সারির বৈশিষ্ট্য রয়েছে:

  • প্রায়শই হিসাবে উল্লেখ করা হয় যে প্রথম আসবে, সে প্রথম যাবে তালিকা
  • দুটি সর্বাধিক মৌলিক পদ্ধতি সমর্থন করে
    • এনকুই (ঙ): এলিমেন্ট ই sertোকান রিয়ার কিউ এর
    • ডেকিউ (): উপাদানটি থেকে সরান এবং ফিরে দিন সামনের কিউ এর

সারি ব্যবহৃত হয়দু'টি প্রক্রিয়া, সিপিইউ শিডিউলিং, ডিস্ক শিডিউলিং এবং অন্যান্য পরিস্থিতিতে যেখানে একাধিক ব্যবহারকারীর মধ্যে সংস্থান ভাগ করা হয় এবং প্রথমে প্রথম সার্ভারের ভিত্তিতে পরিবেশন করা হয় সেগুলির মধ্যে ডেটা অ্যাসিক্রোনাস ট্রান্সফার। এই ‘জাভাতে ডেটা স্ট্রাকচারস এবং অ্যালগরিদম’ নিবন্ধের পরবর্তীটিতে, আমাদের শ্রেণিবদ্ধ ডেটা কাঠামো রয়েছে।

জাভাতে হায়ারার্কিকাল ডেটা স্ট্রাকচারগুলি

বাইনারি ট্রি

বাইনারি ট্রি একটিশ্রেণিবদ্ধ গাছের ডেটা কাঠামো যাতে প্রতিটি নোডের সর্বাধিক দুটি শিশু রয়েছে , যা হিসাবে উল্লেখ করা হয় বাম শিশু এবং ডান শিশু । প্রতিটি বাইনারি গাছের নীচের নোডগুলির গ্রুপ রয়েছে:

  • রুট নোড: এটি শীর্ষতম নোড এবং প্রায়শই প্রধান নোড হিসাবে পরিচিতকারণ অন্য সমস্ত নোডটি মূল থেকে পৌঁছানো যায়
  • বাম উপ-গাছ, এটি একটি বাইনারি গাছও
  • ডান উপ-গাছ, এটি একটি বাইনারি গাছও

নীচে তালিকাভুক্ত একটি বাইনারি গাছের বৈশিষ্ট্য রয়েছে:

  • একটি বাইনারি গাছ দুটি উপায়ে যেতে পারে:
    • গভীরতা প্রথম ট্র্যাভারসাল : অর্ডারেড (বাম-রুট-ডান), প্রেরর্ডার (রুট-বাম-ডান) এবং পোস্টর্ডার (বাম-ডান-রুট)
    • প্রস্থ প্রথম ট্র্যাভারসাল : স্তর আদেশ ট্র্যাভারসাল
  • ট্রি ট্র্যাভারসালের সময় জটিলতা: ও (এন)
  • ‘L’ = 2 স্তরে সর্বাধিক নোড numberl-1

বাইনারি গাছের প্রয়োগগুলির মধ্যে রয়েছে:

  • অনেকগুলি অনুসন্ধান অ্যাপ্লিকেশনগুলিতে ব্যবহৃত হয় যেখানে ডেটা নিয়মিত প্রবেশ / প্রস্থান করে
  • ভিজ্যুয়াল এফেক্টের জন্য ডিজিটাল চিত্রগুলি সংমিশ্রণের জন্য একটি ওয়ার্কফ্লো হিসাবে
  • রাউটার-টেবিলগুলি সংরক্ষণ করার জন্য প্রায় প্রতিটি উচ্চ-ব্যান্ডউইথ রাউটারে ব্যবহৃত হয়
  • ওয়্যারলেস নেটওয়ার্কিং এবং মেমরি বরাদ্দেও ব্যবহৃত হয়
  • সংক্ষেপণ অ্যালগরিদম এবং আরও অনেক কিছুতে ব্যবহৃত হয়

বাইনারি হিপ

বাইনারি হিপ একটি সম্পূর্ণবাইনারি গাছ, যা গাদা সম্পত্তি উত্তর। সহজ কথায় এটিনিম্নলিখিত বৈশিষ্ট্য সহ বাইনারি গাছের একটি প্রকরণ:

  • গাদা একটি সম্পূর্ণ বাইনারি গাছ: কোনও গাছকে সম্পূর্ণরূপে বলা হয় যদি তার গভীরতা সম্ভবত সম্পূর্ণ গভীর থেকে বাদে সম্পূর্ণ হয়। টিবাইনারি হ্যাপের তার সম্পত্তি এটি একটিতে সংরক্ষণের জন্য উপযুক্ত করে তোলে ।
  • গাদা সম্পত্তি অনুসরণ: একটি বাইনারি হিপ হয় হয় ন্যূনতম গাদা বা ক সর্বাধিক গাদা
    • ন্যূনতম বাইনারি গাদা: এফবা একটি গাদা প্রতিটি নোড, নোড এর মান হয় এর চেয়ে কম বা সমান বাচ্চাদের মান
    • সর্বাধিক বাইনারি হিপ: এফবা গাদা প্রতিটি নোড, নোডের মান হয় এর চেয়ে বড় বা সমান বাচ্চাদের মান

বাইনারি হ্যাপের জনপ্রিয় অ্যাপ্লিকেশনগুলির মধ্যে রয়েছেদক্ষ অগ্রাধিকার-সারিগুলি প্রয়োগ করে, একটি অ্যারেতে আরও ক্ষুদ্রতম (বা বৃহত্তম) উপাদানগুলি দক্ষতার সাথে সন্ধান করুন।

হ্যাশ টেবিল

আপনি একটি আছে যে কল্পনা অবজেক্ট এবং অনুসন্ধানটি খুব সহজ করে তুলতে আপনি এর একটি কী বরাদ্দ করতে চান। এই কী / মান জুড়ি সংরক্ষণ করার জন্য, আপনি কোনও ডাটা স্ট্রাকচারের মতো একটি সাধারণ অ্যারে ব্যবহার করতে পারেন যেখানে কী (পূর্ণসংখ্যা) ডেটা মান সংরক্ষণ করার জন্য সরাসরি সূচক হিসাবে ব্যবহার করা যেতে পারে। তবে, কীগুলি খুব বড় এবং সরাসরি সূচক হিসাবে ব্যবহার করা যায় না সে ক্ষেত্রে হ্যাশিং নামক একটি প্রযুক্তি ব্যবহৃত হয় technique

আজকাল জাভা পার্স স্ট্রিং

হ্যাশিংয়ে, বড় কীগুলি ব্যবহার করে ছোট কীগুলিতে রূপান্তরিত হয় হ্যাশ ফাংশন । মানগুলি তখন ডাকা একটি ডেটা স্ট্রাকচারে সংরক্ষণ করা হয়প্রতি হ্যাশ টেবিল. একটি হ্যাশ টেবিল এমন একটি ডেটা স্ট্রাকচার যা একটি অভিধান এডিটি প্রয়োগ করে, এমন একটি কাঠামো যা মানগুলির জন্য অনন্য কী ম্যাপ করতে পারে।

সাধারণভাবে, একটি হ্যাশ টেবিলের দুটি প্রধান উপাদান রয়েছে:

  1. বালতি অ্যারে: হ্যাশ টেবিলের জন্য একটি বালতি অ্যারে হ'ল এন সাইজের একটি অ্যারে, যেখানে এ-এর প্রতিটি কক্ষকে 'বালতি' হিসাবে বিবেচনা করা হয়, যা মূল-মান জোড়ার সংকলন। পূর্ণসংখ্যা এন অ্যারের সক্ষমতা নির্ধারণ করে।
  2. হ্যাশ ফাংশন: এটি এমন কোনও ফাংশন যা আমাদের মানচিত্রে প্রতিটি কীকে মান [0, এন এবং বিয়োগ 1] এর পরিসরের একটি পূর্ণসংখ্যার সাথে মানচিত্র করে, যেখানে এন এই টেবিলের জন্য বালতি অ্যারের ক্ষমতা।

আমরা যখন বস্তুগুলিকে হ্যাশটেবলে রাখি তখন বিভিন্ন জিনিসগুলির একই হ্যাশকোড থাকতে পারে। একে বলা হয় অ সংঘর্ষ । সংঘর্ষ মোকাবেলা করার জন্য, চেইনিং এবং ওপেন অ্যাড্রেসিংয়ের মতো কৌশল রয়েছে।

সুতরাং, এটি জাভাতে কিছু প্রাথমিক এবং সর্বাধিক ব্যবহৃত ডেটা স্ট্রাকচার। এখন যেহেতু আপনি এগুলির প্রতিটি সম্পর্কে অবগত আছেন, আপনি এগুলিকে নিজের মধ্যে প্রয়োগ করতে শুরু করতে পারেন । এটির সাহায্যে আমরা ‘জাভাতে এই‘ ডেটা স্ট্রাকচারস এবং অ্যালগরিদম ’নিবন্ধের প্রথম অংশটি সম্পন্ন করেছি। পরবর্তী অংশে, আমরা সম্পর্কে শিখতে যাচ্ছিমৌলিক অ্যালগরিদম এবং কীভাবে ব্যবহারিক অ্যাপ্লিকেশনগুলিতে বাছাই এবং অনুসন্ধান, বিভাজন এবং বিজয়, লোভী অ্যালগরিদম, গতিশীল প্রোগ্রামিংয়ের মতো ব্যবহার করতে হয়।

জাভা মধ্যে অ্যালগরিদম

জটিল গাণিতিক গণনা সমাধানের সরঞ্জাম হিসাবে Histতিহাসিকভাবে ব্যবহৃত হয়, অ্যালগরিদমগুলি কম্পিউটার বিজ্ঞানের সাথে এবং বিশেষত ডেটা স্ট্রাকচারের সাথে গভীরভাবে সংযুক্ত থাকে। একটি অ্যালগরিদম হয় নির্দেশের ক্রম যা একটি সীমাবদ্ধ সময়কালে একটি নির্দিষ্ট সমস্যা সমাধানের উপায় বর্ণনা করে। তারা দুটি উপায়ে প্রতিনিধিত্ব করা হয়:

  • ফ্লোচার্টস - এটাএকটি অ্যালগরিদমের নিয়ন্ত্রণ প্রবাহের ভিজ্যুয়াল প্রতিনিধিত্ব
  • সুডোকোড - এটাচূড়ান্ত উত্স কোডটি প্রায় অ্যালগরিদমের একটি পাঠ্য উপস্থাপনা

বিঃদ্রঃ: অ্যালগরিদমের পারফরম্যান্স সময় জটিলতা এবং স্থান জটিলতার ভিত্তিতে পরিমাপ করা হয় is বেশিরভাগ ক্ষেত্রে, যে কোনও অ্যালগরিদমের জটিলতা সমস্যা এবং নিজেই অ্যালগরিদমের উপর নির্ভরশীল।

আসুন জাভাতে দুটি বড় বিভাগের অ্যালগরিদমগুলি ঘুরে দেখি, যা হ'ল:

জাভাতে অ্যালগরিদম বাছাই করা হচ্ছে

বাছাই করা অ্যালগরিদমগুলি হল অ্যালগোরিদম যা একটি তালিকার উপাদানগুলিকে একটি নির্দিষ্ট ক্রমে রাখে। সর্বাধিক ব্যবহৃত আদেশগুলি হ'ল সংখ্যাসূচক অর্ডার এবং লিক্সোগ্রাফিকাল ক্রম। এই ‘ডেটা স্ট্রাকচারস এবং অ্যালগরিদম’ নিবন্ধে কয়েকটি বাছাই করা অ্যালগরিদমগুলি অন্বেষণ করতে দেয়।

জাবাতে বাবলি বাছাই করুন

বুদ্বুদ বাছাই, প্রায়শই ডুবন্ত বাছাই হিসাবে পরিচিত, সর্বাধিক সর্টিং অ্যালগরিদম। এটি বার বার তালিকা অনুসারে বাছাই করার জন্য পদক্ষেপগুলি সংলগ্ন উপাদানগুলির প্রতিটি জুটির সাথে তুলনা করে এবং যদি তারা ভুল ক্রমে থাকে তবে এগুলি অদলবদল করে।বুদ্বুদ সাজানোর নামটি পেয়ে যায় কারণ এটি অ্যারের শীর্ষে উপাদানগুলিকে ফিল্টার করে যেমন পানিতে ভাসমান বুদবুদগুলি।

এখানেসিউডোকোড বুদ্বুদ বাছাই অ্যালগরিদম (আরোহণের সাজানোর প্রসঙ্গ) উপস্থাপন করে।

a [] হ'ল N মাপের একটি অ্যারে হ'ল বুবলসোর্ট (ক []] পূর্ণসংখ্যা i, j এর জন্য i = 0 থেকে N - 1 জে = 0 থেকে এন - i - 1 যদি একটি [জে]> এ [জে + 1 ] তারপরে একটি [জে], একটি [জে + 1] প্রান্তটি বদল করুন যদি শেষের জন্য শেষ হয় বাবলসোর্ট

এই কোডটি এন ডেটা আইটেমগুলির এক-মাত্রিক অ্যারেটিকে আরোহণের ক্রমে অর্ডার করে। একটি বাহ্যিক লুপ এন -1 অ্যারের উপরে দিয়ে যায়। প্রতিটি পাস ডেটা আইটেমের আদান প্রদানের জন্য একটি অভ্যন্তরীণ লুপ ব্যবহার করে যাতে পরের ক্ষুদ্রতম ডাটা আইটেমটি 'বুদবুদ' অ্যারের প্রারম্ভিক দিকে থাকে। তবে সমস্যাটি হল তালিকাটি সাজানো হয়েছে তা জানতে অ্যালগরিদমের কোনও অদলবদল ছাড়াই একটি পুরো পাসের প্রয়োজন needs

সবচেয়ে খারাপ এবং গড় কেস জটিলতা: ও (এন * এন) সবচেয়ে খারাপ ক্ষেত্রে ঘটে যখন একটি অ্যারে বিপরীত সাজানো হয়।

সেরা কেস টাইম জটিলতা: চালু). কোনও অ্যারে ইতিমধ্যে বাছাই করা হলে সেরা কেস হয়।

জাভা নির্বাচন বাছাই করুন

নির্বাচন বাছাই করা অনুসন্ধান এবং বাছাই উভয়ের সংমিশ্রণ। অ্যালগোরিদম অরসেট করা অংশ থেকে বার বার ন্যূনতম উপাদানটি (আরোহণের ক্রম বিবেচনা করে) সন্ধান করে এবং অ্যারেতে যথাযথ অবস্থানে রেখে একটি অ্যারে বাছাই করে।

এখানে সিলেক্ট বাছাই অ্যালগরিদমের প্রতিনিধিত্বকারী সিউডোকোড (আরোহী সাজানোর প্রসঙ্গ)।

a [] হ'ল এন সাইজের সিলেকশনসোর্ট (এ []) এর জন্য i = 0 থেকে এন - 1 / * বর্তমান উপাদানকে ন্যূনতম হিসাবে সেট করুন * / মিনিট = i / * ন্যূনতম উপাদানটি সন্ধান করুন * / জে = i + 1 এর জন্য এন যদি তালিকা [জে]

কোড থেকে আপনি বুঝতে পারবেন, অ্যারেতে বাছাইয়ের সময়টি অ্যারের আইটেমের সংখ্যার চেয়ে কম। অভ্যন্তরীণ লুপটি পরের ক্ষুদ্রতম মানটি এবং বাইরের লুপগুলি তার যথাযথ স্থানে আবিষ্কার করে। নির্বাচনের বাছাই কখনই ও (এন) এর চেয়ে বেশি অদলবদল করে না এবং মেমরি রাইটিং ব্যয়বহুল ক্রিয়াকলাপের ক্ষেত্রে কার্যকর হতে পারে।

সময় জটিলতা: চালু) যেমন দুটি নেস্টড লুপ রয়েছে।

সহায়ক স্থান: বা (1)।

জাভাতে সন্নিবেশ সাজান

সারণি বাছাই একটি সরল বাছাই অ্যালগরিদম যা একবারে একটি ইনপুট উপাদান গ্রহণ করে তালিকার মাধ্যমে পুনরাবৃত্তি করে এবং চূড়ান্ত বাছাই করা অ্যারে তৈরি করে। এটি খুব সহজ এবং ছোট ডেটা সেটগুলিতে আরও কার্যকর। এটি স্থিতিশীল এবং ইন-প্লেস বাছাইয়ের কৌশল।

সন্নিবেশ অনুসারে বাছাই করা অ্যালগরিদমের প্রতিনিধিত্বকারী সিউডোকোড (আরোহী সাজানোর প্রসঙ্গ)।

a [] হ'ল এন সাইজের এন আর্ট ইনসারেশনসোর্ট (ক []] এর জন্য i = 1 থেকে এন কী = এ [আই] জে = আই - 1 সময় (জে> = 0 এবং এ [জে]> কী0 এ [জে + 1] = x [জে] জে = জ - ১ প্রান্ত যখন একটি [জে + ১] = শেষ সন্নিবেশের জন্য কী প্রান্ত

আপনি কোড থেকে বুঝতে পারবেন, সন্নিবেশ সাজানোর অ্যালগরিদমইনপুট ডেটা থেকে একটি উপাদান সরিয়ে দেয়, সাজানো তালিকার মধ্যে এটির অবস্থানটি খুঁজে পায় এবং এটি সেখানে সন্নিবেশ করায়। কোনও ইনপুট উপাদানগুলি সাজানো না হওয়া পর্যন্ত এটি পুনরাবৃত্তি করে।

সর্বোত্তম ঘটনা: ইনপুটটি ইতিমধ্যে বাছাই করা এমন অ্যারে হলে সবচেয়ে ভাল কেস হয়। এই ক্ষেত্রে সন্নিবেশ সাজানোর ক্ষেত্রে একটি রৈখিক চলমান সময় থাকে (যেমন, এবং থেটা (এন))।

সবচেয়ে খারাপ ক্ষেত্রে: সর্বাধিক নিকৃষ্টতম কেস ইনপুট হ'ল বিপরীত ক্রমে সাজানো অ্যারে।

জাভাতে কুইকসোর্ট

কুইকসোর্ট অ্যালগরিদম হ'ল একটি দ্রুত, পুনরাবৃত্ত, অ-স্থিতিশীল ধরণের অ্যালগরিদম যা বিভাজন এবং বিজয় নীতি দ্বারা কাজ করে। এটি পাইভট হিসাবে একটি উপাদান এবং সেইটিকে বেছে নেওয়া পিভটের চারপাশে প্রদত্ত অ্যারের পার্টিশন হিসাবে চিহ্নিত করে।

দ্রুত সাজানোর বাস্তবায়নের পদক্ষেপ:

  1. একটি উপযুক্ত 'পিভট পয়েন্ট' চয়ন করুন।
  2. তালিকাগুলি দুটি তালিকায় বিভক্ত করুনএই পিভট উপাদানটির উপর ভিত্তি করে। পিভট এলিমেন্টের চেয়ে ছোট প্রতিটি উপাদান বাম তালিকায় এবং প্রতিটি উপাদান যা বড় সেগুলি ডান তালিকায় রাখা হয়। যদি কোনও উপাদান পিভট এলিমেন্টের সমান হয় তবে এটি যে কোনও তালিকায় যেতে পারে। একে পার্টিশন অপারেশন বলে।
  3. ছোট ছোট প্রতিটি তালিকাকে পুনরাবৃত্তভাবে বাছাই করুন।

এখানে কুইকসোর্ট অ্যালগরিদমের প্রতিনিধিত্বকারী সিউডোকোড।

কুইকসোর্ট (এ অ্যারে হিসাবে কম, ইনট হিসাবে কম, ইনট হিসাবে উচ্চ) - যদি (কম)

উপরের সিউডোকোডে, বিভাজন () ফাংশন পার্টিশন অপারেশন এবং কুইকোর্ট () ফাংশন বারবার তৈরি প্রতিটি ছোট তালিকার জন্য পার্টিশন ফাংশন কল। গড় ক্ষেত্রে কুইকোর্টের জটিলতা হ'ল & থেটা (এন লগ (এন)) এবং সবচেয়ে খারাপ ক্ষেত্রে & থেটা (এন 2)।

জাভাতে বাছাই করুন

Mergesort একটি দ্রুত, পুনরাবৃত্ত, স্থিতিশীল সাজানোর অ্যালগরিদম যা বিভাজন এবং বিজয় নীতি দ্বারাও কাজ করে। কুইকোর্টের অনুরূপ, মার্জ সাজান উপাদানগুলির তালিকা দুটি তালিকায় বিভক্ত করে। এই তালিকাগুলি স্বাধীনভাবে বাছাই করা হয় এবং তারপরে সংযুক্ত করা হয়। তালিকাগুলির সংমিশ্রণের সময়, উপাদানগুলি তালিকার সঠিক স্থানে sertedোকানো হয় (বা মার্জড)।

মার্জ বাছাই অ্যালগরিদমের প্রতিনিধিত্বকারী সিউডোকোড এখানে।

পদ্ধতি MergeSort (একটি অ্যারে হিসাবে) যদি (n == 1) অ্যারে হিসাবে একটি var l1 ফিরে আসে = ক [0] ... একটি [n / 2] ভরা l2 অ্যারের হিসাবে = একটি [এন / 2 + 1] ... a [n] l1 = একীভূতকরণ (l1) l2 = একীভূতকরণ (l2) রিটার্ন মার্জ (l1, l2) শেষ প্রক্রিয়া পদ্ধতিটি মার্জ (একটি অ্যারে হিসাবে, বি হিসাবে অ্যারে) ভেরি সি হিসাবে অ্যারে (a এবং খ উপাদান রয়েছে) যদি ( a [0]> খ [0]) সি এর শেষের সাথে খ [0] কে যোগ করুন বি [0] বি থেকে অন্য একটি [0] যুক্ত করুন সি এর শেষে একটি [0] মুছুন যদি শেষের সময় হয় (একটি উপাদান রয়েছে) সি এর প্রান্তে একটি [0] যুক্ত করুন যখন একটি প্রান্ত থেকে একটি [0] সরিয়ে ফেলুন (বি উপাদান রয়েছে) গ এর শেষের দিকে খ [0] যোগ করুন খ ফিরে আসার সময় খ [0] কে সরান সি শেষ পদ্ধতি

সংযুক্তি () ফাংশন তালিকাটিকে দুটি, কলগুলিতে ভাগ করে সংযুক্তি () এই তালিকাগুলিতে পৃথকভাবে এবং তারপরে () ফাংশনটি মার্জ করার জন্য প্যারামিটার হিসাবে প্রেরণ করে তাদের একত্রিত করে।অ্যালগরিদমের ও (এন লগ (এন)) এর জটিলতা রয়েছে এবং এতে রয়েছে বিস্তৃত অ্যাপ্লিকেশন।

জাভা মধ্যে গাদা সাজান

হিপসোর্ট একটি তুলনা ভিত্তিক বাছাই অ্যালগরিদমবাইনারি হিপ ডেটা স্ট্রাকচার। আপনি এটিকে উন্নত সংস্করণ চ নির্বাচনের ধরণের হিসাবে ভাবতে পারেন, যেখানেএটি তার ইনপুটটিকে বাছাই করা এবং একটি সাজানো অঞ্চলে বিভক্ত করে এবং এটি পুনরুক্ত আকারে বৃহত্তম উপাদান খুঁজে বের করে এবং সাজানো অঞ্চলে স্থানান্তরিত করে সাজানো অঞ্চলটিকে সঙ্কুচিত করে।

কুইকসোর্ট বাস্তবায়নের পদক্ষেপ (ক্রমবর্ধমান ক্রমে):

  1. বাছাই করা অ্যারে দিয়ে একটি সর্বাধিক গাদা তৈরি করুন
  2. এই পয়েন্টেt, বৃহত্তম আইটেমটি গাদাটির গোড়ায় সংরক্ষণ করা হয়। এটি স্তূপের শেষ আইটেমটির সাথে প্রতিস্থাপন করুন এবং স্তূপের আকার 1 দ্বারা হ্রাস করুন শেষ পর্যন্ত গাছের গোড়াটি হিপিফায়েট করুন
  3. স্তূপের আকার 1 এর চেয়ে বেশি না হওয়া পর্যন্ত উপরের পদক্ষেপগুলি পুনরাবৃত্তি করুন

হিপ বাছাই অ্যালগরিদমের প্রতিনিধিত্বকারী সিউডোকোড এখানে।

(I = n / 2 - 1) থেকে i> = 0 হ্যাপিফ্ট (a, n, i) i = n-1 থেকে 0 স্যুপের জন্য (একটি [0], a [i]) হিপসোর্ট (একটি অ্যারে হিসাবে অ্যারে) (a, i, 0) হিপিফাইয়ের জন্য শেষের সমাপ্তি (একটি হিসাবে অ্যারে, এন হিসাবে অন্তর্নিহিত, আমি অন্তর্নিহিত) বৃহত্তম = i // রুট ইনট হিসাবে বৃহত্তর প্রারম্ভিক l eft = 2 * i + 1 // বাম = 2 * i + 1 ইন ডান = 2 * আমি + 2 // ডান = 2 * আমি + 2 যদি (বাম একটি [বৃহত্তম]) বৃহত্তম = বামে (ডান একটি [বৃহত্তম]) বৃহত্তম = ডান যদি (বৃহত্তম! = I) অদলবদল ( a [i], A [বৃহত্তম]) হিপিফাই (এ, এন, বৃহত্তম) শেষ হিপিফায়েট

এগুলি ছাড়াও, আরও বাছাই করা অ্যালগরিদম রয়েছে যা পরিচিত, যেমন, ইনট্রোসোর্ট, কাউন্টিং সাজান ইত্যাদি not এই ‘ডেটা স্ট্রাকচারস এবং অ্যালগরিদম’ নিবন্ধে অ্যালগরিদমগুলির পরবর্তী সেটগুলিতে চলে আসা যাক, অনুসন্ধানের অ্যালগরিদমগুলি ঘুরে দেখি।

জাভাতে অ্যালগরিদম অনুসন্ধান করা

নিয়মিত ব্যবসায়িক অ্যাপ্লিকেশনগুলিতে সন্ধান করা সর্বাধিক সাধারণ এবং প্রায়শই সম্পাদিত ক্রিয়া। আইটেমের সংগ্রহের মধ্যে নির্দিষ্ট বৈশিষ্ট্যযুক্ত আইটেম সন্ধানের জন্য অনুসন্ধান অ্যালগরিদমগুলি অ্যালগরিদম। আসুন সর্বাধিক ব্যবহৃত দুটি অনুসন্ধানের আলগোরিদিমগুলি ঘুরে দেখি।

জাভাতে লিনিয়ার অনুসন্ধান আলগোরিদিম

লিনিয়ার সন্ধান বা ক্রমিক অনুসন্ধান হ'ল সহজ অনুসন্ধান অ্যালগরিদম। এতে উপাদানটিকে সন্ধান না করা বা কাঠামোর শেষ না হওয়া অবধি প্রদত্ত ডেটা স্ট্রাকচারের কোনও উপাদানটির সিক্যুয়াল অনুসন্ধান করা জড়িত। যদি উপাদানটি পাওয়া যায়, তবে আইটেমটির অবস্থান ফিরে আসে অন্যথায় অ্যালগরিদম NULL প্রদান করে।

এখানে জাভাতে লিনিয়ার অনুসন্ধান উপস্থাপন করে সিউডোকোড:

প্রক্রিয়া রৈখিক_আরক্ষ (একটি [], মান) i = 0 থেকে এন -1 এর জন্য যদি একটি [i] = মান হয় তবে প্রিন্ট করুন 'পাওয়া গেল' রিটার্ন আমি শেষ করব যদি প্রান্তরেখার জন্য 'পাওয়া যায় না' প্রান্তটি পাওয়া যায়

এটাব্রুট-ফোর্স অ্যালগরিদম।যদিও এটি অবশ্যই সহজতম, এটি তার অদক্ষতার কারণে এটি সর্বাধিক সাধারণ নয়। লিনিয়ার অনুসন্ধানের জটিলতা হ'ল চালু)

জাভাতে বাইনারি অনুসন্ধান অ্যালগরিদম

বাইনারি অনুসন্ধান, যা লগারিদমিক অনুসন্ধান হিসাবে পরিচিত, এটি একটি অনুসন্ধান অ্যালগরিদম যা ইতিমধ্যে সাজানো অ্যারের মধ্যে একটি লক্ষ্য মানের অবস্থান খুঁজে পায়। এটি ইনপুট সংগ্রহকে সমান ভাগে ভাগ করে দেয় এবং আইটেমটিকে তালিকার মাঝের উপাদানটির সাথে তুলনা করা হয়। যদি উপাদানটি পাওয়া যায় তবে অনুসন্ধানটি সেখানেই শেষ হয়। অন্যথায়, টার্গেট উপাদানটি মধ্য উপাদানের চেয়ে ছোট বা বড় কিনা তার উপর ভিত্তি করে আমরা অ্যারের উপযুক্ত পার্টিশনটি ভাগ করে এবং নির্বাচন করে উপাদানটির সন্ধান করতে থাকি।

এখানে জাভাতে বাইনারি অনুসন্ধান উপস্থাপন করে সিউডোকোড:

প্রক্রিয়া বাইনারি_সন্ধান করুন সারণিযুক্ত অ্যারে এন আকারের অ্যারের x মানের সন্ধান করতে নিম্ন বাউন্ড = 1 আপারবাউন্ড = এন যখন এক্স পাওয়া যাবেনা

উপরের বাউন্ড (আমাদের পয়েন্টার) লোয়ারবাউন্ড (শেষ উপাদান) এর অতীত হয়ে গেলে অনুসন্ধানটি শেষ হয়, যা বোঝায় যে আমরা পুরো অ্যারেটি অনুসন্ধান করেছি এবং উপাদানটি উপস্থিত নেই।এটি তাত্ক্ষণিক অনুসন্ধানের সময়ের কারণে এটি সর্বাধিক ব্যবহৃত সন্ধান অ্যালগরিদম হয়। বাইনারি অনুসন্ধানের সময় জটিলতা চালু) যা এর উপর একটি লক্ষণীয় উন্নতি চালু) লিনিয়ার অনুসন্ধানের জটিলতা।

ফিবোনাচি সিরিজ সি ++

এটি আমাদের এই ‘জাভাতে ডেটা স্ট্রাকচারস এবং অ্যালগরিদম’ নিবন্ধের শেষের দিকে নিয়ে আসে। আমি জাভার অন্যতম মৌলিক এবং গুরুত্বপূর্ণ বিষয় coveredেকে রেখেছি।আশা করি আপনি এই নিবন্ধে আপনার সাথে যা ভাগ করে নেওয়া হয়েছে তার সাথে পরিষ্কার হয়ে গেছেন।

আপনি যথাসম্ভব অনুশীলন নিশ্চিত করুন এবং আপনার অভিজ্ঞতাটি ফিরিয়ে দিন।

দেখুন বিশ্বজুড়ে ছড়িয়ে থাকা 250,000 এরও বেশি সন্তুষ্ট শিক্ষার্থীর নেটওয়ার্ক সহ একটি বিশ্বস্ত অনলাইন লার্নিং সংস্থা এডুরেকা দ্বারা। আমরা আপনার যাতায়াতের প্রতিটি পদক্ষেপে আপনাকে সহায়তা করতে এখানে এই জাভা সাক্ষাত্কারের প্রশ্নগুলির পাশাপাশি হয়ে উঠার জন্য আমরা একটি পাঠ্যক্রম নিয়ে এসেছি যা জাভা ডেভেলপার হতে চান এমন শিক্ষার্থী এবং পেশাদারদের জন্য তৈরি করা হয়েছে।

আমাদের জন্য একটি প্রশ্ন আছে? দয়া করে এই ‘জাভাতে ডেটা স্ট্রাকচারস এবং অ্যালগরিদম’ এর মন্তব্য বিভাগে উল্লেখ করুন নিবন্ধ এবং আমরা যত তাড়াতাড়ি সম্ভব আপনার কাছে ফিরে আসব।