hier is het snelle sorteeralgoritme van de MITOcw(Inleiding tot algoritmen) lezing
QUICKSORT(A,p,q)
if(p < q)
then r = PARTITION(A,p,q)
QUICKSORT(A,p,r-1)
QUICKSORT(A,r+1,q)
PARTITION(A,p,q)
x = A[p]
i=p
for j = p+1 to q
if A[j] <= x
then i = i+1
swap A[i] with A[j]
swap A[p] with A[i]
return i
en hier de C++implementatie op een integer array
#include <iostream>
using namespace std;
void quickSort(int *,int,int);
int partition(int *, int,int);
int main()
{
int A[10]={6,10,13,5,8,3,2,25,4,11};
int p=0,q=10;
cout<<"======Original======="<<endl;
for(int f=0; f<10; f++)
cout<<A[f]<<endl;
quickSort(A,p,q);
cout<<"======Sorted======="<<endl;
for(int f=0; f<10; f++)
cout<<A[f]<<endl;
}
void quickSort(int *A, int p,int q)
{
int r;
if(p<q)
{
r=partition(A, p,q);
quickSort(A,p,(r-1)); //I think the problem is here this first quickSort call
// is reducing the value of r and hence value of q becomes
// less than p recursively. How can I separate both calls
// one for left and one for right sub array of the pivot.
quickSort(A,(r+1),q);
}
}
int partition(int *A, int p,int q)
{
int x= A[p];
int i=p;
int temp;
int j;
for(j=p+1; j<q; j++)
{
if(A[j]<=x)
{
i=i+1;
temp= A[j];
A[j]=A[i];
A[i]=temp;
}
}
temp= A[p];
A[p]=A[i];
A[i]=temp;
return i;
}
Code levert geen gesorteerde array op, hoewel de eerste twee punten van quicksort -functie gewenste uitvoer geeft. Dat is het plaats het eerste draaipunt in de juiste positie
Antwoord 1, Autoriteit 100%
Uw overweging is verkeerd. De waarde van rverandert niet, aangezien deze wordt gegeven als waarde voor de QuickSort-functie (geen referentie).
U behandelt de reeksen met p, qzodanig dat pde eerste index is in het bereik en qde eerste Index niet in het bereik.
Dus, uw oproepen waren verkeerd:
r=partition(A, p,q);
quickSort(A,p,r); //range is from A[p] to A[r-1]
quickSort(A,(r+1),q); //range is from A[r+1] to A[q-1]
Hier is het compleet voorbeeld. Ik gebruikte std :: swap om elementen en
ans std :: vector in plaats van een array.
#include <iostream>
#include <vector>
using namespace std;
void quickSort(vector<int>&,int,int);
int partition(vector<int>&, int,int);
int main()
{
vector<int> A = {6,10,13,5,8,3,2,25,4,11};
int p=0;
int q=10;
cout<<"======Original======="<<endl;
for(auto e: A)
cout<< e <<" ";
cout<< endl;
quickSort(A,p,q);
cout<<"======Sorted======="<<endl;
for(auto e: A)
cout<< e <<" ";
cout<< endl;
}
void quickSort(vector<int>& A, int p,int q)
{
int r;
if(p<q)
{
r=partition(A, p,q);
quickSort(A,p,r);
quickSort(A,r+1,q);
}
}
int partition(vector<int>& A, int p,int q)
{
int x= A[p];
int i=p;
int j;
for(j=p+1; j<q; j++)
{
if(A[j]<=x)
{
i=i+1;
swap(A[i],A[j]);
}
}
swap(A[i],A[p]);
return i;
}
Live voorbeeld: ideone
Antwoord 2, autoriteit 6%
Dit is een op sjablonen gebaseerde oplossing. Het werkt echter voorlopig alleen voor arrays van elementen. Als iemand een verbetering heeft om het generiek te maken voor zowel arrays als STL-containers, doe dat dan alsjeblieft.
template<typename T, typename compare = std::less<T>>
void q_sort(T input[], int l_idx, int r_idx, compare comp = compare()) {
if (l_idx >= r_idx)
return;
// The below is the partition block (can be made a sub function)
int left = l_idx;
int right = r_idx;
{
int pivot_idx = l_idx;
T pivot = input[pivot_idx];
while (left < right) {
while (comp(input[left], pivot))
left++;
while (comp(pivot, input[right]))
right--;
swap(input[left], input[right]);
}
swap(pivot, input[left]);
}
q_sort(input, l_idx, left, comp);
q_sort(input, left+1, r_idx, comp);
}
template<typename T, typename compare = std::less<T>>
void quick_sort(T array[], int N, compare comp = compare()) {
// This is an improvisation on the merge sort algorithm
// is in-place and works on the divide-and-conquer methodology
// Choose a pivot and find its appropriate place, such that
// All elements less than the pivot are on its left and all elements
// greater are on its right. Once found, split the porlblem into subsets
// of elements less than and greater than the pivot and recursively
// follow the process.
q_sort(array, 0, N-1, comp);
}
int main()
{
int input[] = {11, 6, 3, 21, 9, 12};
std::cout << "Before : ";
for (int i=0; i < 6; i++)
std::cout << input[i] << " ";
std::cout << std::endl;
quick_sort(input, 6);
// or
//quick_sort(input, 6, std::greater<int>());
std::cout << "After : ";
for (int i=0; i < 6; i++)
std::cout << input[i] << " ";
std::cout << std::endl;
}
Antwoord 3
Een veel eenvoudigere en schonere implementatie, geeft je ook het aantal minimale SWAPS in voor QuickSort:
int quickSort(int[], int, int);
int partition(int[], int, int, int&);
int main()
{
int array[] = {4, 2, 5};
int size = sizeof(array)/sizeof(array[0]);
/*
first and last indices are passed
idea is to move lower elements to the left of the list/pivot
*/
int swaps = quickSort(array, 0, size-1);
std::cout << "Minimum Swaps are: " << swaps << std::endl;
for(int i = 0; i < size; i++)
{
std::cout << array[i] << " ";
}
}
int quickSort(int array[], int start, int end)
{
int swaps = 0;
if(start < end)
{
int pIndex = partition(array, start, end, swaps);
//after each call one number(the PIVOT) will be at its final position
swaps += quickSort(array, start, pIndex-1);
swaps += quickSort(array, pIndex+1, end);
}
return swaps;
}
int partition(int array[], int start, int end, int& swaps)
{
int pivot = array[end];
int pIndex = start;
for(int i = start; i < end; i++)
{
if(array[i] <= pivot)
{
if(pIndex != i)
{
std::swap(array[i], array[pIndex]);
swaps++;
}
pIndex++;
}
}
if(pIndex != end)
{
std::swap(array[pIndex], array[end]);
swaps++;
}
return pIndex;
}
Antwoord 4
Aangezien ik verschillende antwoorden zie, kun je dit proberen:
#include <iostream>
void quickSort(int a[], int first, int last);
int pivot(int a[], int first, int last);
void swap(int& a, int& b);
void swapNoTemp(int& a, int& b);
void print(int array[], const int& N);
using namespace std;
int main()
{
int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
int N = sizeof(test)/sizeof(int);
cout << "Size of test array :" << N << endl;
cout << "Before sorting : " << endl;
print(test, N);
quickSort(test, 0, N-1);
cout << endl << endl << "After sorting : " << endl;
print(test, N);
return 0;
}
/**
* Quicksort.
* @param a - The array to be sorted.
* @param first - The start of the sequence to be sorted.
* @param last - The end of the sequence to be sorted.
*/
void quickSort( int a[], int first, int last )
{
int pivotElement;
if(first < last)
{
pivotElement = pivot(a, first, last);
quickSort(a, first, pivotElement-1);
quickSort(a, pivotElement+1, last);
}
}
/**
* Find and return the index of pivot element.
* @param a - The array.
* @param first - The start of the sequence.
* @param last - The end of the sequence.
* @return - the pivot element
*/
int pivot(int a[], int first, int last)
{
int p = first;
int pivotElement = a[first];
for(int i = first+1 ; i <= last ; i++)
{
/* If you want to sort the list in the other order, change "<=" to ">" */
if(a[i] <= pivotElement)
{
p++;
swap(a[i], a[p]);
}
}
swap(a[p], a[first]);
return p;
}
Ik heb het in quicksort (C++) .