## C++ || Snippet – Bubble Sort, Selection Sort, Insertion Sort, Quick Sort & Merge Sort Sample Code For Integer Arrays

This page consists of algorithms for sorting integer arrays. Highlighted on this page are Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, and Merge Sort.

In terms of performance and speed, the sorting algorithms on this page will be listed from the (on average) worst, to best case implementations.

Selection sort and Insertion sort are two simple sorting algorithms which are often more efficient than Bubble Sort, though all three techniques aren’t the top of the class algorithmically for sorting large data sets.

====== BUBBLE SORT ======

``` #1 - Modified Bubble Sort C++ #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototype void BubbleSort(int arry[], int arraySize); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for(int x = 0; x < NUM_INTS; ++x) { arry[x] = rand()%100+1; } cout << "Original array values" << endl; // output the original array values for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "n--------------------------------------------------------n"; BubbleSort(arry, NUM_INTS); cout << "The current sorted array" << endl; // output the current sorted array values for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout<<endl; return 0; }// end of main void BubbleSort(int arry[], int arraySize) { bool sorted = false; do{ sorted = true; for(int x = 0; x < arraySize-1; ++x) { if(arry[x] > arry[x+1]) { int temp = arry[x]; arry[x] = arry[x+1]; arry[x+1] = temp; sorted = false; } }// end of for loop --arraySize; }while(!sorted); }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 #include <iostream>#include <iomanip>#include <ctime>#include <cstdlib>using namespace std; // const intconst int NUM_INTS = 12; // function prototypevoid BubbleSort(int arry[], int arraySize); int main(){     // variable declarations     int arry[NUM_INTS];     srand(time(NULL));      // place random numbers into the array     for(int x = 0; x < NUM_INTS; ++x)     {          arry[x] = rand()%100+1;     }       cout << "Original array values" << endl;     // output the original array values     for(int x = 0; x < NUM_INTS; ++x)     {          cout << setw(4) << arry[x];     }     // creates a line seperator      cout << "n--------------------------------------------------------n";      BubbleSort(arry, NUM_INTS);      cout << "The current sorted array" << endl;     // output the current sorted array values     for(int x = 0; x < NUM_INTS; ++x)     {          cout << setw(4) << arry[x];     }     cout<<endl;      return 0;}// end of main void BubbleSort(int arry[], int arraySize){     bool sorted = false;          do{          sorted = true;          for(int x = 0; x < arraySize-1; ++x)          {               if(arry[x] > arry[x+1])               {                    int temp = arry[x];                    arry[x] = arry[x+1];                    arry[x+1] = temp;                    sorted = false;               }           }// end of for loop          --arraySize;     }while(!sorted);}// http://programmingnotes.org/ ```

SAMPLE OUTPUT
(The following randomly generated list took 66 loop iterations/comparisons to sort)

```Original array values 91 65 53 93 54 41 69 76 55 90 10 62 -------------------------------------------------------- The current sorted array 10 41 53 54 55 62 65 69 76 90 91 93```

====== SELECTION SORT ======

``` #2 - Selection Sort C++ #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototype void SelectionSort(int arry[], int arraySize); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for(int x = 0; x < NUM_INTS; ++x) { arry[x] = rand()%100+1; } cout << "Original array values" << endl; // output the original array values for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "n--------------------------------------------------------n"; SelectionSort(arry, NUM_INTS); cout << "The current sorted array" << endl; // output the current sorted array values for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout<<endl; return 0; }// end of main void SelectionSort(int arry[], int arraySize) { for(int currentNumber = 0; currentNumber < arraySize; ++currentNumber) { int index_of_min = currentNumber; for(int previousNumber = currentNumber+1; previousNumber < NUM_INTS; ++previousNumber) { if(arry[index_of_min]>arry[previousNumber]) { index_of_min = previousNumber; } } int temp = arry[currentNumber]; arry[currentNumber] = arry[index_of_min]; arry[index_of_min] = temp; } }// http://programmingnotes.org/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 #include <iostream>#include <iomanip>#include <ctime>#include <cstdlib>using namespace std; // const intconst int NUM_INTS = 12; // function prototypevoid SelectionSort(int arry[], int arraySize); int main(){     // variable declarations     int arry[NUM_INTS];     srand(time(NULL));      // place random numbers into the array     for(int x = 0; x < NUM_INTS; ++x)     {          arry[x] = rand()%100+1;     }       cout << "Original array values" << endl;     // output the original array values     for(int x = 0; x < NUM_INTS; ++x)     {          cout << setw(4) << arry[x];     }     // creates a line seperator      cout << "n--------------------------------------------------------n";      SelectionSort(arry, NUM_INTS);      cout << "The current sorted array" << endl;     // output the current sorted array values     for(int x = 0; x < NUM_INTS; ++x)     {          cout << setw(4) << arry[x];     }     cout<<endl;      return 0;}// end of main void SelectionSort(int arry[], int arraySize){ for(int currentNumber = 0; currentNumber < arraySize; ++currentNumber) { int index_of_min = currentNumber; for(int previousNumber = currentNumber+1; previousNumber < NUM_INTS; ++previousNumber) { if(arry[index_of_min]>arry[previousNumber]) { index_of_min = previousNumber; } } int temp = arry[currentNumber]; arry[currentNumber] = arry[index_of_min]; arry[index_of_min] = temp; }}// http://programmingnotes.org/ ```

