C ++ алгоритм быстрой сортировки

Question

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

Ссылка: http://xoax.net/comp/sci/algorithms/Lesson4.php

Когда это запускается, я получаю это в консоли:

Program loaded.
run
[Switching to process 10738]
Running…
Current language:  auto; currently c++
Program received signal:  “EXC_ARITHMETIC”.


void myQSort(int min, int max, int* myArray)
    {
        // Initially find a random pivot
        int pivotIndex = rand() % max;
            int pivot = myArray[pivotIndex];

        int i = 0 , j = max-1;

        // Pointer to begining of array and one to the end

        int* begin = myArray;
        int* end = &myArray[max-1];

        // While begin < end 
        while( begin < end )
        {
        // Find the lowest bound number to swap
            while( *begin < pivot )
            {
                begin++;
            }
            while( *end > pivot ) 
            {
                // Find the highest bound number to swap
                end--;
            }

        // Do the swap
            swap(begin,end);
        }
        // Partition left
        myQSort(0, pivotIndex-1, myArray);
        // Partiion right
        myQSort(pivotIndex+1,max, myArray);

    }

EDIT-- Код для обмена:

void swap(int* num, int* num2)
{
    int temp = *num;
    *num = *num2;
    *num2 = temp;
}

Answer 1

// sort interval [begin, end)
void myQSort(int* begin, int* end)
{
    if(end - begin < 2)
        return;
    int* l = begin;
    int* r = end - 1;

    // Initially find a random pivot
    int* pivot = l + rand() % (r - l + 1);
    while(l != r)
    {
        // Find the lowest bound number to swap
        while(*l < *pivot) ++l;
        while(*r >= *pivot && l < r) --r;

        // Do the swap
        if(pivot == l) { pivot = r; }
        std::swap(*l, *r);
    }

    // Here l == r and numbers in the interval [begin, r) are lower and in the interval [l, end) are greater or equal than the pivot
    // Move pivot to the position
    std::swap(*pivot, *l);

    // Sort left
    myQSort(begin, l);
    // Sort right
    myQSort(l + 1, end);
}

Answer 2

Вот ясная реализация C ++ для справки:

#include <iostream>
#include <vector>

using namespace std;

int partition(std::vector<int>& arr, int low, int high) {
    // set wall index
    int wall_index = low;
    int curr_index = low;
    int pivot_elem = arr[high]; // taking last element as pivot_element

    // loop through the entire received arr
    for (int i = curr_index; i < high; ++i) {
        // if element is less than or equal to pivot_elem
        // swap the element with element on the right of the wall
        // i.e swap arr[i] with arr[wall_index]
        if (arr[i] <= pivot_elem) {
            // swap
            int temp = arr[wall_index];
            arr[wall_index] = arr[i];
            arr[i] = temp;

            // move the wall one index to the right
            wall_index++;
            curr_index++;
        } else {
            // if the element is greater than the pivot_element
            // then keep the wall at the same point and do nothing
            curr_index++;
        }
    }

    // need to swap the pivot_elem i.e arr[high] with the element right of the wall
    int temp = arr[wall_index];
    arr[wall_index] = arr[high];
    arr[high] = temp;

    return wall_index;
}

void quick_sort(std::vector<int>& arr, int low, int high) {
    if (low < high) { // element with single arr always have low >= high
        int split = partition(arr, low, high);

        quick_sort(arr, low, split-1);
        quick_sort(arr, split, high);
    }
}

int main() {
    std::vector<int> data = {6,13,8,4,2,7,16,3,8};
    int N = data.size();
    quick_sort(data, 0, N-1);

    for (int i : data) {
        cout << i << " ";
    }

    return 0;
}

Answer 3

Я пытался отработать коды выше. Но они не компилируются.

@ Мигран: Ваше решение алгоритмически правильно, но следующая строка выдает ошибку:

myQSort(min, begin - myArray, myArray);

Это потому, что begin имеет тип int *, а myArray имеет тип long, после чего компилятор отображает это сообщение об ошибке:

implicit conversion loses integer precision

Вот рабочее решение на C ++:

#include <iostream>
using namespace std;

void mySwap(int& num1, int& num2){
    int temp = num1;
    num1 = num2;
    num2 = temp;
}

void myQsort(int myArray[], int min, int max){
    int pivot = myArray[(min + max) / 2];

    int left = min, right = max;

    while (left < right) {
        while (myArray[left] < pivot) {
            left++;
        }
        while (myArray[right] > pivot) {
            right--;
        }

        if (left <= right) {
            mySwap(myArray[left], myArray[right]);
            left++;
            right--;
        }
    }

    if (min < right) {
        myQsort(myArray, min, right);
    }
    if (left < max) {
        myQsort(myArray, left, max);
    }
}

int main()
{
    int myArray[] = {1, 12, -5, 260, 7, 14, 3, 7, 2};
    int min = 0;
    int max = sizeof(myArray) / sizeof(int);

    myQsort(myArray, min, max-1);

    for (int i = 0; i < max; i++) {
        cout<<myArray[i]<<" ";
    }

    return 0;
}

Answer 4

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

Answer 5

Я не вижу чистой реализации Quicksort на SO, поэтому вот моя простая для понимания реализация

ПОЖАЛУЙСТА, НЕ ИСПОЛЬЗУЙТЕ В ПРОИЗВОДСТВЕННОМ КОДЕКСЕ

Это только для вашего понимания

// Swap position a with b in an array of integer numbers
void swap(int *numbers, int a, int b){
   int temp = numbers[a];
   numbers[a] = numbers[b];
   numbers[b] = temp;
} 

static int partition(int *data, int low, int high) {

    int left = low,  right = high,  pivot = data[low];

    while (left < right) {

        // Everthing on the left of pivot is lower than the pivot 
        while ((left <= right) && data[left] <= pivot) // <= is because left is the pivot initially
            left++;

        // Everything on the right of the pivot is greater than the pivot 
        while((left <= right) && data[right] > pivot)
            right--;

        if (left < right)
            swap(data, left, right);
    }

    // Put the pivot in the 'rigthful' place
    swap(data, low, right);

    return right;
}

// Quicksort 
static void quick_sort(int *numbers, int low, int high)
{
    if (high > low) {
        int p_index = partition(numbers, low, high);

        quick_sort(numbers, low , p_index - 1);
        quick_sort(numbers, p_index + 1, high);
    }
}