|
Amaliy mashg‘ulot 6 Mavzu
|
| bet | 6/6 | | Sana | 23.05.2024 | | Hajmi | 441,98 Kb. | | #251388 |
Bog'liq 2-dedline uchun shablonpublic class MergeSort {
public static void main(String[] args) {
int[] A = {6,5,12,10,9,1};
sort(A); //saralashni boshlash
System.out.println(Arrays.toString(A)); //natijani chop qilish
}
private static void sort(int[] array) {
if(array.length<=1){ //massiv qismlarini elementlar sonin aniqlash
return; //1 dan kichik yoki teng bo`lsa ajratishni to`xtatish
}
int leftSize = array.length/2; //chap tomon bo`lak uzunligini aniqlash
int rightSize = array.length-leftSize; //o`ng tomon bo`lak uzunligini aniqlash
int[] left = Arrays.copyOfRange(array, 0, leftSize); //mos ravishda o`ng va chap
int[] right = Arrays.copyOfRange(array, leftSize, leftSize+rightSize); //submassivlarga ajratish
sort(left); //rekursiya orqali
sort(right); //bo`laklarga ajratish
merge(array, left, right); //to`g`ri tartibda birlashtirish
}
private static void merge(int[] array, int[] left, int[] right) {
int leftIndex = 0; //left va right submassiv elementlarini
int rightIndex = 0; //to`g`ri saralangan tartibda
int targetIndex = 0; //array massiviga joylashtirsh
int remaining = left.length+right.length;
while(remaining>0){
if (leftIndex >= left.length){
array[targetIndex] = right[rightIndex++];
}else
if (rightIndex >= right.length){
array[targetIndex] = left[leftIndex++];
}else
if (left[leftIndex]-right[rightIndex] < 0){
array[targetIndex] = left[leftIndex++];
}else{
array[targetIndex] = right[rightIndex++];
}
targetIndex++;
remaining--;
}
}
}
Qadamlarda tasvirlanishi:
Aytib o`tish joizki, chiziqli saralash algoritmlaridan farqli o`laroq, birlashmali saralash massiv avvaldan saralangan yoki saralanmaganligiga qaramay ajratib birlashtiradi. Shuning uchun ham eng yomon holatda, u chiziqli saralash algoritmlariga qaraganda tez ishlashiga qaramay, eng yaxshi holatda uning samarasi chiziqli algoritmlardan past bo`ladi. Demak, birlashmali saralashni qisman saralangan massivlarni saralash uchun qo`llamagan ma'qul.
Birlashmali saralashning boshqa saralash algoritmlari bilan solishtirish:
Algoritm Eng yaxshi O`rtacha Engyomon
Tanlab saralash O(n^2) O(n^2) O(n^2)
Pufakchali saralash O(n) O(n^2) O(n^2)
Tezkor saralash O(n log(n)) O(n log(n)) O(n^2)
Birlashmali saralash O(n log(n)) O(n log(n)) O(n log(n))
Jadvaldan ko`rinib turibdiki, umumiy holatda birlashmali saralash algoritmidan foydalanish samaraliroq hisoblanadi.
|
| |
