Pages: [1]   Go Down
Print
Author Topic: Merge e Quick Sort  (Read 554 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
milos224
Forumista
***
Offline Offline

Posts: 830


« on: 02-10-2011, 23:59:34 »

Sto avendo grossi problemi con questi due tipi di ordinamenti. Qualcuno che puó postare il codice di questi due algoritmi, applicati ad un semplice array? Grazie mille!
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #1 on: 03-10-2011, 10:34:51 »

Qui trovi il codice del merge e quick applicati ad un array..
Code:
public void mergeSort( E [ ] a ) {
        E [ ] tmpArray = (E [])new Integer[ a.length ];
        mergeSort( a, tmpArray, 0, a.length - 1 );
    }

    /**
     * Internal method that makes recursive calls.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param left the left-most index of the subarray.
     * @param right the right-most index of the subarray.
     */
    private  void mergeSort( E [ ] a, E [ ] tmpArray,
            int left, int right ) {
        if( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort( a, tmpArray, left, center );
            mergeSort( a, tmpArray, center + 1, right );
            merge( a, tmpArray, left, center + 1, right );
        }
    }

    /**
     * Internal method that merges two sorted halves of a subarray.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param leftPos the left-most index of the subarray.
     * @param rightPos the index of the start of the second half.
     * @param rightEnd the right-most index of the subarray.
     */
    private  void merge( E [ ] a, E [ ] tmpArray,
            int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        // Main loop
        while( leftPos <= leftEnd && rightPos <= rightEnd )
            if( a[ leftPos ].compareTo(a[rightPos])<= 0)
                tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            else
                tmpArray[ tmpPos++ ] = a[ rightPos++ ];

        while( leftPos <= leftEnd )    // Copy rest of first half
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];

        while( rightPos <= rightEnd )  // Copy rest of right half
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];

        // Copy tmpArray back
        for( int i = 0; i < numElements; i++, rightEnd-- )
            a[ rightEnd ] = tmpArray[ rightEnd ];
    }

public void quickSort(E[]a){
        if(a==null || a.length==0) return;
        quickSort(a,0,a.length-1);
    }
    public void quickSort(E[]a, int low,int high){
        int i=low, j=high;
        E pivot=a[low+(high-low)/2];
        while(i<=j){
            while(a[i].compareTo(pivot)<0)
                i++;
            while(a[j].compareTo(pivot)>0)
                j--;
            if(i<=j){
                E tmp=a[i];
                a[i]=a[j];
                a[j]=tmp;
                i++;
                j--;
            }
        }
        if(low<j)
            quickSort(a,low,j);
        if(i<high)
            quickSort(a,i,high);
    }
}

Basta levare i tipi generici ed inserire un array di interi ed il gioco è fatto.
 ciao
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #2 on: 03-10-2011, 12:36:12 »

Qui trovi il codice del merge e quick applicati ad un array..
Code:
public void mergeSort( E [ ] a ) {
        E [ ] tmpArray = (E [])new Integer[ a.length ];
        mergeSort( a, tmpArray, 0, a.length - 1 );
    }

    /**
     * Internal method that makes recursive calls.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param left the left-most index of the subarray.
     * @param right the right-most index of the subarray.
     */
    private  void mergeSort( E [ ] a, E [ ] tmpArray,
            int left, int right ) {
        if( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort( a, tmpArray, left, center );
            mergeSort( a, tmpArray, center + 1, right );
            merge( a, tmpArray, left, center + 1, right );
        }
    }

    /**
     * Internal method that merges two sorted halves of a subarray.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param leftPos the left-most index of the subarray.
     * @param rightPos the index of the start of the second half.
     * @param rightEnd the right-most index of the subarray.
     */
    private  void merge( E [ ] a, E [ ] tmpArray,
            int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        // Main loop
        while( leftPos <= leftEnd && rightPos <= rightEnd )
            if( a[ leftPos ].compareTo(a[rightPos])<= 0)
                tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            else
                tmpArray[ tmpPos++ ] = a[ rightPos++ ];

        while( leftPos <= leftEnd )    // Copy rest of first half
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];

        while( rightPos <= rightEnd )  // Copy rest of right half
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];

        // Copy tmpArray back
        for( int i = 0; i < numElements; i++, rightEnd-- )
            a[ rightEnd ] = tmpArray[ rightEnd ];
    }

public void quickSort(E[]a){
        if(a==null || a.length==0) return;
        quickSort(a,0,a.length-1);
    }
    public void quickSort(E[]a, int low,int high){
        int i=low, j=high;
        E pivot=a[low+(high-low)/2];
        while(i<=j){
            while(a[i].compareTo(pivot)<0)
                i++;
            while(a[j].compareTo(pivot)>0)
                j--;
            if(i<=j){
                E tmp=a[i];
                a[i]=a[j];
                a[j]=tmp;
                i++;
                j--;
            }
        }
        if(low<j)
            quickSort(a,low,j);
        if(i<high)
            quickSort(a,i,high);
    }
}

Basta levare i tipi generici ed inserire un array di interi ed il gioco è fatto.
 ciao

Grazie davvero!
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #3 on: 09-10-2011, 11:13:05 »

Scusa non riesco a creare un main per testare, potresti aiutarmi tu?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: