Quick Sort algoritme

Prøv at følge koden her:

public class Sort {
    private static String arrayToString(int args[], int start, int length) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < length; i++) {
            if (i > 0) {
                builder.append(", ");
            }
            builder.append(args[start + i]);
        }
        return builder.toString();
    }

    private static void swap(int elements[], int first, int second) {
        System.out.println("Swapping element " + first + " and " + second);
        int temp = elements[first];
        elements[first] = elements[second];
        elements[second] = temp;
    }

    private static void quickSort(int elements[], int first, int last) {
        System.out.println("Quick sorting this list of elements (index " + first + " to " + last + "): " + arrayToString(elements, first, last - first + 1));
        int i = first + 1, j = last, pivotIndex = (first + last) / 2;

        if (first < last) {
            swap(elements, first, pivotIndex);//Put pivot at first index

            while (i <= j) {
                //Find first on left side of pivot which is greater than the piov
                while (i <= j && elements[i] <= elements[first])i++;
                //Find last on the right side of pivot which is smaller than pivot
                while (i <= j && elements[j] >= elements[first])j--;
                if (i < j) {
                    //Swap them
                    swap(elements, i, j);
                }
            }
            //Put pivot back where it belongs
            swap(elements, first, j);
            //Now the pivot is in the correct place (index 'j')
            //so sort the lower part of the elements...
            quickSort(elements, first, j - 1);
            //...and then the higher part
            quickSort(elements, j + 1, last);

            System.out.println("Now these should be sorted (index " + first + " to " + last + "): " + arrayToString(elements, first, last - first + 1));
        }
    }

    private static void sort(int elements[]) {
        quickSort(elements, 0, elements.length - 1);
    }

    public static void main(String args[]) {
        //Make list of random integers
        int elements[] = new int[10];
        for (int i = 0; i < elements.length; i++) {
            elements[i] = (int)Math.abs(Math.random() * 100);
        }
        System.out.println("Elements at start: " + arrayToString(elements, 0, elements.length));

        sort(elements);

        System.out.println("Elements after sort: " + arrayToString(elements, 0, elements.length));
    }
}

Du kan ændre størrelse på arrayet i main metoden.

Quicksort sorterer ved at tage alle elementer, som er større end et test tal (pivot) og sætte dem på højre side, og alle tal som er mindre end og sætte dem på venstre side af tallet. Når det er gjort, står pivot tallet korrekt. Så gør man det samme med venstre side (altså de tal som er mindre end pivot tallet), og derefter med højre side. Det bliver man ved med indtil man står med en tom liste.
Min 'if (first < last)' gør, at algoritmen stopper, når den ville have sorteret en tom liste, eller en liste på et element.

Her er en algoritme som er skrevet af Herbert Schildt, en mand som har været med til at sætte ansi/iso standarden for c++...

Synes selv denne stump kode er lidt lettere fordøjelig end Robert Larsens eksempel...

Og det er absolut ingen kritik da jeg sev er meget ny her og til C++ syntes bare lige jeg ville vise hvordan det også kan gøres.

Jeg har tilføjet en smule kode som giver et hjælpe print på skærmen så man kan se hvad der egentlig sker med strengen(char array) løbende.

/*
		QuickSort - Visual C++ 2008 Express Solution
		
		Example from "C++ Beginner's Guide" by Herbert Schildt

		Rewritten by Kent S. Olsen 2008 in part of self-educational use

		This program:	Show QuickSort algorithm using recursive function
*/

#include <iostream>
using namespace std;

#include <cstring>

int COUNTER = 0;
int MINOR = 1;

void quicksort (char *items, int len);	// Interface function
void qs(char *items, int left, int right);

int main (int argc, char *argv[])
{
	char str[] = "QW1ER2TY5UI6OP7LK3JH8GFD9SA4ZX0CVBNM";
	//char str[] = "QWERTYUIOPLKJHGFDSAZXCVBNM";
	//char str[] = "JEGFYRTHSMNXZAOQ";
	//char str[] = "FAEBDC";
	//char str[] = "JSUEHSLKJABEJS";
	//char str[] = "KENT STARK OLSEN";
	//char str[] = "E";
	//char str[] = "";

	cout << "Original order: " << str << "\n\nSorting.....\t\t(Lenght: " << strlen(str) << ")\n\n";

	quicksort(str, strlen(str));

	cout << "\n  Sorted order: " << str << "\n\n";

	system("pause");

	return(0);
}

void quicksort (char *items, int len)
{
	qs(items, 0, len-1);
}

void qs(char *items, const int left, const int right)
{
	COUNTER++;
	cout << "(" << COUNTER << ")\t" << items << '\n' << endl;		// Help output
	MINOR = 1;

	int i, j;
	char x, y;

	i = left; j = right;
	x = items[(left + right) / 2];

	do {
		while((items[i] < x) && (i < right)) i++;
		while((x < items[j]) && (left < j)) j--;

		if (i <= j) {
			y = items[i];
			items[i] = items[j];
			items[j] = y;
			i++; j--;

			cout << "(" << COUNTER << "." << MINOR << ")\t\t" << items << '\n';		// Help output
			MINOR++;

		}
	} while (i <= j);

	cout << endl;

	if (left < j) qs(items, left, j);
	if (i < right) qs(items, i, right);
}

Håber det kan bruges... God fornøjelse