SelectionSort in c not sorting*-CodePudding

I am having a tough time trying to follow the logic here as to why it is not working correctly expected output : 1 5 6 8

any help is greatly appreciated

Update: I got selection sort and insertion sort mixed up

OUTPUT:
unaltered array
5 8 1 6

1  -858993460 -858993460  6

#pragma once
#include <iostream>
using namespace std;


void swap(int &a,int &b)
{
 int temp;
 temp = b;
 b = a;
 a = temp;
}
void SelectionSort(int *arr,int n)
{
 cout << "SelectionSORT1\n";

 int i;
 for (i = 0; i < n - 2; i  ) //-1 ||-2//
 {
  int firstIndex;
  firstIndex = arr[i];
    
    int j;
    for (j = i   1;j < n - 1;j  ) 
    {
        if (arr[j] < arr[firstIndex])
        {
            firstIndex = j;
            //cout << firstIndex;
            
        }
        swap(arr[i], arr[firstIndex]);

       }
    
        cout << "SelectionSORT2\n";

        }
cout << "SelectionSORT3\n";
}

#include <iostream>
#include "SelectionSort.h"


using namespace std;

int main()
{
 int array[] = { 5,8,1,6 };
 int size = { sizeof(array) / sizeof(array[0]) };
 cout << "unaltered array\n";
for (int i = 0; i < 4; i  )
{
    cout << array[i] << "  ";
}
cout << endl;

SelectionSort(array, size);

for (int i = 0; i < 4; i  )
{
    cout << array[i] << "  ";
}
cout << endl;
}

UPDATE

#pragma once
#include <iostream>
using namespace std;


void swap(int &a,int &b)
{
 int temp;
 temp = b;
 b = a;
 a = temp;
}
void SelectionSort(int *arr,int n)
{
 cout << "Selection SORT1\n";

 int I;
 for (i = 0; i < n ; i  ) //-1 ||-2//
 {
    int firstIndex;
    firstIndex = i;
    int j;
    for (j = i   1;j < n  ;j  ) 
    {
        std::cerr << j << ' ' << firstIndex << '\n';
        if (arr[j] < arr[firstIndex])
        {
            firstIndex = j;
            
            
        }
        swap(arr[i], arr[firstIndex]);

    }
    
    cout << "  \n";

 }
cout << "  \n";
}

#include <iostream>
#include "BubbleSort.h"
#include "InsertionSort.h"
#include "SelectionSort.h"

using namespace std;

int main()
{
 int array[] = { 5,8,1,6 };
 int size = { sizeof(array) / sizeof(array[0]) };
 cout << "unaltered array\n";
 for (int i = 0; i < size; i  )
 {
    cout << array[I] << "  ";
 }
 cout << endl;
 SelectionSort(array, size);

 for (int i = 0; i < size; i  )
 {
    cout << array[I] << "  ";
 }
 cout << endl;

unaltered array
5 8 1 6
SelectionSORT1
1 0
2 0
3 2

2 1
3 2

3 2

5 6 1 8

CodePudding user response：

You are using the selection sort method not the insertion sort method.

Bit in any case the function is incorrect

void InsertionSort(int *arr,int n)
{
 cout << "INSERTION SORT1\n";

 int i;
 for (i = 0; i < n - 2; i  ) //-1 ||-2//
 {
  int firstIndex;
  firstIndex = arr[i];
    
    int j;
    for (j = i   1;j < n - 1;j  ) 
    {
        if (arr[j] < arr[firstIndex])
        {
            firstIndex = j;
            //cout << firstIndex;
            
        }
        swap(arr[i], arr[firstIndex]);

       }
    
        cout << "INSERTION SORT2\n";

        }
cout << "INSERTION SORT3\n";
}

For starters it will not sort an array that has two elements due to this for loop

 for (i = 0; i < n - 2; i  ) //-1 ||-2//

Secondly, the variable firstIndex is not initialized by a value of the index i

  firstIndex = arr[i];

So the condition in this if statement

if (arr[j] < arr[firstIndex])

does not make a sense.

Thirdly this inner for loop

for (j = i   1;j < n - 1;j  )

ignores the last element of the array.

Fourth, this unconditional call of the function swap within the inner for loop

swap(arr[i], arr[firstIndex])

also does not make a sense.

The function can look the following way

void SelectionSort( int a[], size_t n )
{
    for ( size_t i = 0; i < n; i   )
    {
        size_t min = i;

        for ( size_t j = i   1; j < n; j   ) 
        {
            if ( a[j] < a[min] )
            {
                min = j;
            }                
        }

        if ( min != i ) swap( a[i], a[min] );
    }
}

And in main the variable size should have the type size_t - the type of the value of the expression with the operator sizeof

const size_t size = sizeof(array) / sizeof(array[0]);

And instead of the magic number 4 in for loops in main you should use the named constant size or you could use the range-based for loop as

 for ( const auto &item : array )
 {
    cout << item << ' ';
 }
 cout << endl;

If you indeed mean the insertion sort method then a corresponding function can look for example the following way

void InsertionSort( int a[], size_t n )
{
    for (size_t i = 1; i < n; i  )
    {
        if (a[i] < a[i - 1])
        {
            int tmp = a[i];

            size_t j = i;
            for ( ; j != 0 && tmp < a[j - 1]; --j )
            {
                a[j] = a[j - 1];
            }

            a[j] = tmp;
        }
    }
}

CodePudding user response：

Thank you all for your help I got it to work like this

 #pragma once
 #include <iostream>
 using namespace std;


 void swap(int &a,int &b)
 {
  int temp;
  temp = b;
  b = a;
  a = temp;
 }
 void InsertionSort(int arr[],int n)
 {
  int i;
  for (i = 0; i < n ; i  ) 
  {
    int firstIndex,j;
    firstIndex = i;
    for (j = i   1;j < n ;j  ) 
    {
        if (arr[j] < arr[firstIndex])
        {
            firstIndex = j;
        }
    }
    swap(arr[i], arr[firstIndex]);  
 }
}

CodePudding user response：

The following is C :

std::set<int> sorted_array({ 5,8,1,6 });

If you have duplicates and need to keep them, use:

std::multiset<int> sorted_array({ 5,8,1,6 });

Done. One line.