Реализация Quicksort в C с использованием первого элемента в качестве точки опоры

Question

Я полный новичок для stackoverflow, и это мой первый пост. Пожалуйста, простите, если это не правильное место для публикации этих запросов. Я написал код для алгоритма Quicksort, основанный на алгоритме, указанном в курсе «Алгоритмы» в Coursera (однако это не для каких-либо назначений).

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

Любая помощь приветствуется. Благодарю.

#include <stdio.h> 
    void swap(int *p, int i, int j) 
    { 
     int temp = *(p+i); 
     *(p+i) = *(p+j); 
     *(p+j) = temp; 
    } 

    int partition(int *q, int l, int r) 
    { 
     int i = l+1, j; 
     int p = l; 
     int len = r-l +1; 
     for (j = l+1; j < len; j++) 
     { 
      /*printf("%d \n", j);*/ 
      if (*(q+j) < *(q+p)) 
      { 
       swap(q, i, j); 
       i += 1; 
      } 
     } 
     swap(q, l, i-1); 
     /*printf("%d", i-1);*/ 
     return (i-1); 
    } 

    void quicksort(int *ptr, int low, int high) 
    { 
     if (low < high) 
     { 
      int p = partition(ptr, low, high); 
      printf("%d\n", p); 
      quicksort(ptr, low, p); 
      quicksort(ptr, p+1, high); 
     } 
    } 


    int main(){ 
     int i; 
     int a[] = {3, 8, 2, 5, 1, 4, 7, 6}; 
     int len = sizeof(a)/sizeof(a[0]); 
     for (i = 0; i < len; ++i) 
     { 
      printf("%d ", a[i]); 
     } 
     printf("\n"); 
     int *ptr = a; 
     quicksort(ptr, 0, len-1); 
     for (i = 0; i < sizeof(a)/sizeof(a[0]); ++i) 
     { 
      printf("%d ", a[i]); 
     } 
     printf("\n"); 
     return 0; 
    } 

Answer 1

2 исправления.

Малый один: Изменение 3-й линии внутри, если блок в функции QuickSort

из

quicksort(ptr, low, p); 

в

quicksort(ptr, low, p-1); 

Это позволит повысить производительность.

Основная ошибка:

Ваша функция перегородки неверна. В частности, цикл, где j работает от l+1 до r-l+1, потому что, r-l+1 может быть меньше, чем l+1

Напишу статсумму для вас, если вы хотите (оставить комментарий, если вы сталкиваетесь с какой-либо проблемы с этим), хотя я советую сделать это самостоятельно.

EDIT:

Возможная статсумма:

int partition(int *q, int l, int r){ 
    int i,j; 
    int p = *(q + l); 
    for(i = l + 1, j = r; ;){ 
     while(*(q + i) <= p) 
      i++; 
     while(*(q + j) >= p) 
      j--; 
     if(i >= j) 
      break; 
     swap(q, i, j); 
    } 
    return i; 
} 

Answer 2

Изменение отмечены в комментариях.

int partition(int *q, int l, int r) 
{ 
    int i = l+1, j; 
    int p = l; 
            /* fix: int len = r-l+1; is not used */ 
    for (j = l+1; j <= r; j++)  /* fix: j <= r */ 
    { 
     if (*(q+j) <= *(q+p))  /* fix: <= */ 
     { 
      swap(q, i, j); 
      i += 1; 
     } 
    } 
    swap(q, l, i-1); 
    return (i-1); 
} 

void quicksort(int *ptr, int low, int high) 
{ 
    if (low < high) 
    { 
     int p = partition(ptr, low, high); 
     quicksort(ptr, low, p-1); /* optimization: p-1 */ 
     quicksort(ptr, p+1, high); 
    } 
} 

Если заинтересована, схема разделения Hoare выполняется быстрее. Если вы переключитесь на это, не забудьте изменить два быстрых вызова на quicksort (lo, p) и quicksort (p + 1, hi)). Возможно, вы захотите изменить поворот Хора на pivot = A [(lo + hi)/2], что позволит избежать проблемы с наихудшим случаем при сортированном или обратном отсортированном массиве.

http://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme