Sort.md

Sort

პრობლემა:

კონსოლიდან შეგყვავს n და შემდეგ n ცალი მთელი რიცხვი, დაალაგეთ რიცხვები
ზრდადობით და დაბეჭდეთ.

პრობლემის გადაჭრის გზა

ჩვენი ამოცანა შეგვიძლია სამ ნაწილად დავყოთ

1. წავიკითხოთ n ცალი მთელი რიცხვი და შევინახოთ თითოეული ArrayList-ში
2. შევქმნათ ფუნქცია რომელიც მიიღებს Int-ების ArrayList-ს და უკან დაგვიბრუნებს დალაგებულ მიმდევრობას
3. დავბეჭდოთ ჩვენი ფუნქციის მიერ დაბრუნებული მიმდევრობა.

პრობლემის გადაჭრის გზის კოდად გარდაქმნა

1. წავიკითხოთ n კონსოლიდან, ამისთვის გამოვიყენოთ მეთოდი readInt();, ამის შემდეგ კი for ციკლის გამოყენებით წავიკითხოთ n ცალი რიცხვი, თითოეული კი შევინახოთ Integer-ების ArrayList-ში, შესაბამისად მივიღებთ კოდს

	int n = readInt("N: ");
	ArrayList<Integer> array = new ArrayList<Integer>();
		
	for(int i = 0; i < n; i++) {
		int newNum = readInt("Enter Num: ");
		array.add(newNum);
	}	

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

3. ბოლოს კი უნდა დავბეჭდოთ ჩვენი რიცცხვები, ამისთვისაც შეგვიძლია ცალკე ფუნქცია შევქმნათ, რომელიც მიიღებს ArrayList-ს და for ციკლის გამოყენებით თითოეულ წევრს დაბეჭდავს შესაბამისად მივიღებთ კოდს

	private void printArray(ArrayList<Integer> array) {
		
		for(int i = 0; i < array.size(); i++) {
			
			println(i + " --- " + array.get(i));
		}
	}

ბონუსი

რა თქმა უნდა selectionSort-ის ნაცვლად შეგვეძლო სხვა უფრო სწრაფი ალგორითმიც გამოგვეყენებინა, მაგალითად mergeSort, რომელიც შემდეგნაირია:

1. გავყოთ n ელემენტიანი მიმდევრობა ორ n / 2 ელემენტის შემცველ ქვემიმდევრობად
2. მიღებული ქვემიმდევრობები კვლავ გავყოთ ორ ტოლ ნაწილად და ასე გავაგრძელოთ მანამ სანამ ყველა ქვემიმდევრობაში ერთი ლემენტი არ დაგვრჩება
3. მიღებული ქვემიმდევრობები გავაერთიანოთ წყვილ-წყვილად ისე, რომ თითოეული გაერთიანებული ქვემიმდევრობა დალაგებული იყოს.