Бързо сортиране

от Уикипедия, свободната енциклопедия

Нагледно бързо сортиране на списък с числа. Главният елемент е в червено.

Бързо сортиране (от английското quick sort) е добре известен сортиращ алгоритъм, разработен от Ч. А. Р. Хоар през 1960 година. Основната част на алгоритъма се състои в сравняващо сортиране.

В най-лошия случай алгоритъмът има сложност O(n²). В средния случай алгоритъмът има сложност О(nlogn), а в амортизирания се правят 1.386nlogn сравнения.

[редактиране] Принцип на действие

1. Избира се "главен" елемент от списъка с елементи, които ще бъдат сортирани.
2. Списъкът се пренарежда така, че всички елементи, които са по-малки от "главния" се поставят вляво от него, а всички, които са по-големи - вдясно от него.
3. Рекурсивно се повтарят горните стъпки върху списъка с по-малките и списъка с по-големите елементи.
4. Получените списъци се сливат (конкатенация) и се получава сортираният списък.

[редактиране] Пример

[5 3 2 8 7 6 1 9 4]
За "главен" елемент избираме 5. Разделяме списъка на три части: елементи, по-малки от "главния", "главния", елементи, по-големи от главния.
[3 2 1 4] | [5] | [8 7 6 9]
Рекурсивно извършваме действията върху новополучените списъци.
[2 1] | [3] | [4] | [5] | [7 6] | [8] | [9]
[1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9]
Свързваме отделните списъци и получаваме сортирания списък.
[1 2 3 4 5 6 7 8 9]

[редактиране] Код на C++

#include <iostream>
using namespace std;

int a[10];
int partition(int left, int right);
void swap(int i, int j);
void sort(int i, int j);

int main()
{
	int i,j=0,k=9;
	for(i=0;i<10;i++)
	cin >> a[i];

	sort(j,k);
	for(i=0;i<10;i++)
	cout << a[i] << endl;
	return 0;
}

void sort(int left, int right)
{
	int p;
	if(left>=right)
	return;
	p = partition(left, right);

	sort(left,p-1);
	sort(p+1,right);
}

int partition(int left, int right)
{
	int first=left, pivot=right--;
	while(left<=right)
	{
		while(a[left]<a[pivot])
		left++;
		while((right>=first)&&(a[right]>=a[pivot]))
		right--;
		if(left<right)
		{
			swap(left,right);
			left++;
		}
	}
	if(left!=pivot)
	swap(left,pivot);

	return left;
}

void swap(int i, int j)
{
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}

[редактиране] Пример на Java за сортиране на числата 6, 9, 5, 3, 11, 7, 10

public class QuickSort {

    public QuickSort() {
        int[] array = new int[7];
        array[0] = 6;
        array[1] = 9;
        array[2] = 5;
        array[3] = 3;
        array[4] = 11;
        array[5] = 7;
        array[6] = 10;

        System.out.println("Elementite predi sortirane:");
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
             
        sort(array, 0 , array.length - 1);

        System.out.println("\nSortiraneto e izvarsheno!");
        System.out.println("\nElementite sled sortirane:");
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
    
    public void sort(int[] array, int l, int r) {
        
        if (l >= r) {
            return;
        }

        int i = l;
        int j = r;
        int p = array[r];
        
        while (i < j) {
            while (i < j && array[i] <= p) {
                i++;
            }

            while (i < j && array[j] >= p) {
                j--;
            }

            if (i < j) {
                int t =  array[i];
                array[i] = array[j];
                array[j] = t;
             
            }            
        }
        int t =  array[i];
        array[i] = array[r];
        array[r] = t;

        sort(array, l, i - 1);
        sort(array, i + 1, r);
    }

    
    public static void main(String[] args) {
        new QuickSort();
    }
    
}