Algoritmet dhe strukturat e të dhënave nga zero në hero

Në shkencat kompjuterike, renditja e përzgjedhjes është një algoritëm i renditjes krahasuese në vend. - Wikipedia

Për të ndjekur këtë artikull duhet të kuptoni temat e mëposhtme:

Analogjia

Supozoni se keni një mori këngësh në kompjuterin tuaj.

Për secilin artist, ju keni një numër shfaqjesh.

Ju dëshironi ta renditni këtë listë nga më së shumti në më pak të luajtur, në mënyrë që të mund të renditni artistët tuaj të preferuar. Si mund ta bëni?

Një mënyrë është të kaloni nëpër listë dhe të gjeni artistin më të luajtur. Shtoni atë artist në një listë të re.

Bëje përsëri për të gjetur artistin tjetër më të luajtur.

Vazhdoni ta bëni këtë dhe do të përfundoni me një listë të renditur.

Kompleksiteti kohor

Për të gjetur artistin me numrin më të madh të shfaqjeve, duhet të kontrolloni çdo artikull në listë. Kjo kërkon kohë O(n), siç sapo e patë. Pra, ju keni një operacion që kërkon kohë O(n) dhe duhet ta bëni atë n herë:

Kjo tikes O(n x n) kohën ose O(n^2) kohën.

Shembull i listimit të kodeve

Rendit një grup nga më i vogli tek më i madhi.

Le të shkruajmë një funksion për të gjetur elementin më të vogël në një grup:

// Search the remainder of the array for the smallest number
function findSmallest(nums, index) {
  let smallest = nums[index];
  let swapIndex = index;
  for (let i = index + 1; i <= nums.length; i++) {
    if (nums[i] < smallest) {
      smallest = nums[i];
      swapIndex = i;
    }
  }
  return { swapIndex, smallest };
}

Tani mund të përdorni këtë funksion për të shkruar renditjen e përzgjedhjes:

const selectionSort = (nums) => {
  for (let i = 0; i < nums.length - 1; i++) {
    const { smallest, swapIndex } = findSmallest(nums, i);
// Swap if the smallest number isn't at the current index
    if (i !== swapIndex) {
      const tmp = nums[i];
      nums[i] = smallest;
      nums[swapIndex] = tmp;
    }
  }
  return nums;
};

Përmbledhje

  • Renditja e përzgjedhjes është algoritmi më i thjeshtë i renditjes që funksionon duke gjetur në mënyrë të përsëritur elementin minimal (duke marrë parasysh rendin rritës) nga pjesa e pa sortuar dhe duke e vendosur atë në fillim.

Burimet

  • Wikipedia
  • Geeks për geeks
  • Algoritmet Grokking (libër)

Tabela e përmbajtjes | Tjetër(Së shpejti) ➡️