Programmieren lernen

package ch.programmieraufgaben.rekursion.quicksort;

import java.util.Arrays;

/**
 * www.programmieraufgaben.ch
 * 
 * @author Philipp Gressly (phi AT gressly DOT ch)
 */
public class Quicksort {
    
    int[] zahlen = { 4, 9, 1, 55, 8, 9, 7, 3, 1, 6, 8, 2, 3, 8 };

    public static void main(String[] args) {
        new Quicksort().top();
    }

    void top() {
        sortRekursiv(0, zahlen.length - 1);
        ausgabe();
    }


     void ausgabe() {
        System.out.println(Arrays.toString(zahlen));
    }

    int nrOfElements(int left, int right) {
        return right - left + 1;
    }

    void tausche(int pos1, int pos2) {
        int val = zahlen[pos1];
        zahlen[pos1] = zahlen[pos2];
        zahlen[pos2] = val;
    }

    void sortRekursiv(int left, int right) {
        if (nrOfElements(left, right) < 3) {
            if (zahlen[left] > zahlen[right]) {
                tausche(left, right);
            }
            return;
        }
        int pivot = pivotBestimmen(left, right);
        int pivotPos = partitionieren(left, right, pivot);
        if (left < pivotPos - 1) {
            sortRekursiv(left, pivotPos - 1);
        }
        if (right > pivotPos + 1) {
            sortRekursiv(pivotPos + 1, right);
        }

    }

    /**
     * <= pivot -> Links > pivot -> Rechts
     */
    int partitionieren(int left, int right, int pivot) {
        int pivotPos = getPivotPos(left, right, pivot);
        while (left < right) {
            if (left < pivotPos && zahlen[left] <= pivot) {
                left++;
            } else if (right > pivotPos && zahlen[right] > pivot) {
                right--;
            } else if (left < pivotPos && zahlen[left] > pivot) {
                tausche(pivotPos, left);
                pivotPos = left;
            } else if (right > pivotPos && zahlen[right] <= pivot) {
                tausche(pivotPos, right);
                pivotPos = right;
            }
        }
        return pivotPos;
    }

    int getPivotPos(int left, int right, int pivot) {
        int pos = left;
        while (pos <= right) {
            if (zahlen[pos] == pivot) {
                return pos;
            }
            pos++;
        }
        System.out.println("Error in get Pivot Pos!");
        System.exit(0);
        return 0;
    }

    int pivotBestimmen(int left, int right) {
        int[] val = new int[3];
        int found = 0;
        double zaehler = 3.0;
        int nenner = nrOfElements(left, right);
        int pos = left;

        // 3 zufällige auswählen
        while (pos <= right && found < 3) {
            // die Wahrscheinlichkeit zur Auswahl eines Elementes
            // wächst mit jeder Zahl, die nicht ausgewählt wurde.
            if (Math.random() < zaehler / nenner) {
                val[found] = zahlen[pos];
                found = found + 1;
                zaehler = zaehler - 1;
            }
            nenner = nenner - 1;
            pos = pos + 1;
        }

        if (val[0] <= val[1] && val[1] <= val[2])
            return val[1];
        if (val[2] <= val[1] && val[1] <= val[0])
            return val[1];
        if (val[1] <= val[0] && val[0] <= val[2])
            return val[0];
        if (val[2] <= val[0] && val[0] <= val[1])
            return val[0];

        return val[2];
    }

} // end of class Quicksort
                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#define SWAP(a, b, type) {type tmp = a; a = b; b = tmp;}


int getMedian(int *val, int l, int r) {
	srand(time(NULL));
	int a, b, c;
	a = (rand() % (r + 1 - l)) + l;
	b = (rand() % (r + 1 - l)) + l;
	c = (rand() % (r + 1 - l)) + l;

	if (val[a] > val[b])
		SWAP(a, b, int);
	if (val[a] > val[c])
		SWAP(a, c, int);
	if (val[b] > val[c])
		SWAP(b, c, int);

	return b;
}

void quickSort(int *a, int l, int r) {
	int j;

	if (l < r) {
		// divide and conquer
		j = partition(a, l, r);
		quickSort(a, l, j - 1);
		quickSort(a, j + 1, r);
	}

}

int partition(int *a, int l, int r) {
	int pivot, i, j, t;

	SWAP(a[l], a[getMedian(a, l, r)], int);

	pivot = a[l];
	i = l;
	j = r + 1;

	while (1) {
		do
			++i;
		while (a[i] <= pivot && i <= r);
		do
			--j;
		while (a[j] > pivot);
		if (i >= j)
			break;
		t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	t = a[l];
	a[l] = a[j];
	a[j] = t;
	return j;
}

void printList(int valNum, int *val) {
	for (int i = 0; i < valNum; i++)
		printf("%d ", val[i]);
	printf("\n");
}

int main(int argc, char **argv) {

	int x[] = { 87, 16, 204, 1, 9, 200, 99, 18 };

	printf("Unsortierte Liste: ");
	printList(8, x);
	quickSort(x, 0, 7);
	printf("Sortierte Liste: ");
	printList(8, x);
}

                

Lösung von: André Trobisch ()