Изменение этого Quicksort всегда использовать последний элемент как стержень

Question

У меня есть следующая Быстрая сортировка , которая всегда выбирает первый элемент подпоследовательности в качестве своей оси:

void qqsort(int array[], int start, int end) {
    int i = start; // index of left-to-right scan
    int k = end; // index of right-to-left scan

    if (end - start >= 1) { // check that there are at least two elements to sort 
        int pivot = array[start]; // set the pivot as the first element in the partition
        while (k > i) { // while the scan indices from left and right have not met, 
            while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first element greater than the pivot
                i++;
            while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first element not greater than the pivot
                k--;
            if (k > i) // if the left seekindex is still smaller than the right index, swap the corresponding elements
                swap(array, i, k);              
        }
        swap(array, start, k); // after the indices have crossed, swap the last element in the left partition with the pivot 
        qqsort(array, start, k - 1); // quicksort the left partition
        qqsort(array, k + 1, end); // quicksort the right partition
    } else { // if there is only one element in the partition, do not do any sorting 
        return;
    }
}

Теперь, как вы можете видеть, этот алгоритм всегда принимает первый элемент, чтобы быть осью: int pivot = array[start];

Я хочу изменить этот алгоритм, чтобы он всегда использовал последний элемент вместо первого элемента подпоследовательности, потому что я хочу проанализировать физическое время выполнения обеих реализаций.

Я попытался изменить строку int pivot = array[start]; на int pivot = array[end];, но алгоритм затем вывел несортированную последовательность:

//Changes: int pivot = array[end]; 
unsorted: {5 4 3 2 1}
*sorted*: {1 2 5 4 3}

Чтобы проверить еще одну опорную точку, я также попытался использовать центральный элемент подпоследовательности, но алгоритм все еще не удался:

//Changes: int pivot = array[(start + end) / 2]; 
unsorted: {5 3 4 2 1}
*sorted*: {3 2 4 1 5}

---

Может кто-то пожалуйста, помогите мне понять этот алгоритм правильно и сказать мне, какие изменения мне нужно сделать, чтобы успешно иметь эту реализацию всегда выбирает последний элемент подпоследовательности в качестве опоры?

Answer 1

причина проблемы

Проблема в том, что вы используете int k = end;. Было бы хорошо использовать int i = start;, когда в качестве первого элемента в массиве был элемент pivot, потому что ваши проверки в цикле пропустят его (array[i] <= pivot). Однако, когда вы используете последний элемент в качестве оси, k останавливается на конце индекса и переключает точку в левую половину раздела. У вас уже есть неприятности, потому что ваш стержень, скорее всего, будет где-то внутри левого раздела, а не на границе.

Решение

Чтобы это исправить, вам нужно установить int k = end - 1;, когда вы используете крайний правый элемент в качестве оси. Вам также понадобится изменить линии для перестановки оси на границу между левым и правым разделами:

swap(array, i, end);
qqsort(array, start, i - 1);
qqsort(array, i + 1, end);

Вы должны использовать i для этого, потому что я окажусь в крайнем левом элементе правого раздела (который затем можно поменять местами с поворотной точкой в ​​крайнем правом элементе, и это сохранит порядок). Наконец, вы захотите изменить k >= i на k > i в то время, когда значение k уменьшается, иначе происходит небольшое изменение ошибки индексации массива [-1]. Это было невозможно сделать раньше, потому что к этому моменту я всегда был равен i + 1.

Это должно сделать это.

Sidenote:

Это плохо написанная быстрая сортировка, из которой я бы не рекомендовал учиться. В нем есть несколько посторонних, ненужных сравнений, а также некоторые другие недостатки, которые я не буду тратить впустую. Я бы рекомендовал использовать быстрые сортировки в этой презентации Седжвиком и Бентли.

Answer 2

Я не проверял, но все равно проверял:

это

// after the indices have crossed,
// swap the last element in the left partition with the pivot
swap(array, start, k);

вероятно должно быть

swap(array, end, i);

или что-то подобное, если мы выберем end в качестве точки разворота.

