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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
// ============================================================================ // 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/ |
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 ======
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
// ============================================================================ // 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/ |
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 ======
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
// ============================================================================ // 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/ |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
// ============================================================================ // 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/ |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
// ============================================================================ // 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/ |
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
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
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 ?