Быстрая сортировка в C выпуск - PullRequest
Новая
       6

Быстрая сортировка в C выпуск

1 голос
/ 10 марта 2020

В какой-то момент моя программа быстрой сортировки застряла в C. Кто-нибудь может указать, где ошибка? Мой код не запускается, и я попытался сравнить его с несколькими онлайн-программами. Завтра у меня тест, и я хочу узнать, в чем заключается ошибка, прежде чем я попытаюсь. 

#include <stdio.h>

void swap(int a,int b){
    int t;
    t=a;
    a=b;
    b=t;
}

int partition(int a[],int l,int h){
    int pi=l,i=l,j=h;
    while(i<j){
            while(a[i]<=a[pi])
                i++;
            while(a[j]>a[pi])
                j--;
            if(i<j){
                swap(a[i],a[j]);
            }
        }
    swap(a[j],a[pi]);
    return j;
}

void quicksort(int a[],int l,int h){
    int j;
    j=partition(a,l,h);
    quicksort(a,l,j-1);
    quicksort(a,j+1,h);
}

int main(){
    int n,i;
    printf("Enter the number of elements: ");
    scanf("%d",&n);
    int a[n];
    printf("Enter the elements: ");
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    quicksort(a,0,n-1);
    printf("The array after sorting is: ");
    for(i=0;i<n;i++){
        printf("%d",a[i]);
    }
    return 0;
}

Ответы [ 2 ]

1 голос
/ 10 марта 2020

Ваш код имеет несколько проблем.

Во-первых, ваша функция подкачки меняет местные переменные a и b, но это не повлияет на массив a в partition. Йен Эбботт объяснил это более подробно.

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

void swap(int array[], int i, int j)
{
    int t = array[i]; array[i] = array[j]; array[j] = t;
}

Во-вторых, должна когда-нибудь остановить рекурсию. Когда у вас есть массив только с одним элементом или вообще без элементов, делать нечего, потому что массив (или подмассив) уже отсортирован.

Так что ничего не делайте в этом случае. Или, скорее, делать что-то только тогда, когда у вас есть хотя бы два элемента. Это имеет приятный побочный эффект, что рекузрион фактически останавливается. :)

void quicksort(int a[], int l, int h)
{
    if (l < h) {
        int j;

        j = partition(a, l, h);
        quicksort(a, l, j - 1);
        quicksort(a, j + 1, h);
    }
}
1 голос
/ 10 марта 2020

Аргументы функции передаются значением в C. Ваша swap функция: 

void swap(int a,int b){
    int t;
    t=a;
    a=b;
    b=t;
}

получает два целочисленных аргумента, int a и int b. Внутри функции они ведут себя как локальные переменные, поэтому изменения на a и b в функции swap не оказывают никакого влияния на вызывающего.

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

Например, ваша функция swap может быть изменена следующим образом: 

void swap(int *a,int *b){
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

Вызовы этой функции также необходимо изменить, чтобы передать адреса объектов чьи значения должны быть обменены. Например, swap(a[i],a[j]); необходимо изменить на swap(&a[i],&a[j]); (или, что эквивалентно, изменить на swap(a+i,a+j);).

...