I need to sort my array in a random order. Thanks /* C++ implementation QuickSor
ID: 3706856 • Letter: I
Question
I need to sort my array in a random order. Thanks
/* C++ implementation QuickSort */
#include <iostream>
using namespace std;
void swap(int* a, int* b);
int partition (int arr[], int i, int j);
void quickSort(int arr[], int i, int j);
void printArray(int arr[], int size);
// Driver program to test above functions
int main()
{
int arr[] = {6, 2, 5, 4, 7, 1, 8, 3};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
cout << "Sorted array: ";
printArray(arr, n);
system ("pause");
return 0;
}
// A utility function to swap two elements
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
/* This function takes the last element as pivot, places the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int i, int j)
{
int pivot = arr[i]; // pivot
int h = i; // Index of smaller element
for (int k = i+1; k <= j; k++)
{
// If current element is smaller than or
// equal to pivot
if (arr[k] <= pivot)
{
h++; // increment index of smaller element
swap(&arr[h], &arr[k]);
}
}
swap(&arr[i], &arr[h]);
return (h);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
i --> Starting index,
j --> Ending index */
void quickSort(int arr[], int i, int j)
{
if (i < j)
{
/* p is partitioning index, arr[p] is now
at right place */
int p = partition(arr, i, j);
// Separately sort elements before
// partition and after partition
quickSort(arr, i, p - 1);
quickSort(arr, p + 1, j);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout << " " << arr[i];
cout << endl;
}
/* Function to print an array */
void printArray2(int arr[], int i, int j)
{
int k;
for (k=i; k <= j ; k++)
cout << " " << arr[k];
cout << endl;
}
Explanation / Answer
U can use random pivoting for getting random order.
int partition_random (int arr[], int i, int j)
{
srand(time(NULL));
int rand=i+rand()%(j-i);
swap(&arr[random], &arr[h]);
return partition(arr,i,j);
}
//Full code
#include <iostream>
#include<cstdlib>
using namespace std;
void swap(int* a, int* b);
int partition (int arr[], int i, int j);
void quickSort(int arr[], int i, int j);
void printArray(int arr[], int size);
// Driver program to test above functions
int main()
{
int arr[] = {6, 2, 5, 4, 7, 1, 8, 3};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
cout << "Sorted array: ";
printArray(arr, n);
system ("pause");
return 0;
}
// A utility function to swap two elements
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
/* This function takes the last element as pivot, places the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int i, int j)
{
int pivot = arr[i]; // pivot
int h = i; // Index of smaller element
for (int k = i+1; k <= j; k++)
{
// If current element is smaller than or
// equal to pivot
if (arr[k] <= pivot)
{
h++; // increment index of smaller element
swap(&arr[h], &arr[k]);
}
}
swap(&arr[i], &arr[h]);
return (h);
}
int partition_random (int arr[], int i, int j)
{
srand(time(NULL));
int rand=i+rand()%(j-i);
swap(&arr[random], &arr[h]);
return partition(arr,i,j);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
i --> Starting index,
j --> Ending index */
void quickSort(int arr[], int i, int j)
{
if (i < j)
{
/* p is partitioning index, arr[p] is now
at right place */
int p = partition_random(arr, i, j);
// Separately sort elements before
// partition and after partition
quickSort(arr, i, p - 1);
quickSort(arr, p + 1, j);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout << " " << arr[i];
cout << endl;
}