Question: How can I improve quick sort to run faster and only print the numbers once?

example- 1111112222233333344445555

instead print it as - 123456.

// QuickSort.cpp : Defines the entry point for the console application. // QuickSort Algorithm - Divide and conquer algorithm // Running time - Big O (n log n)

#include "stdafx.h" #include #include using namespace std; //to display the array/list values const int SIZE = 10; const int NEWSIZE = 100000; //display output void output(int a[], int size) { for (int i = 0; i < size; i++) { cout << a[i] << ' '; } cout << endl; } //generating a random array void generate_array(int a[], int size) { for (int i = 0; i < size; i++) a[i] = rand() % 1000 + 1;

cout << "unsorted: "; output(a, size); } //Partition funtion: //swap based on pivot //pivot chosen to be left-most element //easiest choice but not always most efficient. int partition(int *v, int left, int right) { int i = left + 1; //swap index int p = v[left]; //set current pivot to left-most for (int j = left + 1; j < right + 1; j++) { if (v[j] < p) { //compare with current p, if less then swap int temp = v[j]; v[j] = v[i]; v[i] = temp; cout << v[j] << " "; i++; } cout << endl; cout << v[j] << " "; } cout << endl; int pos = i - 1; int temp = v[left]; v[left] = v[pos]; v[pos] = temp; output(v, right+1); return pos; //return new midpoint with pivot in its final position } //operate recursively, into smaller and smaller left-right sub lists void quick_sort(int * v, int left, int right) { if (left < right) { int pos = partition(v, left, right); quick_sort(v, left, pos - 1); quick_sort(v, pos + 1, right); } } int main() { clock_t t; double execution_time; t = clock(); //const int SIZE = 10; int a[SIZE] = { 8, 4, 1, 5, 10, 7, 6, 2, 9, 3 }; cout << "unsorted: "; output(a, SIZE); cout << endl;

quick_sort(a, 0, SIZE-1); cout << "sorted: "; output(a, SIZE); cout << endl; t = clock() - t; execution_time = (double)t / CLOCKS_PER_SEC; printf("quick sort took %f seconds to execute ", execution_time); cout << endl;

t = clock(); cout << endl << endl; int b[NEWSIZE]; cout << "Generating a random array" << endl; generate_array(b, NEWSIZE); cout << endl; //sorting the array using quicksort quick_sort(b, 0, NEWSIZE-1); cout << "sorted: "; output(b, NEWSIZE); cout << endl; t = clock() - t; execution_time = (double)t / CLOCKS_PER_SEC; printf("quick sort took %f seconds to execute ", execution_time); cout << endl;

return 0; }