Skip to content

Instantly share code, notes, and snippets.

@juanfal

juanfal/99.ordenarSelectInsertBub.cpp

Created November 4, 2025 11:08
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save juanfal/e016bc8320603bf5916062248bf61d30 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save juanfal/e016bc8320603bf5916062248bf61d30 to your computer and use it in GitHub Desktop.
Download ZIP
SelectSort BubbleSort BubbleSortOpt ShakeSort InsertSort SelectSortIndex
Raw
99.ordenarSelectInsertBub.cpp
// 99.ordenarSelectInsertBub.cpp
// juanfc 2025-11-04
//
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <array>
using namespace std;
const int N = 25;
typedef array<int, N> TVec;
int main()
{
void SelectSort(TVec& a);
void BubbleSort(TVec& a);
void BubbleSortOpt(TVec& a);
void ShakeSort(TVec& a);
void InsertSort(TVec& a);
void SelectSortIndex(TVec& idx, TVec& a);
void randomFillArr(TVec& a); // fills a random array
void printArray(TVec a); // Display an array
void printIndexedArr(TVec idx, TVec a); // Display by indexes
TVec a, aa, idx;
randomFillArr(aa);
a = aa;
cout << setw(18) << "Before: ";
printArray(a);
cout << "Sorting by:" << endl;
cout << setw(18) << "SelectSort: ";
SelectSort(a);
printArray(a);
a = aa;
cout << setw(18) << "InsertSort: ";
InsertSort(a);
printArray(a);
a = aa;
cout << setw(18) << "BubbleSort: ";
BubbleSort(a);
printArray(a);
a = aa;
cout << setw(18) << "BubbleSortOpt: ";
BubbleSortOpt(a);
printArray(a);
a = aa;
cout << setw(18) << "ShakeSort: ";
ShakeSort(a);
printArray(a);
a = aa;
cout << setw(18) << "SelectSortIndex: ";
SelectSortIndex(idx, a);
printIndexedArr(idx, a);
return 0;
}
/**********************
* *
* sorting methods *
* *
**********************/
void SelectSort(TVec& a)
{
int ilowestFrom(TVec, int);
void swap(TVec&, int, int);
for (int i = 0; i < N; ++i)
swap(a, i, ilowestFrom(a, i));
}
void InsertSort(TVec& a)
{
for (int i = 1; i < N; ++i)
if (a[i] < a[i-1]) {
int x = a[i];
int j=i-1;
while ( j >= 0 and a[j] > x ) {
a[j+1]= a[j];
j--;
}
a[j+1]=x;
}
}
void InsertSort2(TVec& a)
{
void insertDown(TVec&, int);
for (int i = 1; i < N; ++i)
if (a[i] < a[i-1])
insertDown(a, i);
}
void insertDown(TVec& a, int pos)
{
int x = a[pos];
int j = pos-1;
while ( j >= 0 and a[j] > x) {
a[j+1]= a[j];
j--;
}
a[j+1]=x;
}
void BubbleSort(TVec& a)
{
void swap(TVec&, int, int);
for (int top = N-1; top >= 1; top--)
for (int i = 0; i < top; ++i)
if ( a[i] > a[i+1])
swap(a, i, i+1);
}
void BubbleSortOpt(TVec& a)
{
void swap(TVec&, int, int);
bool wasChanged;
int top = N-1;
do {
wasChanged = false;
for (int i = 0; i < top; ++i)
if (a[i] > a[i+1]) {
swap(a, i, i+1);
wasChanged = true;
}
top--;
} while (top >= 1 and wasChanged);
}
void SelectSortIndex(TVec& idx, TVec& a)
{
void swap(TVec&, int, int);
for ( int i = 0; i < N; ++i)
idx[i] = i;
for ( int i = 0; i < N; ++i) {
int tmp = i;
for ( int j = i+1; j < N; ++j )
if (a[idx[j]] < a[idx[tmp]])
tmp = j;
swap(idx, i, tmp);
}
}
// see animation: http://youtu.be/SIbfrKNlL0w
void ShakeSort(TVec& a)
{
void swap(TVec&, int, int);
int iz = 1;
int de = N-1;
int k = de;
do {
// raise element higher
for ( int j = de; j >= iz; --j ) {
if (a[j-1] > a[j]) {
swap(a, j-1, j);
k = j;
}
}
// lower element lower
iz = k+1;
for ( int j = iz+1; j <= de; ++j ) {
if (a[j-1] > a[j]) {
swap(a, j-1, j);
k = j;
}
}
de = k-1;
} while ( iz <= de );
}
/****************
* *
* Utilities *
* *
****************/
int ilowestFrom(TVec a, int pos)
{
int tmp = pos;
for ( int i = pos+1; i < N; ++i )
if (a[i] < a[tmp])
tmp = i;
return tmp;
}
void randomFillArr(TVec& a)
{
// srandom(); // if we want to pre-randomize
for (int i = 0; i < N; ++i)
a[i] = random() % N; // limit sizes
}
void printArray(TVec a)
{
for (int i = 0; i < N; ++i)
cout << setw(3) << a[i];
cout << endl;
}
void printIndexedArr(TVec idx, TVec a)
{
for (int i = 0; i < N; ++i)
cout << setw(3) << a[idx[i]];
cout << endl;
}
void swap(TVec& a, int i, int j)
{
int t = a[i];
a[i] = a[j]; a[j] = t;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment