SelectionSort in c++ not sorting*

Question

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

Add the line `std::cerr << j << ' ' << firstIndex << '\n';` just above the line `if (arr[j] < arr[firstIndex])`. See anything strange? Hint: `5` is out of bounds since `arr[3]` is the last valid element. Follow-up: `firstIndex = arr[i];` why is `firstIndex` picking a value from the array (in the first case, `5`) and use that as an index? — Ted Lyngmo, Sep 15 '22 at 21:38
thanks for your comment, but there is still something in my code causing the issue, this displayed insertion sort1\n 1 5 \n 2 5 \n insertion sort2 \n 2 8 \n insertion sort2 \n insertion sort3\n 1 -858993461 -858993461 6 *where "\n" is a new line in the console — SurlyGent, Sep 15 '22 at 21:41
_"still something in my code causing issue"_ - I don't see that you've updated your code so I can't comment on what it could be. — Ted Lyngmo, Sep 15 '22 at 21:42

Vlad from Moscow · Answer 1 · 2022-09-15T22:40:01.493

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;
        }
    }
}

You are always helpful Vlad thanks! There is also a very popular Q. How to implement Classical sorting algorithms in "Modern C++". https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c — Captain Giraffe, Sep 15 '22 at 22:04

score -1 · Answer 2 · answered Sep 15 '22 at 22:35

-1

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]);  
 }
}

answered Sep 15 '22 at 22:35

SurlyGent

17
2

2

Remove this your answer because it does not make a sense and to close your question select the best answer and your reputation will be increased.:) – Vlad from Moscow Sep 15 '22 at 22:41
This is still a bad solution, look at Vlads answer closely. – Captain Giraffe Sep 15 '22 at 22:57
If it's meant to be an answer, it's a really bad one. Either explain how this answers your question - or remove it and accept the answer that gave you the help you needed to solve your problem. – Ted Lyngmo Sep 16 '22 at 14:59

Alexis Wilke · Answer 3 · 2022-09-15T22:03:40.140

-2

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.

edited Sep 15 '22 at 22:03

answered Sep 15 '22 at 21:42

Alexis Wilke

19,179
10
84
156

3

As long as there aren't any duplicate elements... – Alan Birtles Sep 15 '22 at 21:46
2

Does this involve selection sort? – Evg Sep 15 '22 at 21:48
2

nobody needs a smart mouth – SurlyGent Sep 15 '22 at 21:53
@Evg According to the [`insert()` complexity](https://en.cppreference.com/w/cpp/container/set/insert#Complexity) (see entry 5), _"O(N*log(size() + N)), where N is the number of elements to insert."_. – Alexis Wilke Sep 15 '22 at 22:02
And this rules out insertion sort, which is O(N^2) (_selection_ -> _insertion_ in my first comment). – Evg Sep 15 '22 at 22:05
And this rules out selection sort which is *guaranteed* N^2. – Captain Giraffe Sep 15 '22 at 22:06

SelectionSort in c++ not sorting*

3 Answers3