Quicksort 2 - Sorting

  • + 13 comments

    When the problem gives the function declaration already, I tend to stick with it and not change it. You can solve this problem with the given vector parameter. Notice arr is passed in as a reference, so there is no need to return back another vector. The exit case can just be detected if size < 2, don't need to swap when size == 2. I tested with a swap, but it just gave me the same answer. Hope this helps anyone stuck on this problem.

    [C++]

    void quickSort(vector &arr) {

    // Complete this function
    
    int size = arr.size();
    if (size < 2) {
        return;
    }
    
    vector <int> leftArray;
    vector <int> rightArray;
    
    int pivot = arr[0];
    
    for (int i = 1; i < size; ++i) {
        if (arr[i] <= pivot) {
            leftArray.push_back(arr[i]);
        }
        else {
            rightArray.push_back(arr[i]);
        }
    }
    quickSort(leftArray);
    quickSort(rightArray);
    
    int index = 0;
    
    // Copy left array back into the original array
    for (unsigned int l = 0; l < leftArray.size(); ++l) {
        arr[index++] = leftArray[l];
        cout << leftArray[l] << " ";
    }
    
    // Copy the pivot between left & right arrays
    arr[index++] = pivot;
    cout << pivot << " ";
    
    // Copy right array back into the original array
    for (unsigned int r = 0; r < rightArray.size(); ++r) {
        arr[index++] = rightArray[r];
        cout << rightArray[r] << " ";
    }
    cout << endl;
    

    }