A sorting method arranges a set of elements into either an ascending or descending sequence.
A search method looks for a specified element in a set.
Sorting methods usually involve the two basic operations of comparing and swapping elements.
We will first implement an insertion sort of an array. Our insertion sort will go backwards through an array of n elements. Our method first compares the element array[n-1] and array[n-2]. If array[n-1] is less than array[n-2], then array[n-1] is inserted before array[n-2], thus leading to a sublist sorted in ascending order. We insert one element after another into this sorted sublist in an interative fashion until the whole array is sorted.
We’ll start with our basic sort class definition.
#pragma once #include <iostream> class Sort{ private: int *iArray; int n; public: Sort(int size); copyList(int toCopy[], int size); void insertionSort(); }
Next, let’s implement these functions.
#include "sort.h" Sort::Sort(int n){ this->n = n; this->iArray = new int[n]; } void Sort::copyList(int toCopy[], int length){ //check for bounds if(length > n) { length = n; } if(length < 1) { return; } while(length-- > 0){ this->iArray[length] = toCopy[length]; } } void Sort::printArray(){ int i = 0; for(; i < n; i++){ std::cout << iArray[i] << " "; } std::cout << std::endl; } void Sort::insertionSort(){ int j = n - 1; int i, swap; while(j > 0){ i = j--; swap = iArray[j]; while((swap > iArray[i]) && (i < n)){ iArray[i - 1] = iArray[i]; i++; } iArray[i - 1] = swap; //show progress printArray(); } }
And let’s see if it all works.
#include "sort.h" int main(){ const int array_size = 14; int dataArray[array_size] = {1138, 42, 10538, 8, 389, 443, 1701, 73, 47, 451, 88, 3, 5, 17}; Sort theSorter(array_size); theSorter.copyList(dataArray, array_size); theSorter.insertionSort(); return 0; }
So far, so good!
Insertion sort isn’t exactly the greatest sort out there. In the worst case scenario we get O(n^2) performance.
Next, let’s look at an implementation of bubble sort.
First, let’s add the method definition to sort.h
void bubbleSort();
Next, let’s implement the method.
void Sort::bubbleSort(){ bool swapFlag = true; int iteration, i, j, temp; for(iteration = 0; iteration < n && swapFlag == true; iteration++){ swapFlag = false; for(i = 0, j = n - iteration; i < j; i++){ if(iArray[i] > iArray[i+1]){ //swap the items swapFlag = true; temp = iArray[i]; iArray[i] = iArray[i+1]; iArray[i+1] = temp; printArray(); } } } }
Bubble sort has some issues. For one, it depends on comparing and swapping only consecutive data elements. In each iteration, only one element actually ends up definitely where it is supposed to be in the sequence.
The quicksort algorithm is one of the most efficient sorting algorithms. Quicksort divides the set into smaller subsets, it then sorts the subsets, and the merges the sorted subsets into the final sequence. The divide-and-conquer strategy splits a big problem into smaller, easier to solve problems, then puts it back together again. Quicksort splits the data up by selecting a key and using it as a pivot value so that it divides the data into a left and right subset. Our implemenation of quicksort will involve recursive calls to the same function, which will eat up stack space. Also, there is the concern of the memory needed for copying into the new sorted array – although there is an in place version of quicksort available.
We will create two functions, a public function, and a private function called by the public function
#pragma once #include <iostream> class Sort{ private: int *iArray; int n; void quickSortHelper(int first, int last); public: Sort(int size); void copyList(int toCopy[], int size); void insertionSort(); void bubbleSort(); void quickSort(); void printArray(); };
Then we will implement the two functions.
void Sort::quickSort(){ if(n > 0){ quickSortHelper(0, n-1); } printArray(); } void Sort::quickSortHelper(int first, int last){ std::cout << "first: " << first << " " << "last: " << last << std::endl; //check that first is before last if(first < last){ int temp; int thePivot = iArray[first]; int leftIndex = first; int rightIndex = last; std::cout << "The pivot value: " << thePivot << std::endl; while(leftIndex < rightIndex){ while(iArray[leftIndex] <= thePivot && leftIndex < last){ //move the left index to the right //until it points to an element greater in value //than the element in the first element leftIndex++; } while(iArray[rightIndex] >= thePivot && rightIndex > first){ //move the right index to the left //until it points to an element less than in value //in the first element rightIndex--; } //if the left index is less than the right index //swap the two elements if(leftIndex < rightIndex){ temp = iArray[rightIndex]; iArray[rightIndex] = iArray[leftIndex]; iArray[leftIndex] = temp; } } //switch theArray[lastIndex] with theArray[firstIndex] temp = iArray[rightIndex]; iArray[rightIndex] = iArray[first]; iArray[first] = temp; printArray(); //sort the section to the left of the new pivot quickSortHelper(first, rightIndex - 1); //sort the section to the right of the new pivot quickSortHelper(rightIndex + 1, last); } }
Simple C++ Tutorials 