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:
Do'stlaringiz bilan baham: |