algorithm
Unisci Ordina
Ricerca…
Unisci elementi di base di ordinamento
Unisci Ordina è un algoritmo divide et impera. Divide l'elenco di input della lunghezza n a metà in successione finché non ci sono n liste di dimensione 1. Quindi, le coppie di liste vengono unite insieme al primo elemento più piccolo tra la coppia di liste che vengono aggiunte in ogni passaggio. Attraverso la fusione e il confronto successivi dei primi elementi, viene costruita la lista ordinata.
Un esempio:
Complessità del tempo : T(n) = 2T(n/2) + Θ(n)
La ricorrenza di cui sopra può essere risolta usando il metodo Recurrence Tree o il metodo Master. Cade nel caso II del Metodo Master e la soluzione della ricorrenza è Θ(nLogn)
. La complessità temporale di Merge Sort è Θ(nLogn)
in tutti e 3 i casi ( peggiore, medio e migliore ) poiché l'ordinamento di merge divide sempre l'array in due parti e prende il tempo lineare per unire due metà.
Spazio ausiliario : O(n)
Paradigma algoritmico : Dividi e conquista
Ordinamento in atto : non in un'implementazione tipica
Stabile : sì
Unisci ordinamento di ordinamento in C #
C Unisci Ordina
int merge(int arr[],int l,int m,int h)
{
int arr1[10],arr2[10]; // Two temporary arrays to
hold the two arrays to be merged
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0; i<n1; i++)
arr1[i]=arr[l+i];
for(j=0; j<n2; j++)
arr2[j]=arr[m+j+1];
arr1[i]=9999; // To mark the end of each temporary array
arr2[j]=9999;
i=0;
j=0;
for(k=l; k<=h; k++) { //process of combining two sorted arrays
if(arr1[i]<=arr2[j])
arr[k]=arr1[i++];
else
arr[k]=arr2[j++];
}
return 0;
}
int merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high) {
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
// Combine
merge(arr,low,mid,high);
}
return 0;
}
C # Ordina unisci
public class MergeSort
{
static void Merge(int[] input, int l, int m, int r)
{
int i, j;
var n1 = m - l + 1;
var n2 = r - m;
var left = new int[n1];
var right = new int[n2];
for (i = 0; i < n1; i++)
{
left[i] = input[l + i];
}
for (j = 0; j < n2; j++)
{
right[j] = input[m + j + 1];
}
i = 0;
j = 0;
var k = l;
while (i < n1 && j < n2)
{
if (left[i] <= right[j])
{
input[k] = left[i];
i++;
}
else
{
input[k] = right[j];
j++;
}
k++;
}
while (i < n1)
{
input[k] = left[i];
i++;
k++;
}
while (j < n2)
{
input[k] = right[j];
j++;
k++;
}
}
static void SortMerge(int[] input, int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
SortMerge(input, l, m);
SortMerge(input, m + 1, r);
Merge(input, l, m, r);
}
}
public static int[] Main(int[] input)
{
SortMerge(input, 0, input.Length - 1);
return input;
}
}
Unisci ordinamento di ordinamento in Java
Di seguito c'è l'implementazione in Java usando un approccio generico. È lo stesso algoritmo, che è presentato sopra.
public interface InPlaceSort<T extends Comparable<T>> {
void sort(final T[] elements); }
public class MergeSort < T extends Comparable < T >> implements InPlaceSort < T > {
@Override
public void sort(T[] elements) {
T[] arr = (T[]) new Comparable[elements.length];
sort(elements, arr, 0, elements.length - 1);
}
// We check both our sides and then merge them
private void sort(T[] elements, T[] arr, int low, int high) {
if (low >= high) return;
int mid = low + (high - low) / 2;
sort(elements, arr, low, mid);
sort(elements, arr, mid + 1, high);
merge(elements, arr, low, high, mid);
}
private void merge(T[] a, T[] b, int low, int high, int mid) {
int i = low;
int j = mid + 1;
// We select the smallest element of the two. And then we put it into b
for (int k = low; k <= high; k++) {
if (i <= mid && j <= high) {
if (a[i].compareTo(a[j]) >= 0) {
b[k] = a[j++];
} else {
b[k] = a[i++];
}
} else if (j > high && i <= mid) {
b[k] = a[i++];
} else if (i > mid && j <= high) {
b[k] = a[j++];
}
}
for (int n = low; n <= high; n++) {
a[n] = b[n];
}}}
Unisci ordinamento di ordinamento in Python
def merge(X, Y):
" merge two sorted lists "
p1 = p2 = 0
out = []
while p1 < len(X) and p2 < len(Y):
if X[p1] < Y[p2]:
out.append(X[p1])
p1 += 1
else:
out.append(Y[p2])
p2 += 1
out += X[p1:] + Y[p2:]
return out
def mergeSort(A):
if len(A) <= 1:
return A
if len(A) == 2:
return sorted(A)
mid = len(A) / 2
return merge(mergeSort(A[:mid]), mergeSort(A[mid:]))
if __name__ == "__main__":
# Generate 20 random numbers and sort them
A = [randint(1, 100) for i in xrange(20)]
print mergeSort(A)
Implementazione Java bottom-up
public class MergeSortBU {
private static Integer[] array = { 4, 3, 1, 8, 9, 15, 20, 2, 5, 6, 30, 70, 60,80,0,9,67,54,51,52,24,54,7 };
public MergeSortBU() {
}
private static void merge(Comparable[] arrayToSort, Comparable[] aux, int lo,int mid, int hi) {
for (int index = 0; index < arrayToSort.length; index++) {
aux[index] = arrayToSort[index];
}
int i = lo;
int j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid)
arrayToSort[k] = aux[j++];
else if (j > hi)
arrayToSort[k] = aux[i++];
else if (isLess(aux[i], aux[j])) {
arrayToSort[k] = aux[i++];
} else {
arrayToSort[k] = aux[j++];
}
}
}
public static void sort(Comparable[] arrayToSort, Comparable[] aux, int lo, int hi) {
int N = arrayToSort.length;
for (int sz = 1; sz < N; sz = sz + sz) {
for (int low = 0; low < N; low = low + sz + sz) {
System.out.println("Size:"+ sz);
merge(arrayToSort, aux, low, low + sz -1 ,Math.min(low + sz + sz - 1, N - 1));
print(arrayToSort);
}
}
}
public static boolean isLess(Comparable a, Comparable b) {
return a.compareTo(b) <= 0;
}
private static void print(Comparable[] array) {http://stackoverflow.com/documentation/algorithm/5732/merge-sort#
StringBuffer buffer = new StringBuffer();http://stackoverflow.com/documentation/algorithm/5732/merge-sort#
for (Comparable value : array) {
buffer.append(value);
buffer.append(' ');
}
System.out.println(buffer);
}
public static void main(String[] args) {
Comparable[] aux = new Comparable[array.length];
print(array);
MergeSortBU.sort(array, aux, 0, array.length - 1);
}
}
Unisci ordinamento di ordinamento in Go
package main
import "fmt"
func mergeSort(a []int) []int {
if len(a) < 2 {
return a
}
m := (len(a)) / 2
f := mergeSort(a[:m])
s := mergeSort(a[m:])
return merge(f, s)
}
func merge(f []int, s []int) []int {
var i, j int
size := len(f) + len(s)
a := make([]int, size, size)
for z := 0; z < size; z++ {
lenF := len(f)
lenS := len(s)
if i > lenF-1 && j <= lenS-1 {
a[z] = s[j]
j++
} else if j > lenS-1 && i <= lenF-1 {
a[z] = f[i]
i++
} else if f[i] < s[j] {
a[z] = f[i]
i++
} else {
a[z] = s[j]
j++
}
}
return a
}
func main() {
a := []int{75, 12, 34, 45, 0, 123, 32, 56, 32, 99, 123, 11, 86, 33}
fmt.Println(a)
fmt.Println(mergeSort(a))
}