Search and Sorting algorithms

searchSort.cpp

//Milad Abbasi
//06-07-2018
//Searching and Sorting algorithms

#include <iostream>
#include <random>
#include <time.h>
#include <string.h>
using namespace std;

const int n = 1000;
//const int n = 100000000;
const int RANGE = 100;

void printArray(int [], int);
void randGenerator(int []);
void swap(int &, int&);
void bubbleSort(int [], int);
void selectionSort(int [], int);
int minIndex(int [], int, int);
void recurSelectionSort(int [], int, int index = 0);
void insertionSort(int [], int);
void shellSort(int [], int);
void shakerSort(int [], int);
void countSort(int [], int);
int partition (int [], int, int);
void quickSort(int [], int, int);
void merge(int [], int, int, int);
void mergeSort(int [], int, int);
void heapify(int [], int, int);
void heapSort(int [], int);
int binarySearch(int [], int, int, int);

int main(void)
{
	int *numbers = new int[n];
	randGenerator(numbers);
	
	//printArray(numbers, n);
	//cout<<endl;
	clock_t t = clock();
	
	//bubbleSort(numbers, n);
	//selectionSort(numbers, n);
	//recurSelectionSort(numbers, n);
	//insertionSort(numbers, n);
	//shellSort(numbers, n);
	//shakerSort(numbers, n);
	//countSort(numbers, n);
	quickSort(numbers, 0, n-1);
	//mergeSort(numbers, 0, n-1);
	//heapSort(numbers, n);
	
	t = clock() - t;
	
	cout<<"Excution time: "<<(float)t / CLOCKS_PER_SEC;
	//cout<<endl;
	//printArray(numbers, n);
	
	//cout<<endl<<binarySearch(numbers, 0, n, 10);

	delete[] numbers;
	return 0;
}// End main

void printArray(int array[], int size)
{
    int i;
    for (i=0; i < size; i++)
		cout<<array[i]<<",";
}

void randGenerator(int numbers[])
{
	srand (time(NULL));
	for(size_t i = 0; i < n; i++)
	    numbers[i] = rand() % 100;
}

void swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

void bubbleSort(int numbers[], int n)
{	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n - i - 1; j++)
		{
			if(numbers[j] > numbers[j+1])
				swap(numbers[j], numbers[j+1]);
		}
}

void selectionSort(int numbers[], int n)
{
    int i, j, min_idx;
 
	// One by one move boundary of unsorted subarray
	for (i = 0; i < n-1; i++)
	{
		// Find the minimum element in unsorted array
		min_idx = i;
		for (j = i+1; j < n; j++)
			if (numbers[j] < numbers[min_idx])
				min_idx = j;
		
		// Swap the found minimum element with the first element
		swap(numbers[min_idx], numbers[i]);
	}
}

// Return minimum index
int minIndex(int numbers[], int i, int j)
{
    if (i == j)
        return i;
 
    // Find minimum of remaining elements
    int k = minIndex(numbers, i + 1, j);
 
    // Return minimum of current and remaining.
    return (numbers[i] < numbers[k]) ? i : k;
}
 
// Recursive selection sort. n is size of numbers[] and index
// is index of starting element.
void recurSelectionSort(int numbers[], int n, int index)
{
    // Return when starting and size are same
    if (index == n)
       return;
 
    // calling minimum index function for minimum index
    int k = minIndex(numbers, index, n-1);
 
    // Swapping when index and minimum index are not same
    if (k != index)
       swap(numbers[k], numbers[index]);
 
    // Recursively calling selection sort function
    recurSelectionSort(numbers, n, index + 1);
}

void insertionSort(int numbers[], int n)
{
	for(int i = 0; i < n; i++)
	{
		int j = i;
		while(j >= 0 && numbers[j] > numbers[j+1])
		{
			swap(numbers[j], numbers[j+1]);
			j--;
		}
	}

}

void shellSort(int numbers[], int n)
{
    // Start with a big gap, then reduce the gap
    for (int gap = n/2; gap > 0; gap /= 2)
    {
        // Do a gapped insertion sort for this gap size.
        // The first gap elements a[0..gap-1] are already in gapped order
        // keep adding one more element until the entire array is
        // gap sorted 
        for (int i = gap; i < n; i += 1)
        {
            // add a[i] to the elements that have been gap sorted
            // save a[i] in temp and make a hole at position i
            int tmp = numbers[i];
 
            // shift earlier gap-sorted elements up until the correct 
            // location for a[i] is found
            int j;            
            for (j = i; j >= gap && numbers[j - gap] > tmp; j -= gap)
                numbers[j] = numbers[j - gap];
             
            //  put tmp (the original a[i]) in its correct location
            numbers[j] = tmp;
        }
    }
}

