## 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++ // ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: bubbleSort.cpp // Description: Demonstrates how to sort an array using bubble sort // ============================================================================ #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; cin.get(); 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/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273 // ============================================================================//    Author: Kenneth Perkins//    Date:   Feb 11, 2012//    Taken From: http://programmingnotes.org///    File:  bubbleSort.cpp//    Description: Demonstrates how to sort an array using bubble sort// ============================================================================#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;     cin.get();    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:

```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++ // ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: selectionSort.cpp // Description: Demonstrates how to sort an array using selection sort // ============================================================================ #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; cin.get(); 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 < arraySize; ++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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172 // ============================================================================//    Author: Kenneth Perkins//    Date:   Feb 11, 2012//    Taken From: http://programmingnotes.org///    File:  selectionSort.cpp//    Description: Demonstrates how to sort an array using selection sort// ============================================================================#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;     cin.get();    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 < arraySize; ++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:

```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++ // ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: insertionSort.cpp // Description: Demonstrates how to sort an array using insertion sort // ============================================================================ #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; cin.get(); return 0; }// end of main void InsertionSort(int arry[], int arraySize) { int previousIndex = 0; int currentValue = 0; // iterate through entire list for (int index = 1; index < arraySize; ++index) { currentValue = arry[index]; previousIndex = index - 1; while (previousIndex >= 0 && arry[previousIndex] > currentValue) { arry[previousIndex + 1] = arry[previousIndex]; previousIndex = previousIndex - 1; }// end while loop arry[previousIndex + 1] = currentValue; }// end for loop }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475 // ============================================================================//    Author: Kenneth Perkins//    Date:   Feb 11, 2012//    Taken From: http://programmingnotes.org///    File:  insertionSort.cpp//    Description: Demonstrates how to sort an array using insertion sort// ============================================================================#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;     cin.get();    return 0;}// end of main void InsertionSort(int arry[], int arraySize){    int previousIndex = 0;    int currentValue = 0;     // iterate through entire list    for (int index = 1; index < arraySize; ++index)    {        currentValue = arry[index];        previousIndex = index - 1;         while (previousIndex >= 0 && arry[previousIndex] > currentValue)        {            arry[previousIndex + 1] = arry[previousIndex];            previousIndex = previousIndex - 1;        }// end while loop        arry[previousIndex + 1] = currentValue;    }// end for loop}// http://programmingnotes.org/ ```

SAMPLE OUTPUT:

```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++ // ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: quickSort.cpp // Description: Demonstrates how to sort an array using quick sort // ============================================================================ #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); void QuickSort(int arry[], int start, int end); int Partition(int arry[], int start, int end); 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; cin.get(); return 0; }// end of main // the initial function call and initiates the sort void QuickSort(int arry[], int arraySize) { QuickSort(arry, 0, arraySize - 1); }// end of QuickSort // recursive call that carries out the sort void QuickSort(int arry[], int start, int end) { if (start < end) { // partition the arry and get the new pivot position int newPiviotIndex = Partition(arry, start, end); // quick sort the first part QuickSort(arry, start, newPiviotIndex); // quick sort the second part QuickSort(arry, newPiviotIndex + 1, end); } }// end of QuickSort int Partition(int arry[], int start, int end) { // choose a random pivot int pivotIndex = start + rand() % (end - start + 1); std::swap(arry[end], arry[pivotIndex]); // swap pivot with last element int left = start; // left index int right = end; // right index // compare and select smallest from the subarray for (int index = start; index <= right; ++index) { if (arry[index] < arry[right]) { std::swap(arry[index], arry[left]); ++left; } } // move pivot to its final place std::swap(arry[right], arry[left]); return left; // return the position of the new pivot }// http://programmingnotes.org/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697 // ============================================================================//    Author: Kenneth Perkins//    Date:   Feb 11, 2012//    Taken From: http://programmingnotes.org///    File:  quickSort.cpp//    Description: Demonstrates how to sort an array using quick sort// ============================================================================#include <iostream>#include <ctime>#include <iomanip>#include <cstdlib>using namespace std; // const intconst int NUM_INTS = 12; // function prototypesvoid QuickSort(int arry[], int arraySize);void QuickSort(int arry[], int start, int end);int Partition(int arry[], int start, int end); 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;     cin.get();    return 0;}// end of main // the initial function call and initiates the sortvoid QuickSort(int arry[], int arraySize) {    QuickSort(arry, 0, arraySize - 1);}// end of QuickSort // recursive call that carries out the sortvoid QuickSort(int arry[], int start, int end){    if (start < end)    {        // partition the arry and get the new pivot position        int newPiviotIndex = Partition(arry, start, end);        // quick sort the first part        QuickSort(arry, start, newPiviotIndex);        // quick sort the second part        QuickSort(arry, newPiviotIndex + 1, end);    }}// end of QuickSort int Partition(int arry[], int start, int end){    // choose a random pivot    int pivotIndex = start + rand() % (end - start + 1);    std::swap(arry[end], arry[pivotIndex]); // swap pivot with last element    int left = start; // left index    int right = end; // right index     // compare and select smallest from the subarray    for (int index = start; index <= right; ++index)    {        if (arry[index] < arry[right])        {            std::swap(arry[index], arry[left]);            ++left;        }    }    // move pivot to its final place    std::swap(arry[right], arry[left]);     return left; // return the position of the new pivot}// http://programmingnotes.org/ ```

SAMPLE OUTPUT:

```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++ // ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: mergeSort.cpp // Description: Demonstrates how to sort an array using merge sort // ============================================================================ #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 arraySize); void MergeSort(int arry[], int start, int end); void Merge(int arry[], int start, int midPt, int end); 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, NUM_INTS); 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; cin.get(); return 0; }// end of main // the initial function call and initiates the sort void MergeSort(int arry[], int arraySize) { MergeSort(arry, 0, arraySize - 1); }// end of MergeSort // recursive call that carries out the sort 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, end); } }// end of MergeSort // sorts the sub array void Merge(int arry[], int start, int midPt, int end) { int leftFirst = start; int leftLast = midPt; int rightFirst = midPt + 1; int rightLast = end; int* tempArray = new int[rightLast + 1]; 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]; } delete[] tempArray; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119 // ============================================================================//    Author: Kenneth Perkins//    Date:   Feb 11, 2012//    Taken From: http://programmingnotes.org///    File:  mergeSort.cpp//    Description: Demonstrates how to sort an array using merge sort// ============================================================================#include <iostream>#include <iomanip>#include <ctime>#include <cstdlib>using namespace std; // const intconst int NUM_INTS = 12; // function prototypesvoid MergeSort(int arry[], int arraySize);void MergeSort(int arry[], int start, int end);void Merge(int arry[], int start, int midPt, int end); 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, NUM_INTS);     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;     cin.get();    return 0;}// end of main // the initial function call and initiates the sortvoid MergeSort(int arry[], int arraySize){    MergeSort(arry, 0, arraySize - 1);}// end of MergeSort // recursive call that carries out the sortvoid 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, end);    }}// end of MergeSort // sorts the sub arrayvoid Merge(int arry[], int start, int midPt, int end){    int leftFirst = start;    int leftLast = midPt;    int rightFirst = midPt + 1;    int rightLast = end;    int* tempArray = new int[rightLast + 1];    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];    }     delete[] tempArray;}// http://programmingnotes.org/ ```

SAMPLE OUTPUT:

```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```

Was this article helpful?
👍 YesNo

### 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 ?