1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
|
#include <string>
#include <iostream>
using namespace std;
void display(char* A[], int size){
for (int i = 0; i <5; i++)
{
cout << A[i] << endl;
}
}
void swap(char* A[], int i, int j){
char* tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
int partition(char* A[], int low, int high){
int i = low;
int j = high;
int mid = (low + high) / 2;
char* pivot = A[mid];
swap(A, low, mid); //swaps the pivot into A[low]
while(i <= j)
{
//skip over elements <= the pivot
while (i <= high && A[i] <= pivot)
{
i++;
}
//skip over elements > the pivot
while(low <= j && pivot < A[j])
{
j--;
}
//swap values at i & j
if (i < j)
swap(A, i, j);
}
swap(A, low, j);
return j;
}
void QuickSort(char* A[], int low, int high){
if(low < high) // recursive case
{
int mid = partition(A, low, high);
QuickSort(A, low, mid-1);
QuickSort(A, mid+1, high);
}
}
int main()
{
int SIZE;
string wordToSort;
cin >> wordToSort;
SIZE = wordToSort.length();
char *suffixes[SIZE];
for(int index = 0; index < SIZE; index++)
{
suffixes[index] = &wordToSort[index];
}
QuickSort(suffixes, 0, SIZE);
display(suffixes, SIZE);
}
|