Быстрая сортировка C ++ с указателями - PullRequest
Новая
       6

Быстрая сортировка C ++ с указателями

0 голосов
/ 21 февраля 2020

Может ли кто-нибудь указать на ошибку в моем коде? Извините за вводящие в заблуждение имена аргументов функций - rptr должен быть rvalue или что-то в этом роде c, я постоянно что-то менял. Большая часть этого должна быть сделана с помощью указателей. Я думаю, что ошибка может быть в partArr, возвращающем недопустимую переменную, но я действительно не знаю. 

#include <iostream>

const int ArSize = 10;

void swap(int *lptr, int *rptr) {
    int tempV = *lptr;
    *lptr = *rptr;    
    *rptr = tempV;
}

int partArr(int *arr, int lptr, int rptr) {
    int pivot = (lptr + rptr) / 2;
    int * leftP = &lptr;
    int * rightP = &rptr;

    while (true) {
        while (arr[*rightP] >= pivot) --(*rightP);
        while (arr[*leftP] <= pivot)  ++(*leftP);
        if(*rightP > *leftP) {
            swap(leftP,rightP);
            --(*rightP);
            ++(*leftP);
        }
        else {
            return rptr;
        }
    }
}

void quickSort(int *arr, int ptrL, int ptrR) {
    if (ptrR > ptrL) { 
        int arr_piv = partArr(arr, ptrL, ptrR);    
        quickSort(arr, ptrL, arr_piv - 1);    
        quickSort(arr,arr_piv+1,ptrR);
    }
}

int main() {
    int tab[ArSize] = {10, 40, 30, 4, 3, 312, 3, 4, 1};  
    int ptrL = tab[0];    
    int ptrR = tab[ArSize - 1];
    quickSort(tab, ptrL, ptrR);
    for (int x : tab)
        std::cout << x << " ";
    return 0;
}

Ответы [ 2 ]

2 голосов
/ 21 февраля 2020

Здесь 

int * leftP = &lptr;
int * rightP = &rptr;

вы берете адреса параметров функции. Когда вы звоните 

swap(leftP,rightP);

, вы меняете значения lptr и rptr. Когда вы пишете 

--(*rightP)

, вы уменьшаете значение rptr. Вы никогда не изменяете элемент массива.

У меня нет степени CS, поэтому, когда я хочу отсортировать массив, я использую std::sort: 

#include <algorithm>
#include <iostream>
#include <iterator>
int main() {
    int tab[] = {10, 40, 30, 4, 3, 312, 3, 4, 1};  

    std::sort( std::begin(tab), std::end(tab));

    for (int& x : tab)
        std::cout << x << " ";
    return 0;
}

Если вам нужно реализовать это самостоятельно в качестве упражнения, вам следует научиться пользоваться отладчиком, иначе вы всегда столкнетесь с такими проблемами. Чтобы стать лучше в кодировании, нужно не столько не допустить ошибок, сколько узнать, как их обнаружить и исправить, и именно для этого создан отладчик.

0 голосов
/ 21 февраля 2020

Быстрая сортировка с использованием указателей не должна передавать имя массива в качестве параметра. Пример кода: 

void QuickSort(int *lo, int *hi)
{
int *i, *j;
int p, t;
    if(lo >= hi)
        return;
    p = *(lo + (hi-lo)/2);
    i = lo - 1;
    j = hi + 1;
    while (1){
        while (*(++i) < p);
        while (*(--j) > p);
            if (i >= j)
                break;
            t = *i;
            *i = *j;
            *j = t;
    }
    QuickSort(lo, j);
    QuickSort(j+1, hi);
}

Вызов быстрой сортировки будет: 

QuickSort(array, array+(sizeof(array)/sizeof(array[0]))-1);
...