Глядя на сортировки - Быстрая сортировка Итеративный?

Question

Я смотрю на все виды.Обратите внимание, что это не домашняя работа (я нахожусь в финале), я просто хочу быть готовым, если такие вещи появятсяЯ не смог найти надежный метод выполнения быстрой сортировки итеративно.Возможно ли это, и если да, то как?

Answer 1

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

Возможно ли это, и если да, то как?

Давайте сначала посмотрим, что можно понять, создав рекурсивный алгоритм итеративный .

Например, мы хотим иметь некоторую функцию sum(n), которая суммирует числа от 0 до n.

Конечно, это

sum(n) = 
  if n = 0
    then return 0
    else return n + sum(n - 1)

Когда мы попытаемся вычислить что-то вроде sum(100000), мы скоро увидим, что у этого рекурсивного алгоритма есть свои ограничения - произойдет переполнение стека.

Итак, в качестве решения мы используем итерационный алгоритм для решения той же проблемы.

sum(n) =
   s <- 0
   for i in 0..n do
     s <- s + i
   return s

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

Это первый аспект создания итеративного алгоритма: поиск другого итеративного алгоритма, который решает ту же проблему.

В некоторых случаях такой итеративной версии может просто не быть.

второй однако применим к каждому рекурсивному алгоритму . Вы можете превратить любую рекурсию в итерацию путем явного представления стека, который рекурсия использует неявно . Теперь этот алгоритм будет иметь те же характеристики, что и исходный, - и стек будет расти с O(n), как в рекурсивной версии. Это не так легко переполнится, поскольку он использует обычную память вместо стека вызовов и итеративный, но это все тот же алгоритм.

Что касается быстрой сортировки: не существует другой формулировки, которая работает без хранения данных, необходимых для рекурсии. Но, конечно, вы можете использовать для них явный стек, как показал Эхсан. Таким образом, вы можете - как всегда - создать итерационную версию.

Answer 2

#include <stdio.h>
#include <conio.h>

#define MAXELT          100
#define INFINITY        32760         // numbers in list should not exceed
                                      // this. change the value to suit your
                                      // needs
#define SMALLSIZE       10            // not less than 3
#define STACKSIZE       100           // should be ceiling(lg(MAXSIZE)+1)

int list[MAXELT+1];                   // one extra, to hold INFINITY

struct {                              // stack element.
        int a,b;
} stack[STACKSIZE];

int top=-1;                           // initialise stack

int main()                           // overhead!
{
    int i=-1,j,n;
    char t[10];
    void quicksort(int);

    do {
        if (i!=-1)
            list[i++]=n;
        else
            i++;
        printf("Enter the numbers <End by #>: ");
        fflush(stdin);
        scanf("%[^\n]",t);
        if (sscanf(t,"%d",&n)<1)
        break;
    } while (1);

    quicksort(i-1);

    printf("\nThe list obtained is ");
    for (j=0;j<i;j++)
        printf("\n %d",list[j]);

    printf("\n\nProgram over.");
    getch();
    return 0;       // successful termination.
}

void interchange(int *x,int *y)        // swap
{
    int temp;

    temp=*x;
    *x=*y;
    *y=temp;
}

void split(int first,int last,int *splitpoint)
{
    int x,i,j,s,g;

    // here, atleast three elements are needed
    if (list[first]<list[(first+last)/2]) {  // find median
        s=first;
        g=(first+last)/2;
    }
    else {
        g=first;
        s=(first+last)/2;
    }
    if (list[last]<=list[s]) 
        x=s;
    else if (list[last]<=list[g])
        x=last;
    else
        x=g;
    interchange(&list[x],&list[first]);      // swap the split-point element
                                             // with the first
    x=list[first];
    i=first+1;                               // initialise
    j=last+1;
    while (i<j) {
        do {                                 // find j 
            j--;
        } while (list[j]>x);
        do {
            i++;                             // find i
        } while (list[i]<x);
        interchange(&list[i],&list[j]);      // swap
    }
    interchange(&list[i],&list[j]);          // undo the extra swap
    interchange(&list[first],&list[j]);      // bring the split-point 
                                             // element to the first
    *splitpoint=j;
}

void push(int a,int b)                        // push
{
    top++;
    stack[top].a=a;
    stack[top].b=b;
}

void pop(int *a,int *b)                       // pop
{
    *a=stack[top].a;
    *b=stack[top].b;
    top--;
}

void insertion_sort(int first,int last)
{
    int i,j,c;

    for (i=first;i<=last;i++) {
        j=list[i];
        c=i;
        while ((list[c-1]>j)&&(c>first)) {
            list[c]=list[c-1];
            c--;
        }
        list[c]=j;
    }
}

void quicksort(int n)
{
    int first,last,splitpoint;

    push(0,n);
    while (top!=-1) {
        pop(&first,&last);
        for (;;) {
            if (last-first>SMALLSIZE) {
                // find the larger sub-list
                split(first,last,&splitpoint);
                // push the smaller list
                if (last-splitpoint<splitpoint-first) {
                    push(first,splitpoint-1);
                    first=splitpoint+1;
                }
                else {
                    push(splitpoint+1,last);
                    last=splitpoint-1;
                }
            }
            else {  // sort the smaller sub-lists
                    // through insertion sort
                insertion_sort(first,last);
                break;
            }
        }
    }                        // iterate for larger list
}

// End of code.

взято из здесь

Answer 3

Это мое усилие.Скажите, возможно ли какое-либо улучшение.

Этот код взят из книги «Структуры данных, Сеймур Липшуц (Страница-173), Mc GrawHill, Схема серии Шаума».

Answer 4

 I was unable to find a reliable method of doing a quicksort iteratively

Вы пробовали Google ?

Это просто обычная быстрая сортировка, когда рекурсия реализуется с массивом.