Basic Sorting Algorithm

[jgialis]

Hello all.

I am going to take an algorithm analysis class which starts next week. I have very little knowledge of algorithms but I decided to try and code a basic sorting algorithm my self before starting the class.

It seems I am on the right track since I get the correct output when the input of numbers is initially in a decreasing sequence, but that seems to be the only time it works.


I am not sure where I am messing up, but I have some ideas.

Please let me know where I am going wrong. Thanks.

#include <iostream>

using namespace std;

int main(){
    int a[5] = {2,1,4,3,5};
    
    cout << "Unsorted array: ";
    for (int m = 0; m < 5; m++) {
        cout << a[m] << ", ";
    }
    
    cout << endl;
        int min = 0;
        int index = 0;
        int temp = 0;
        
    for (int j = 0; j < 5; j++) {
        
//        cout << "List: ";
//        for (int p = 0; p < 3; p++)
//        cout << a[p] << ", ";
        
//        cout << "\nJ iteration: " << j << endl;
        min = a[j];
//        cout << "min = a[" << j << "] = " << a[j] << endl << endl;
        
        for (int i = j + 1; i < 5; i++) {
//            cout << min << " > " << a[i] << endl;
            if (min > a[i]) {
                min = a[i];
                index = i;
//                cout << "min = " << a[i] << endl;
//                cout << "index = " << i << endl;
            }
            temp = a[j];
            a[j] = min;
            a[index] = temp;
            cout << "temp = a[" << j << "] = " << a[j] << endl;
            cout << "a[j] = " << min << endl;
            cout << "a[index] = " << temp << endl << endl << endl << endl;
        }
    }
    
    
    cout << "Sorted array: ";
    for (int n = 0; n < 5; n++) {
        cout << a[n] << ", ";
    }
    
    
    cout << endl << endl;
    
}

[dutch]

You need to move the swap outside of the loop that finds the min.

#include <iostream>
using namespace std;

int main() {

    int a[] = { 2, 1, 4, 3, 5 };
    int sz = sizeof a / sizeof *a;
    
    cout << "Unsorted array: ";
    for (int i = 0; i < sz; ++i)
        cout << a[i] << ", ";
    cout << '\n';

    for (int i = 0; i < sz; ++i) {
        int min = i;
        for (int j = i + 1; j < sz; ++j)
            if (a[j] < a[min])
                min = j;
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }

    cout << "Sorted array  : ";
    for (int i = 0; i < sz; ++i)
        cout << a[i] << ", ";
    cout << '\n';
}

[jgialis]

Thanks! I appreciate the help.

[jonnin]

shell sort for fun... you may not see this one in your class, and the analysis of it for different sequences can fill an entire chapter. Maybe circle back to it after you do the sorting section in class...

void vec_sort (vector<double> &m) 
{      
   const    
   static vector<unsigned int> harr =
	{  0, //terminal condition for sort	      
	 1,4,19,87, 388,1725,7661,34015, 151030,670574,2977348,13219428,  	  
      999999999 //terminal condition for find index		
	};
   const unsigned int size = m.size();
   unsigned int i;
   unsigned int j, dx = 1;
   while(size > harr[dx]) dx++;  
   while(--dx)
	{
       const unsigned int &hdx = harr[dx]; 		   
	   for(i = 1; i < size; i++)
		{		 
                  const double temp = m[i];         
                  for(j = i; (j >= hdx) && (m[j-hdx] > temp); j -= hdx)
                   {			
                      m[j] = m[j-hdx];          		
                   }
                 m[j] = temp;           		 		 
		} 
	}   
}

[jgialis]

Thanks jonnin I will look it over.


If I may ask, why does the switch need to be inside the inner loop, instead of outside?