SAMPLE OUTPUT
(The following randomly generated list took 78 loop iterations/comparisons to sort)

```Original array values 87 74 58 64 4 43 23 16 3 93 9 80 -------------------------------------------------------- The current sorted array 3 4 9 16 23 43 58 64 74 80 87 93```

====== INSERTION SORT ======

``` #3 - Insertion Sort C++ #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototype void InsertionSort(int arry[], int arraySize); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for(int x = 0; x < NUM_INTS; ++x) { arry[x] = rand()%100+1; } // output the original array values cout << "Original array values" << endl; for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "n--------------------------------------------------------n"; InsertionSort(arry, NUM_INTS); // display sorted values cout<<"The current sorted array"<<endl; // output the current sorted array values for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) <<arry[x]; } cout<<endl; return 0; }// end of main void InsertionSort(int arry[], int arraySize) { int previousNumber = 0; int currentNumber = 0; // iterate through entire list for(int index = 1; index < arraySize; ++index) { currentNumber = arry[index]; previousNumber = index - 1; while(previousNumber >= 0 && arry[previousNumber] > currentNumber) { arry[previousNumber + 1] = arry[previousNumber]; previousNumber = previousNumber - 1; }// end while loop arry[previousNumber + 1] = currentNumber; }// end for loop }// http://programmingnotes.org/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 #include <iostream>#include <iomanip>#include <ctime>#include <cstdlib>using namespace std; // const intconst int NUM_INTS = 12; // function prototypevoid InsertionSort(int arry[], int arraySize); int main(){     // variable declarations     int arry[NUM_INTS];     srand(time(NULL));      // place random numbers into the array     for(int x = 0; x < NUM_INTS; ++x)     {          arry[x] = rand()%100+1;     }           // output the original array values     cout << "Original array values" << endl;     for(int x = 0; x < NUM_INTS; ++x)     {          cout << setw(4) << arry[x];     }      // creates a line seperator      cout << "n--------------------------------------------------------n";      InsertionSort(arry, NUM_INTS);      // display sorted values     cout<<"The current sorted array"<<endl;      // output the current sorted array values     for(int x = 0; x < NUM_INTS; ++x)     { cout << setw(4) <<arry[x];     }     cout<<endl;      return 0;}// end of main void InsertionSort(int arry[], int arraySize){ int previousNumber = 0; int currentNumber = 0; // iterate through entire list for(int index = 1; index < arraySize; ++index) { currentNumber = arry[index]; previousNumber = index - 1; while(previousNumber >= 0 && arry[previousNumber] > currentNumber) { arry[previousNumber + 1] = arry[previousNumber]; previousNumber = previousNumber - 1; }// end while loop arry[previousNumber + 1] = currentNumber; }// end for loop}// http://programmingnotes.org/ ```

SAMPLE OUTPUT
(The following randomly generated list took 41 loop iterations/comparisons to sort)

```Original array values 97 80 94 74 10 38 87 7 87 14 3 97 -------------------------------------------------------- The current sorted array 3 7 10 14 38 74 80 87 87 94 97 97```

====== QUICK SORT ======

Quicksort is one of the fastest sorting algorithms, and is often the best practical choice for sorting, as its average expected running time for large data sets is more efficient than the previously discussed methods.

``` #4 - Quick Sort C++ #include <iostream> #include <ctime> #include <iomanip> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototypes void QuickSort(int arry[], int arraySize); int Partition(int arry[], int arraySize, int pivotIndex); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for(int x = 0; x < NUM_INTS; ++x) { arry[x] = rand()%100+1; } cout << "Original array values" << endl; // output the original array values for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "n--------------------------------------------------------n"; QuickSort(arry, NUM_INTS); cout << "The current sorted array" << endl; // output the current sorted array values for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout<<endl; return 0; }// end of main void QuickSort(int arry[], int arraySize) { if(arraySize > 1) { // choose pivot int pivotIndex = rand()%(arraySize-1); // partition the arry and get the new pivot position int newPiviotIndex = Partition(arry, arraySize, pivotIndex); // quick sort the first part QuickSort(arry, newPiviotIndex); // quick sort the second part QuickSort(arry+newPiviotIndex+1, arraySize-newPiviotIndex-1); } }// end of QuickSort int Partition(int arry[], int arraySize, int pivotIndex) { int pivotValue = arry[pivotIndex]; arry[pivotIndex] = arry[arraySize-1]; // swap pivot with last element arry[arraySize-1] = pivotValue; int left = 0; // left index int right = arraySize-2; // right index while(left < right) { // ( < pivot ), pivot, ( >= pivot) while((arry[left] < pivotValue) && (left < right)) { ++left; } while((arry[right] >= pivotValue) && (left < right)) { --right; } if(left < right) { std::swap(arry[left],arry[right]); ++left; --right; } } if(left == right) { if(arry[left] < pivotValue) { ++left; } } arry[arraySize-1] = arry[left]; // move pivot to its final place arry[left] = pivotValue; return left; // return the position of the pivot }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798 #include <iostream>#include <ctime>#include <iomanip>#include <cstdlib>using namespace std; // const intconst int NUM_INTS = 12; // function prototypesvoid QuickSort(int arry[], int arraySize);int Partition(int arry[], int arraySize, int pivotIndex); int main(){     // variable declarations     int arry[NUM_INTS];     srand(time(NULL));      // place random numbers into the array     for(int x = 0; x < NUM_INTS; ++x)     {          arry[x] = rand()%100+1;     }       cout << "Original array values" << endl;     // output the original array values     for(int x = 0; x < NUM_INTS; ++x)     {          cout << setw(4) << arry[x];     }     // creates a line seperator      cout << "n--------------------------------------------------------n";      QuickSort(arry, NUM_INTS);      cout << "The current sorted array" << endl;     // output the current sorted array values     for(int x = 0; x < NUM_INTS; ++x)     {          cout << setw(4) << arry[x];     }     cout<<endl;      return 0;}// end of main void QuickSort(int arry[], int arraySize) {    if(arraySize > 1)     {        // choose pivot        int pivotIndex = rand()%(arraySize-1);         // partition the arry and get the new pivot position        int newPiviotIndex = Partition(arry, arraySize, pivotIndex);         // quick sort the first part        QuickSort(arry, newPiviotIndex);         // quick sort the second part        QuickSort(arry+newPiviotIndex+1, arraySize-newPiviotIndex-1);     }}// end of QuickSort int Partition(int arry[], int arraySize, int pivotIndex) {    int pivotValue = arry[pivotIndex];    arry[pivotIndex] = arry[arraySize-1]; // swap pivot with last element    arry[arraySize-1] = pivotValue;    int left = 0; // left index    int right = arraySize-2; // right index     while(left < right)     { // ( < pivot ), pivot, ( >= pivot)        while((arry[left] < pivotValue) && (left < right))        {            ++left;        }        while((arry[right] >= pivotValue) && (left < right))        {            --right;        }        if(left < right)         {            std::swap(arry[left],arry[right]);            ++left;            --right;        }    }    if(left == right)    {        if(arry[left] < pivotValue)        {            ++left;        }    }    arry[arraySize-1] = arry[left]; // move pivot to its final place    arry[left] = pivotValue;    return left; // return the position of the pivot}// http://programmingnotes.org/ ```

SAMPLE OUTPUT
(The following randomly generated list took 38 loop iterations/comparisons to sort)

```Original array values 50 94 1 16 51 63 41 17 70 28 6 34 -------------------------------------------------------- The current sorted array 1 6 16 17 28 34 41 50 51 63 70 94```

====== MERGE SORT ======

Merge sort is a fast, stable sorting routine which, in the worst case, does about (on average) 39% fewer comparisons than quick sort.

``` #5 - Merge Sort C++ #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototypes void MergeSort(int arry[], int start, int end); void Merge(int arry[], int leftFirst, int leftLast, int rightFirst, int rightLast); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for(int x = 0; x < NUM_INTS; ++x) { arry[x] = rand()%100+1; } cout << "Original array values" << endl; // output the original array values for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "n--------------------------------------------------------n"; MergeSort(arry, 0, NUM_INTS-1); cout << "The current sorted array" << endl; // output the current sorted for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout<<endl; return 0; }// end of main void MergeSort(int arry[], int start, int end) { // no significant comparisons are done during splitting if(start < end) { int midPt = (start+end)/2; MergeSort(arry,start, midPt); MergeSort(arry,midPt+1,end); Merge(arry, start,midPt, midPt+1, end); } }// end of MergeSort void Merge(int arry[], int leftFirst, int leftLast, int rightFirst, int rightLast) { int* tempArray = new int [rightLast]; int index = leftFirst; int saveFirst = leftFirst; while((leftFirst <= leftLast) && (rightFirst <= rightLast)) {// compare and select smallest from two subarrays if(arry[leftFirst] < arry[rightFirst]) { tempArray[index] = arry[leftFirst]; // smallest assigned to temp ++leftFirst; } else { tempArray[index] = arry[rightFirst]; ++rightFirst; } ++index; } while(leftFirst <= leftLast) { tempArray[index] = arry[leftFirst]; ++leftFirst; ++index; } while(rightFirst <= rightLast) { tempArray[index] = arry[rightFirst]; ++rightFirst; ++index; } for(index = saveFirst; index <= rightLast; ++index) {// copies from temp array to the initial array arry[index] = tempArray[index]; } }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596 #include <iostream>#include <iomanip>#include <ctime>#include <cstdlib>using namespace std; // const intconst int NUM_INTS = 12; // function prototypesvoid MergeSort(int arry[], int start, int end);void Merge(int arry[], int leftFirst, int leftLast, int rightFirst, int rightLast); int main(){ // variable declarations int arry[NUM_INTS]; srand(time(NULL));  // place random numbers into the array for(int x = 0; x < NUM_INTS; ++x) { arry[x] = rand()%100+1; } cout << "Original array values" << endl; // output the original array values for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "n--------------------------------------------------------n";  MergeSort(arry, 0, NUM_INTS-1); cout << "The current sorted array" << endl; // output the current sorted for(int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout<<endl;  return 0;}// end of main void MergeSort(int arry[], int start, int end){  // no significant comparisons are done during splitting    if(start < end)    {        int midPt = (start+end)/2;           MergeSort(arry,start, midPt);        MergeSort(arry,midPt+1,end);        Merge(arry, start,midPt, midPt+1, end);    }}// end of MergeSort void Merge(int arry[], int leftFirst, int leftLast, int rightFirst, int rightLast){ int* tempArray = new int [rightLast]; int index = leftFirst; int saveFirst = leftFirst; while((leftFirst <= leftLast)  && (rightFirst <= rightLast)) {// compare and select smallest from two subarrays if(arry[leftFirst] < arry[rightFirst]) { tempArray[index]  = arry[leftFirst]; // smallest assigned to temp ++leftFirst; } else { tempArray[index]  = arry[rightFirst]; ++rightFirst; } ++index; } while(leftFirst <= leftLast) { tempArray[index] = arry[leftFirst]; ++leftFirst; ++index; } while(rightFirst <= rightLast) { tempArray[index] = arry[rightFirst]; ++rightFirst; ++index; } for(index = saveFirst; index <= rightLast; ++index) {// copies from temp array to the initial array arry[index] = tempArray[index]; }}// http://programmingnotes.org/ ```

SAMPLE OUTPUT
(The following randomly generated list took 29 loop iterations/comparisons to sort)

```Original array values 18 46 41 30 84 97 54 49 19 32 70 30 -------------------------------------------------------- The current sorted array 18 19 30 30 32 41 46 49 54 70 84 97```

### One Response to C++ || Snippet – Bubble Sort, Selection Sort, Insertion Sort, Quick Sort & Merge Sort Sample Code For Integer Arrays

1. putri says:

I see you’re code but why if we want to be they are in one main ? I mean the selection,insertion,bubble,merge sort in the one program ?