Редактировать: Это интересный алгоритм разбиения, но он не стандартный .

Ну, а pivot фиксируется в логике разбиения.
Алгоритм обрабатывает первый элемент как заголовок, а остальные элементы как тело, подлежащее разделению.
После того, как разделение выполнено, в качестве последнего шага, голова (шарнир) заменяется элементом last левой разделенной части, чтобы сохранить порядок.

Единственный способ, с помощью которого я решил использовать другую опору без изменения алгоритма, это:

...
if (end - start >= 1) {
    // Swap the 1st element (Head) with the pivot
    swap(array, start, pivot_index);
    int pivot = array[start];
...

Answer 3

Первый совет: если данные случайные, в среднем не имеет значения, какое значение вы выбираете в качестве сводного. Единственный способ реально улучшить «качество» сводной точки - это взять больше (например, 3) индексов и использовать индекс со средним значением.

Второй совет: если вы изменяете значение сводки, вам также нужно изменить индекс сводки. Это не названо явно, но array[start] поменяется на «середину» отсортированной подпоследовательности в одной точке. Вы должны изменить эту строку соответственно. Если вы берете индекс, который не находится на краю подпоследовательности, вам нужно сначала поменять его на край, перед итерацией.

Третий совет: предоставленный вами код чрезмерно прокомментирован. Вы должны быть в состоянии действительно понять эту реализацию.

Answer 4

Если вы начнете следить за каждым элементом от 1-го элемента массива до последнего - 1, сохраняя последний элемент как опорный элемент при каждой рекурсии, то вы получите точный ответ O (nlogn) время.

#include<stdio.h>
void quicksort(int [], int, int);
int main()
{
int n, i = 0, a[20];
scanf("%d", &n);
while(i < n)
scanf("%d", &a[i++]);

quicksort(a, 0, n - 1);
i = 0;
while(i < n)
printf("%d", a[i++]);

}
void quicksort(int a[], int p, int r)
{
int i, j, x, temp;
if(p < r)
{
    i = p;
    x = a[r];
    for(j = p; j < r; j++)
    {
        if(a[j] <= x)
        {
            if(a[j] <a[i])
            {
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
            i++;
        }

        else
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    if(x != i)
    {
        temp = a[r];
        a[r] = a[i];
        a[i] = temp;
    }

    quicksort(a, p, i - 1);
    quicksort(a, i + 1, r);
}
}

Answer 5

#include <time.h>
#include <stdlib.h>
#include<iostream>
#include<fstream>
using namespace std;

int counter=0;
void disp(int *a,int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}

void swap(int a[],int p,int q)
{

int temp;
temp=a[p];
a[p]=a[q];
a[q]=temp;

}

int partition(int a[], int p, int start, int end)
{
swap(a,p,start);// to swap the pivot with the first element of the partition
counter+=end-start;  // instead of (end-start+1)
int i=start+1;
for(int j=start+1 ; j<=end ; j++)
{
    if(a[j]<a[start])
    {
        swap(a,j,i);
        i++;

    }


}
swap(a,start,i-1);  // not swap(a,p,i-1) because p and start were already swaped.....    this was the earlier mistake comitted
return i-1; // returning the adress of pivot
}

void quicksort(int a[],int start,int end)
{
if(start>=end)
    return;


int p=end; // here we are choosing last element of the sub array as pivot
// here p is the index of the array where pivot is chosen randomly

int index=partition(a,p,start,end);

quicksort(a,start,index-1);
quicksort(a,index+1,end);

}

int main()
{

ifstream fin("data.txt");
int count=0;

int array[100000];

while(fin>>array[count])
{
    count++;
}
quicksort(array,0,count-1);
/*
int a[]={32,56,34,45,23,54,78};
int n=sizeof(a)/sizeof(int);
disp(a,n);

quicksort(a,0,n-1);
disp(a,n);*/
cout<<endl<<counter;
return 0;

}

Answer 6

Положите один

swap(array, start, end)

до инициализации пивота

int pivot = array[start]