Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

C++ quicksort

  1. User

    C++ quicksort

  2. Assistant

    Quicksort is a commonly used sorting algorithm in C++. It is an efficient algorithm that uses a divide-and-conquer approach to sort an array or a list of elements. Here is an implementation of quicksort in C++:

    #include <iostream>
    using namespace std;
    
    // Function to swap two elements
    void swap(int* a, int* b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    // Function to partition the array and return the partitioning index
    int partition(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++;
                swap(&arr[i], &arr[j]);
            }
        }
        swap(&arr[i + 1], &arr[high]);
        return (i + 1);
    }
    
    // Function to implement quicksort
    void quicksort(int arr[], int low, int high)
    {
        if (low < high)
        {
            int pi = partition(arr, low, high);
            quicksort(arr, low, pi - 1);
            quicksort(arr, pi + 1, high);
        }
    }
    
    // Function to print an array
    void printArray(int arr[], int size)
    {
        for (int i = 0; i < size; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
    
    // Driver code
    int main()
    {
        int arr[] = { 11, 2, 9, 13, 57, 25, 17 };
        int n = sizeof(arr) / sizeof(arr[0]);
    
        cout << "Original Array: ";
        printArray(arr, n);
    
        quicksort(arr, 0, n - 1);
    
        cout << "Sorted Array: ";
        printArray(arr, n);
    
        return 0;
    }
    

    This implementation takes an array of integers as input and sorts it using the quicksort algorithm. The partition function is used to choose a pivot element and partition the array around it. The quicksort function recursively applies the partitioning and sorting steps to the sub-arrays. Finally, the printArray function is used to display the sorted array.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.