Walker dasturchi, frilanser, gik va introvert Faoliyat

Kontentga o’tish
WALKER
Dasturchi, frilanser, gik va introvert

• 
  Faoliyat
  

• 
  Frilans
  

• 
  Algoritmlar
  

• 
  Sayohat
  

• 
  Islom
  

• 
  Munosabat
  

• 
  Betartib
  

• 
  Muallif
  

POSTED ONSENTABR 16, 2020 BY SHERZOD SHERMUKHAMEDOV
Tartiblash. Insertion sort

Algoritmlar bo’yicha navbatdagi maqolalar tartiblash metodlari haqida bo’ladi. Eng oson va oddiy tartiblash algoritmlaridan biri – Insertion sort. U array elementlarini solishtirib, elementlarning o’rnini almashtirish hisobiga tartiblaydi.
Insertion sort’ning ustunliklari:

• 
  Oddiy algoritm
  
• 
  Kichik array’lar uchun mahsuldorlik yuqori
  

Kamchiliklari:

• 
  Katta array’larda mahsuldorlik pasayib ketadi, sababi juda ko’p solishtirishlarni amalga oshirish kerak bo’ladi.
  
• 
  Upper bound – ¼ N² ~ O(N²). Algoritm mergesort va quicksort bilan solishtirganda yaxshi natija ko’rsatmaydi.
  

Ishlash konsepti

1. 
   Arrayning ikkinchi elementini birinchi elementi bilan solishtiramiz. Agar ikkinchi element katta bo’lsa, birinchi element va ikkinchi element o’rnini almashtiramiz.
   
2. 
   Arrayning uchinchi elementini ikkinchi elementi bilan solishtiramiz. Agar uchinchi elementi ikkinchi elementidan katta bo’lsa, uchinchi va ikkinchi element o’rnini almashtiramiz. So’ng 1-qadamni takrorlaymiz.
   
3. 
   Arrayning to’rtinchi elementini uchinchi elementi bilan solishtiramiz. Agar to’rtinchi elementi uchinchi elementidan katta bo’lsa, to’rtinchi va uchinchi element o’rnini almashtiramiz. So’ng 2-qadamni takrorlaymiz.
   

Animatsion ko’rinishda:
Insertion sort
Kod:

	function insertionSort(arr = []) {
	const length = arr.length
	for (let i = 1; i < length; i++) {
	for (let j = i; j > 0; j--) {
	if (arr[j] < arr[j - 1]) {
	// Ikki element o'rnini almashtiramiz.
	[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
	}
	else {
	// Keyingi solishtirishlarning foydasi yo'q.
	// Ular allaqachon tartiblangan.
	break
	}
	}
	}
	return arr
	}

view rawinsertion-sort.js hosted with ❤ by GitHub
Note: Funksiya faqat integer sonlarni to’g’ri tartiblaydi. Harflarni yoki string sonlarni tartiblash uchun «<» dan boshqa amalni ishlatish kerak. Masalan, ES6 uchun String.prototype.localeCompare() ni ishlatib ko’ring.
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sorts/insertion-sort.js
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.
CATEGORIESALGORITMLARTAGSALGORITMLAR, INSERTION SORT, SORT
Post menyusi
Previous PostPREVIOUSFull time dasturchidan frilanserlikka. Frilansning ustunliklari va kamchiliklari
Next PostKEYINGITartiblash. Selection sort
Top of Form
Qidirshish:Izlash
Bottom of Form
KUZATIB BORING

• 
  
• 
  
• 
  
•