O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Tizimli va amaliy dasturlash kafedrasi

Algoritmlarni loyihalash fani bo’yicha

LABORATORIYA ISHI

Mavzu: Murakkab ma’lumotlar tuzilmasi. Ustuvor navbatlar

Bajardi: CAL020-L3 guruh talabasi

Xo’rozov Ilyos

Tekshiridi: Xamidullayev Abdulbosit

TOSHKENT 2020

Variant № 16

1-topshiriq:

Dastur kodi:

import java.util.Random;

public class Main {
private static final Random r = new Random();

public static void main(String[] args) {

System.out.println("Shaker sort:");
System.out.println("n = 450, time = " + shakerSortTime(450) + " ns");
System.out.println("n = 1800, time = " + shakerSortTime(1800) + " ns");
System.out.println("n = 5500, time = " + shakerSortTime(5500) + " ns");
System.out.println("Quick sort:");
System.out.println("n = 450, time = " + quickSortTime(450) + " ns");
System.out.println("n = 1800, time = " + quickSortTime(1800) + " ns");
System.out.println("n = 5500, time = " + quickSortTime(5500) + " ns");
System.out.println("Insertion sort:");
System.out.println("n = 450, time = " + insertionSortTime(450) + " ns");
System.out.println("n = 1800, time = " + insertionSortTime(1800) + " ns");
System.out.println("n = 5500, time = " + insertionSortTime(5500) + " ns");
}

private static long shakerSortTime(int n){

int[] a = randomArray(n);

long begin = System.nanoTime();

for (int i = 0; i < n/2; i++) {
boolean swapped = false;

for (int j = i; j < n-i-1; j++){

if (a[j] > a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
swapped = true;
}
}

for (int j = n-i-2; j > i; j--) {

if (a[j] < a[j-1]){
int tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
swapped = true;
}
}

if (!swapped) break;

}

long end = System.nanoTime();

return end - begin;
}

private static long quickSortTime(int n){

int[] a = randomArray(n);

long begin = System.nanoTime();

quickSortHelper(a,0, n-1);

long end = System.nanoTime();

return end - begin;
}

private static void quickSortHelper(int[] a, int left, int right){

if (left >= right) return; //end-point of recursion
int last = left-1;

for(int i = left; i < right; i++){

if (a[i] < a[right]){ //right element is pivot element
if (++last != i){
int tmp = a[i];
a[i] = a[last];
a[last] = tmp;
}
}
}
last++;
int tmp = a[last];
a[last] = a[right];
a[right] = tmp;

quickSortHelper(a, left, last-1);
quickSortHelper(a, last+1, right);
}

private static long insertionSortTime(int n){

int[] a = randomArray(n);

long begin = System.nanoTime();

for (int i = 1; i < n; i++) {
int tmp = a[i];
for (int j = i-1; j >= 0; j--) {
if (a[j] > a[j+1]) a[j+1] = a[j];
else {
a[j+1] = tmp;
}
}
}

long end = System.nanoTime();

return end - begin;
}

private static int[] randomArray(int length){

int[] a = new int[length];

for (int i = 0; i < length; i++) {

a[i] = r.nextInt();
}

return a;

}
}

Dastur natijasi:



Tahlil:

Algoritm	Vaqt bo’yicha murakkablik	Elementlar soni	Saralash uchun ketgan vaqt (ns)
Shaker sort		450	7361889
		1800	29968799
		5500	70581620
Quick sort	O(n logn(n))	450	426670
		1800	2023383
		5500	6817189
Insertion sort		450	6828186
		1800	28385282
		5500	95606326

Diagrammadan shuni bilish mumkinki, yuqorida sanab o’tilga nalgoritmlari ichida “Quick sort” saralash usulida eng kam vaqt sarflanadi.

2-topshiriq:

Dastur kodi:
PriorityQueue.java:
package org.iksoft;

import java.util.Collections;

import java.util.LinkedList;
import java.util.List;

/**
* Created by IK
*/

public class PriorityQueue> {
private LinkedList items;

public PriorityQueue(){

items = new LinkedList<>();
}

public PriorityQueue(List items){

this();
this.items = new LinkedList<>(items);
Collections.sort(this.items);
}

public void offer(T item){

int n = size()-1;

while (items.get(n).compareTo(item) > 0){n--;}

items.add(n+1, item);
}

public T peek(){

return items.getFirst();
}

public T poll(){

T tmp = items.getFirst();
items.removeFirst();
return tmp;
}

public T peekLast(){

return items.getLast();
}

public T pollLast(){

T item = items.getLast();
items.removeLast();

return item;

}

public void clear(){

items.clear();
}

public int size(){ return items.size(); }

public boolean isEmpty() { return size() == 0;}

public void merge(PriorityQueue other){

items.addAll(other.items);
Collections.sort(items);
}

@Override

public String toString() { return items.toString(); }
}
Main.java:
package org.iksoft;

import java.util.Arrays;

public class Main {

public static void main(String[] args) {

Integer[] a = new Integer[]{5,4,6,-4};

PriorityQueue first = new PriorityQueue<>(Arrays.asList(a));

System.out.println("1-queue : " + first);
first.offer(0);
System.out.println("1-queue after adding 0 : " + first);
int n = first.pollLast();
System.out.println("Max element of queue : "+n);
System.out.println("1-queue after polling max number : "+first);

PriorityQueue second = new PriorityQueue<>(Arrays.asList(56,-8,7,-1));

System.out.println("2-queue : "+second);
first.merge(second);
System.out.println("1-queue after merging 2-queue : "+first);
}
}
Dastur natijasi: