Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d1/daa/random__pivot__quick__sort_8cpp.html below:

TheAlgorithms/C++: sorting/random_pivot_quick_sort.cpp File Reference

Loading...

Searching...

No Matches

Implementation of the Random Pivot Quick Sort algorithm. More...

#include <algorithm>
#include <array>
#include <cassert>
#include <ctime>
#include <iostream>
#include <tuple>

Go to the source code of this file.

Implementation of the Random Pivot Quick Sort algorithm.

• A random pivot quick sort algorithm is pretty much same as quick sort with a difference of having a logic of selecting next pivot element from the input array.
• Where in quick sort is fast, but still can give you the time complexity of O(n^2) in worst case.
• To avoid hitting the time complexity of O(n^2), we use the logic of randomize the selection process of pivot element.

       ### Logic
           * The logic is pretty simple, the only change is in the
  

  partitioning algorithm, which is selecting the pivot element.
  • Instead of selecting the last or the first element from array for pivot we use a random index to select pivot element.
  • This avoids hitting the O(n^2) time complexity in practical use cases.

      ### Partition Logic
          * Partitions are done such as numbers lower than the "pivot"
    

    element is arranged on the left side of the "pivot", and number larger than the "pivot" element are arranged on the right part of the array.

      ### Algorithm
          * Select the pivot element randomly using getRandomIndex() function
    

    from this namespace.

Initialize the pInd (partition index) from the start of the array.

• Loop through the array from start to less than end. (from start to < end). (Inside the loop) :-
  • Check if the current element (arr[i]) is less than the pivot element in each iteration.
  • If current element in the iteration is less than the pivot element, then swap the elements at current index (i) and partition index (pInd) and increment the partition index by one.
• At the end of the loop, swap the pivot element with partition index element.
• Return the partition index from the function.

Definition in file random_pivot_quick_sort.cpp.

template<size_t size>

A function utility to generate unsorted array of given size and range.

Template Parameters

size Size of the output array.

Parameters

from Stating of the range. to Ending of the range.

Returns

std::array<int64_t , size> Unsorted array of specified size.

Definition at line 160 of file random_pivot_quick_sort.cpp.

160 {

161 srand(time(nullptr));

162 std::array<int64_t, size> unsortedArray{};

163 assert(from < to);

164 int64_t i = 0;

165 while (i < size) {

166 int64_t randomNum = from + rand() % (to - from + 1);

167 if (randomNum) {

168 unsortedArray[i] = randomNum;

169 i++;

170 }

171 }

172 return unsortedArray;

173}

Takes the start and end indices of an array and returns a random int64_teger between the range of those two for selecting pivot element.

Parameters

start The starting index. end The ending index.

Returns

int64_t A random number between start and end index.

Definition at line 88 of file random_pivot_quick_sort.cpp.

88 {

89 srand(time(nullptr));

90 int64_t randomPivotIndex = start + rand() % (end - start + 1);

91 return randomPivotIndex;

92}

Main function.

Returns

0 on exit

Definition at line 321 of file random_pivot_quick_sort.cpp.

321 {

323

324 const int64_t inputSize = 10;

325 std::array<int64_t, inputSize> unsorted_array =

327 50, 1000);

328 std::cout << "Unsorted array is : " << std::endl;

330

331 std::array<int64_t, inputSize> sorted_array =

333 unsorted_array, 0, unsorted_array.size() - 1);

334 std::cout << "Sorted array is : " << std::endl;

336 return 0;

337}

std::array< int64_t, size > generateUnsortedArray(int64_t from, int64_t to)

A function utility to generate unsorted array of given size and range.

std::array< int64_t, size > quickSortRP(std::array< int64_t, size > arr, int64_t start, int64_t end)

Random pivot quick sort function. This function is the starting point of the algorithm.

static void test()

Self-test implementations.

void showArray(std::array< int64_t, T > arr)

Utility function to print the array.

template<size_t size>

A partition function which handles the partition logic of quick sort.

Template Parameters

size size of the array to be passed as argument.

Parameters

start The start index of the passed array end The ending index of the passed array

Returns

std::tuple<int64_t , std::array<int64_t , size>> A tuple of pivot index and pivot sorted array.

Definition at line 103 of file random_pivot_quick_sort.cpp.

104 {

105 int64_t pivot = arr[end];

106

107 int64_t pInd = start;

108

109 for (int64_t i = start; i < end; i++) {

110 if (arr[i] <= pivot) {

111 std::swap(arr[i], arr[pInd]);

112

113 pInd++;

114 }

115 }

116 std::swap(arr[pInd],

117 arr[end]);

118 return std::make_tuple(pInd, arr);

119}

template<size_t size>

Random pivot quick sort function. This function is the starting point of the algorithm.

Template Parameters

size size of the array to be passed as argument.

Parameters

start The start index of the passed array end The ending index of the passed array

Returns

std::array<int64_t , size> A fully sorted array in ascending order.

Definition at line 130 of file random_pivot_quick_sort.cpp.

131 {

132 if (start < end) {

134

135

136 std::swap(arr[end], arr[randomIndex]);

137

138 int64_t pivotIndex = 0;

139

std::tie(pivotIndex, arr) =

(arr, start, end);

141

142

143 std::array<int64_t, arr.size()> rightSortingLeft =

145 std::array<int64_t, arr.size()> full_sorted =

(rightSortingLeft, pivotIndex + 1, end);

147 arr = full_sorted;

148 }

149 return arr;

150}

std::tuple< int64_t, std::array< int64_t, size > > partition(std::array< int64_t, size > arr, int64_t start, int64_t end)

A partition function which handles the partition logic of quick sort.

int64_t getRandomIndex(int64_t start, int64_t end)

Takes the start and end indices of an array and returns a random int64_teger between the range of tho...

template<size_t T>

Utility function to print the array.

Template Parameters

Parameters

arr array used to print its content

Returns

void

Definition at line 73 of file random_pivot_quick_sort.cpp.

73 {

74 for (int64_t i = 0; i < arr.size(); i++) {

75 std::cout << arr[i] << " ";

76 }

77 std::cout << std::endl;

78}

Self-test implementations.

Returns

void

Definition at line 312 of file random_pivot_quick_sort.cpp.

312 {

315}

class encapsulating the necessary test cases

void runTests()

Executes test cases.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4