void shakerSort(int numbers[], int n)
{
    bool swapped = true;
    int start = 0;
    int end = n-1;
 
    while (swapped)
    {
        // reset the swapped flag on entering
        // the loop, because it might be true from
        // a previous iteration.
        swapped = false;
 
        // loop from left to right same as
        // the bubble sort
        for (int i = start; i < end; ++i)
        {
            if (numbers[i] > numbers[i + 1])
            {
                swap(numbers[i], numbers[i+1]);
                swapped = true;
            }
        }
 
        // if nothing moved, then array is sorted.
        if (!swapped)
            break;
 
        // otherwise, reset the swapped flag so that it
        // can be used in the next stage
        swapped = false;
 
        // move the end point back by one, because
        //  item at the end is in its rightful spot
        --end;
 
        // from right to left, doing the
        // same comparison as in the previous stage
        for (int i = end - 1; i >= start; --i)
        {
            if (numbers[i] > numbers[i + 1])
            {
                swap(numbers[i], numbers[i+1]);
                swapped = true;
            }
        }
 
        // increase the starting point, because
        // the last stage would have moved the next
        // smallest number to its rightful spot.
        ++start;
    }
}

void countSort(int numbers[], int n)
{
    int count[RANGE] = {0};
    int i;
    int out[n];
    
    for(i = 0; i < n; i++)
    	++count[numbers[i]];
    
    for(i = 1; i < RANGE; i++)
    	count[i] += count[i-1];
    
    for(i = n - 1; i >= 0; i--)
	{
        out[count[numbers[i]] - 1] = numbers[i];
        --count[numbers[i]];
    }
    
    for(i = 0; i < n; i++)
    	numbers[i] = out[i];
}


/* This function takes 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 numbers[], int low, int high)
{
    int pivot = numbers[high];    // pivot
    int i = (low - 1);  // Index of smaller element
 
    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (numbers[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(numbers[i], numbers[j]);
        }
    }
    swap(numbers[i + 1], numbers[high]);
    return (i + 1);
}
 
/* The main function that implements QuickSort
 arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void quickSort(int numbers[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(numbers, low, high);
 
        // Separately sort elements before
        // partition and after partition
        quickSort(numbers, low, pi - 1);
        quickSort(numbers, pi + 1, high);
    }
}


// Merges two subarrays of numbers[].
// First subarray is numbers[l..m]
// Second subarray is numbers[m+1..r]
void merge(int numbers[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
 
    /* create temp arrays */
    int L[n1], R[n2];
 
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = numbers[l + i];
    for (j = 0; j < n2; j++)
        R[j] = numbers[m + 1+ j];
 
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            numbers[k] = L[i];
            i++;
        }
        else
        {
            numbers[k] = R[j];
            j++;
        }
        k++;
    }
 
    /* Copy the remaining elements of L[], if there
       are any */
    while (i < n1)
    {
        numbers[k] = L[i];
        i++;
        k++;
    }
 
    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2)
    {
        numbers[k] = R[j];
        j++;
        k++;
    }
}
 
/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(int numbers[], int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;
 
        // Sort first and second halves
        mergeSort(numbers, l, m);
        mergeSort(numbers, m+1, r);
 
        merge(numbers, l, m, r);
    }
}

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int numbers[], int n, int i)
{
    int largest = i;  // Initialize largest as root
    int l = 2*i + 1;  // left = 2*i + 1
    int r = 2*i + 2;  // right = 2*i + 2
 
    // If left child is larger than root
    if (l < n && numbers[l] > numbers[largest])
        largest = l;
 
    // If right child is larger than largest so far
    if (r < n && numbers[r] > numbers[largest])
        largest = r;
 
    // If largest is not root
    if (largest != i)
    {
        swap(numbers[i], numbers[largest]);
 
        // Recursively heapify the affected sub-tree
        heapify(numbers, n, largest);
    }
}
 
// main function to do heap sort
void heapSort(int numbers[], int n)
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(numbers, n, i);
 
    // One by one extract an element from heap
    for (int i=n-1; i>=0; i--)
    {
        // Move current root to end
        swap(numbers[0], numbers[i]);
 
        // call max heapify on the reduced heap
        heapify(numbers, i, 0);
    }
}


// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1
int binarySearch(int numbers[], int begin, int end, int x)
{
   if (end >= begin)
   {
        int mid = begin + (end - begin) / 2;
 
        // If the element is present at the middle 
        // itself
        if (numbers[mid] == x)  
            return mid;
 
        // If element is smaller than mid, then 
        // it can only be present in left subarray
        if (numbers[mid] > x) 
            return binarySearch(numbers, begin, mid-1, x);
 
        // Else the element can only be present
        // in right subarray
        return binarySearch(numbers, mid+1, end, x);
   }
 
   // We reach here when element is not 
   // present in array
   return -1;
}