Получение большого значения со знаком в моем алгоритме QuickSort / InsertionSort - PullRequest
Новая
       27

Получение большого значения со знаком в моем алгоритме QuickSort / InsertionSort

1 голос
/ 29 апреля 2019

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

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

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

int partitionMiddle (int arr[], int low, int high) {

    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high- 1; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void chooseMiddle....
void chooseMedian{code here...}

void insertionSort(int arr[], int low, int high){
    int j;
    for(int i = low+1; i <= high; i++){
        j = i;

        while(j>low && arr[j-1]> arr[j]){
            swap(arr[j], arr[j-1]);
            j= j-1;
        }
    }
}

void quickSortMiddle(int arr[], int low, int high)
{
    int pi = partitionMiddle(arr, low, high);
    if (high-low > 20)
    {    
        quickSortMiddle(arr, low, pi - 1);
        quickSortMiddle(arr, pi + 1, high);
    }
    else {
           insertionSort(arr, low, pi);
           insertionSort(arr, pi+1, high);   
   }
}

void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
}


int main()
{
    clock_t x, k;
    x = clock();

    int arr[10000];
    srand((unsigned)time(0));

    for(int i =0; i<10000; i++) {
        arr[i] = (rand()%100)+1;
    }

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Original array: " ;
    printArray(arr, n);
    cout << endl;

    cout << "With Insertion Sort & Middle Element";

    chooseMiddle(arr, 0, n-1);
    quickSortMiddle(arr, 0, n-1);

    cout << endl;

    k = clock();

    // can comment this one vvvv or the previous one out to try them both
    cout << "With Insertion Sort & Median Element";

    chooseMedian(arr, 0, arr[((n-1)/2)], n-1);
    quickSortMiddle(arr, 0, n-1);

    cout << endl;

    k = clock();

    printf("Sorted array: ");
    printArray(arr, n);

    cout << endl;

    cout << "CPU Time : ";
    cout << k-x;

    cout << endl << endl;
    return 0;
}

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

**** РЕДАКТИРОВАТЬ ... Таким образом, я пошел, чтобы отладить код самостоятельно, и это число появлялось там, так или иначе имеющее отношение к n-1параметр, когда я вызывал функции chooseMedian / chooseMiddle или quickSortMiddle.Я изменил это, чтобы быть просто 'n'.Я не понимаю почему, но сейчас это работает.Если кто-то может объяснить почему, это было бы полезно, но если нет, то это тоже нормально.

**** РЕДАКТИРОВАТЬ2 ... Итак, теперь, когда я привлек ваше внимание, не могли бы вы объяснить мне, почему с помощьюуказатели в функции подкачки лучше, чем нет?Я нашел этот пример функции свопинга в Интернете и не знаю, почему они использовали указатели.

...