Created
March 15, 2013 17:43
-
-
Save unsign3d/5171668 to your computer and use it in GitHub Desktop.
recursive merge sort in java, just for study
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
public class MergeSort{ | |
public static void main(String[] args) { | |
int a[]= { 5, 7, 2, 8, 11, 34, 2, 0, 7}; | |
System.out.println("Prima: "+Arrays.toString(a)+"\n"); | |
merge_sort(a); | |
System.out.println("Dopo: "+Arrays.toString(a)); | |
} | |
public static void merge_sort(int[] a, int[] b, int left, int right){ | |
int mid; | |
if(left < right){ | |
//trovo la meta' | |
mid = (left + right) / 2; | |
//applico la ricorsione e spezzo in 2 l'array | |
merge_sort(a, b, left, mid); | |
merge_sort(a, b, mid+1, right); | |
//rimetto assieme gli array | |
merge(a, b, left, mid+1, right); | |
} | |
} | |
public static void merge_sort(int[] a){ | |
int[] b = new int[a.length]; | |
merge_sort(a, b, 0, a.length -1); | |
} | |
public static void merge(int a[], int b[], int left, int center, int right){ | |
int end1 = center -1; //indice di dove finisce il primo array | |
int j = left; //da dove parto con b | |
int n = right - left + 1; //numero di elementi | |
//scansione array | |
while(left <= end1 && center <= right){ | |
//copio il minore nella prima posizione libera di b | |
if(a[left] <= a[center]){ | |
b[j++] = a[left++]; | |
} else { | |
b[j++] = a[center++]; | |
} | |
} | |
//fondo la prima parte | |
while(left <= end1 ){ | |
b[j++] = a[left++]; | |
} | |
while(center <= right){ | |
b[j++] = a[center++]; | |
} | |
//copio l'array | |
for (int i= 0; i < n; i++, right--){ | |
a[right] = b[right]; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment