ლექციის ჩანაწერი

ამ სემინარზე განვიხილავთ კომპიუტერული მეცნიერებების ცნობილ ალგორითმებს. მაგალითების კოდის გასაშვებად შეგიძლიათ გამოიყენოთ კონსოლი ან ჯავასკრიპტის კოდის გასაშვები საიტი

ზოგიერთი ალგორითმის წინ ეწერება ფსევდოკოდის მაგვარი აღწერა. ფსევდო კოდი არის ალგორითმის მუშაობის პრინციპის გადმოცემა სიტყვიერად, კონკრეტული პროგრამული ენის გარეშე

მაქსიმუმის და მინიმუმის პოვნა

გვაქვს სია და გვჭირდება ვიპოვოთ ყველაზე დიდი/ყველაზე პატარა ელემენტი

max იყოს პირველი ელემენტი
ყოველ შემდეგ ელემენტზე:
	შევადაროთ ელემენტი და max
		თუ მეტია, max-ის მნიშვნელობას შევცვლით

let myarr = [2, 41, 321, 2, 56, 64]

function max(myList) {
	let max = myList[0]
	// პრობლემა ხომ არ არის, რომ i-ს 0-დან ვიწყებთ?
	for (let i=0; i < myList.length; i++) {
		// რა შეიცვლება, თუ >= ს დავწერთ?
		if (myList[i] > max) {
			max = myList[i]
		}
	}
	return max
}

max(myarr) // დააბრუნებს max-ს

მინიმუმის პოვნა იქნება იმავე პრინციპით, ოღონდ if-ში ეწერება myList[i] < , >-ის მაგივრად (სცადე დაწერა დამოუკიდებლად)

სიის სორტირება

სორტირების ალგორითმების კოდის ცოდნა არ არის საჭირო, მხოლოდ უნდა გესმოდეთ განსხვავება

insertion sort

• 1. ვიწყებთ პირველი ელემენტიდან
     • 1. ვპოულობთ მინიმალურ ელემენტს ახლანდელი ელემენტის შემდეგ
     • 1. მინიმალურს და ახლანდელს ვუცვლით ადგილს
     • 1. გადავდივართ მომდევნო ელემენტზე და ვიმეორებთ მე-2 ნაბიჯიდან

let myarr = [2, 41, 321, 2, 56, 64]

function insertionSort(myList) {
	for (let i = 0; i < myList.length -1;    i++) {
		swap(myList, i, findMin(myList, i + 1))
		console.log(myList)
	}
  return myList
}

/**
 * იპოვის მინიმალური ელემენტის ინდექსს
 */
function findMin(myList, index) {
	let minIndex = index
	for (let i=index; i < myList.length; i++) {
		if (myList[i] < myList[minIndex]) {
			minIndex = i
		}
	}
	return minIndex
}

function swap(myList, j, k) {
	let temp = myList[j]
	myList[j] = myList[k]
	myList[k] = temp
}

sort1(myarr)
// [2, 2, 41, 56, 64, 321]

bubble sort

• 1. ვიწყებთ პირველი ელემენტიდან.
     • 1. ვადარებთ შემდეგ ელემენტს. თუ შემდეგ ელემენტზე მეტია ახლანდელი ელემენტი, ვუცვლით ერთმანეთს ადგილს
     • 1. გადავდივართ შემდეგ ელემენტზე და ვიმეორებთ 2-დან
• ბოლოში მისვლის შემდეგ ვბრუნდებით პირველ ელემენტზე და ვიმეორებთ 1-დან ყველა ნაბიჯს მანამ, სანამ პირველიდან ბოლო ელემენტამდე ცვლილება აღარ დაგვჭირდება.

ალგორითმების კომპლექსურობა

დავაკვირდეთ insertion და bubble sort არგუმენტებს. შეგვიძლია ვივარაუდოთ, რამდენჯერ მოგვიწევს სიაზე გადაყოლა (შედარება/შეცვლა) n-ელემენტიან სიაზე? ორივე შემთხვევაში საშუალოდ n*n-ჯერ.

კვადრატული

ამ შემთხვევაში ვამბობთ, რომ ალგორითმს აქვს კვადრატული კომპლექსურობა - ელემენტის ერთით გაზრდასთან ერთად საჭირო დრო ბევრად მეტჯერ იზრდება (წარმოიდგინეთ პარაბოლა). რატომ არის ეს ცუდი?

წრფივი

მინიმუმის და მაქსიმუმის ფუნქციებს ასეთი კოპმლექსურობა აქვთ. რამდენი ელემენტიც არის, დაახლოებით იმდენჯერ დაგვჭირდება ოპერაციების შესრულება. ეს ბევრად უკეთესია, ვიდრე კვადრატული, თუმცა როგორც წესი, პროგრამისტები ცდილობენ ალგორითმის ეფექტურობა ამაზე უკეთესიც კი იყოს.