fork download
copy 
  1. #include <iostream>
  2. #include <cstddef>
  3. #include <future>
  4.  
  5. // Swap two elements - Utility function  
  6. void swap(int* a, int* b) 
  7. { 
  8.     int t = *a; 
  9.     *a = *b; 
  10.     *b = t; 
  11. } 
  12.  
  13. // partition the array using last element as pivot
  14. int partition (int arr[], int low, int high) 
  15. { 
  16.     int pivot = arr[high];    // pivot 
  17.     int i = (low - 1);   
  18.  
  19.     for (int j = low; j <= high- 1; j++) 
  20.     { 
  21.         //if current element is smaller than pivot, increment the low element
  22.         //swap elements at i and j
  23.         if (arr[j] <= pivot) 
  24.         { 
  25.             i++;    // increment index of smaller element 
  26.             swap(&arr[i], &arr[j]); 
  27.         } 
  28.     } 
  29.     swap(&arr[i + 1], &arr[high]); 
  30.     return (i + 1); 
  31. } 
  32.  
  33. //quicksort algorithm
  34. void quickSort(int arr[], int low, int high) 
  35. { 
  36.     if (low < high) 
  37.     { 
  38.         //partition the array 
  39.         int pivot = partition(arr, low, high); 
  40.  
  41.         //sort the sub arrays independently 
  42.         std::future<void> subtask = std::async(std::launch::async, quickSort, arr, low, pivot - 1);
  43.         quickSort(arr, pivot + 1, high); 
  44.         subtask.get(); // synchronously wait for the async task to finish
  45.     } 
  46. }
  47.  
  48. template<std::size_t N>
  49. void displayArray(const int(&arr)[N])
  50. {
  51. 	for (int value : arr)
  52. 	    std::cout << value << ' ';
  53. 	std::cout << '\n';
  54. }
  55.  
  56. int main() 
  57. { 
  58. 	using namespace std;
  59.  
  60.     int arr[] = {12,23,3,43,51,35,19,45}; 
  61.     int n = sizeof(arr)/sizeof(arr[0]); 
  62.     cout<<"Input array"<<endl;
  63.     displayArray(arr);
  64.     cout<<endl;
  65.     quickSort(arr, 0, n-1); 
  66.     cout<<"Array sorted with quick sort"<<endl; 
  67.     displayArray(arr); 
  68.     return 0; 
  69. }
  70.  
Success #stdin #stdout 0.01s 5608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input array
12 23 3 43 51 35 19 45 

Array sorted with quick sort
3 12 19 23 35 43 45 51
https://ideone.com/GtoTbC
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!